April 14, 2018 Single Round Match 733 Editorials

The author of this round is [ltdtl].
Div II Easy::MinimizeAbsoluteDifferenceDiv2
In this problem, we have an expression with three integers a,b,c and we want to arrange them to minimize the value of |?/? – ?|. This is an easier version of the div1 easy.
This is mainly an implementation problem. We can try all 3! = 6 permutations take the one that results in the minimum value. The time complexity is O(n! * n) where n = 3 in this problem.

#include<bits/stdc++.h>
using namespace std;
struct MinimizeAbsoluteDifferenceDiv2{
    vector <int> findTriple(int x0, int x1, int x2) {
        int x[3]={x0,x1,x2};
        int p[3]={0,1,2};
        for(int i=0;i<3;i++)assert(x[i]>=1 && x[i] <=10000);
        vector <int> an(3);
        double mi=1e18;
        do{
            double v=fabs(x[p[0]]*1./x[p[1]]-x[p[2]]);
            if(v<mi){
                mi=v;
                an=vector <int> (p,p+3);
            }
        }while(next_permutation(p,p+3));
        return an;
    }
};

 
Div II Medium::BulidingSpanningTreeDiv2
In this problem, we are given a complete graph with n nodes, and n-3 “special” edges. We need count the number of spanning trees that contain all of these edges. This is an easier version of the div1 medium.
First, if there are any cycles in E, then the answer is zero, since a spanning tree can’t have a cycle.
The actual topology of E doesn’t matter, what matters is the sizes of the connected components it forms. In addition, since E has n-3 edges and no cycles, there will be exactly 3 components left over.
Let the sizes of these components be s_0, s_1, s_2.
To form a spanning tree, we must add two more edges. There are three possible edges we can add, of which we need to choose exactly two of them.
1) We add an edge between s_0, s_1. This can be done in s_0*s_1 ways. (A)
2) We add an edge between s_0, s_2. This can be done in s_0*s_2 ways. (B)
3) We add an edge between s_1, s_2. This can be done in s_1*s_2 ways. (C)
Thus, the final answer is the sum of products of choosing two of the edges, which is A*B + A*C + B*C = (s_0*s_1) * (s_0*s_2) + (s_0*s_1) * (s_1*s_2) + (s_0*s_2) * (s_1*s_2).
The time it takes to find the sizes of the components is similar to using Kruskal’s and union find which takes O(n * \alpha(n)), where \alpha(n) is the inverse ackermann function.
Don’t forget about the modulo.
C++ code:

  #include<bits/stdc++.h>
#define SZ(X) (int)((X).size())
using namespace std;
const int SIZE = 1024;
const int MOD = 987654323;
int d[SIZE],num[SIZE];
void uu(int x,int y) {
    while(x != d[x]) x = d[x];
    while(y != d[y]) y = d[y];
    if(x == y) return;
    d[x] = d[y];
    num[y] += num[x];
}
struct BuildingSpanningTreesDiv2{
    int getNumberOfSpanningTrees(int n, vector <int> x, vector <int> y){
        assert(4 <= n && n <= 1000);
        int m = n - 3;
        assert(SZ(x) == m && SZ(y) == m);
        for(int i = 1; i <= n; i++) {
            d[i] = i;
            num[i] = 1;
        }
        for(int i = 0; i < m; i++) {
            assert(1 <= x[i] && x[i] < y[i] && y[i] <= n);
            uu(x[i], y[i]);
        }
        vector<long long> gg;
        for(int i = 1; i <= n; i++) {
            if(d[i] == i) gg.push_back(num[i]);
        }
        if(SZ(gg) != 3) return 0;
        return (gg[0] * gg[1] * gg[1] * gg[2] +
                gg[0] * gg[2] * gg[2] * gg[1] +
                gg[1] * gg[0] * gg[0] * gg[2]) % MOD;
    }
};

Div II Hard::HamiltonianPathsInGraph
This is a classic problem where we want to find a hamiltonian path in a tournament graph. There may already exist some resources online about it (see this link for example: https://math.stackexchange.com/questions/1682492/prove-that-every-tournament-contains-at-least-one-hamiltonian-path). This is an easier version of the div1 hard.
We will prove an answer always exists by constructing one. We do this by induction.
First, our base case is when n=1, which is just a path with a single node.
Now, consider an arbitrary n > 1, and suppose we have constructed a hamiltonian path of the vertices {0,1,2,..,n-2} and we want to add vertex n-1.
For each node {0,1,2,…,n-2}, color node i red if there is an edge from i to n-1, otherwise color node i blue if there is an edge from n-1 to i.
Suppose the hamiltonian path on {0,1,2,..,n-2} is p_0, p_1, …, p_{n-2}.
If p_0 is blue, we can append node n-1 to the beginning. If p_{n-2} is red, then we can append node n-1 to the end. So, now let’s consider the harder case when p_0 is red and p_{n-2} is blue.
We want to find p_i and p_{i+1} such that p_i is red and p_{i+1} is blue.
This must exist, since the first node in our path is red, and the last node is blue, so at some point, it must switch from red to blue, at which point we can insert n.
Thus, this shows that we can always extend the hamiltonian path by 1, which completes our induction and gives us an algorithm.
To implement this, we can follow the steps in our induction above. There are n times where we add nodes, and each of those steps takes O(n) time (O(n) to classify the previous nodes as red or blue, and O(n) time to insert our new node into this list).
Java Code

import java.util.Set;
import java.util.HashSet;
public
class HamiltonianPathsInGraph {
	public int[] findPath(String[] X) {
		int n = X.length;
		int[] left = new int[128], right = new int[128];
		int start, end;
		int ans[] = new int[n];
		start = end = 0;
		left[0] = right[0] = -1;
		for(int i = 1; i < n; i++) { if(X[i].charAt(start) == '+') { // i->start
				left[start] = i;
				right[i] = start;
				left[i] = -1;
				start = i;
				continue;
			}
			if(X[end].charAt(i) == '+') { // end -> i
				right[end] = i;
				left[i] = end;
				right[i] = -1;
				end = i;
				continue;
			}
			// start->i && i->end
			int j = start;
			while(X[j].charAt(i) == '+') j = right[j];
			// X[left[j]][i] = '+' & X[i][j] = '+';
			int k = left[j];
			right[k] = i; left[i] = k;
			left[j] = i; right[i] = j;
		}
		int x = start, idx = 0;
		while(x != -1) {
			ans[idx] = x;
			idx++;
			x = right[x];
		}
		return ans;
	}
}

Div I Easy::MinimizeAbsoluteDifferenceDiv1
In this problem, you are given five variables a,b,c,d,e and you want to put four of them in the expression |?/? – ?/?| so the resulting value is minimized. This is a harder version of the div2 easy.
This is an implementation problem. Here, we can try all 5! permutations of replacement, and take the minimum possible value. The time complexity is O(n! * n) where n = 5.
Java Code:

class MinimizeAbsoluteDifferenceDiv1 {
	public int[] findTuple(int[] x) {
		int[]	ans = new int[4];
		long ans1 = 0, ans2 = 0;
		for(int i = 0; i < 5; i++) {
			for(int j = 0; j < 5; j++) {
				if(i == j)continue;
				for(int k = 0; k < 5 ; k++) {
					if(k == i || k == j) continue;
					for(int l = 0; l < 5; l++) {
						if(l == i || l == j || l == k) continue;
						long a = x[i], b = x[j], c = x[k], d = x[l];
						long f1 = (a*d - c*b), f2 = b*d;
						if(f1 < 0) f1 = -f1;
						if(ans2 == 0 || (ans1*f2 > f1*ans2)) {
							ans1 = f1;
							ans2 = f2;
							ans[0] = i;
							ans[1] = j;
							ans[2] = k;
							ans[3] = l;
						}
					}
				}
			}
		}
		return ans;
	}
	public String checkData(int[] x) {
		if(x == null || x.length != 5)
			return "x must contain exactly five elements.";
		for(int i = 0; i < x.length; i++) {
			if(x[i] < 1 || x[i] > 10000) {
				return String.format("Element " + i + " of x must be between 1 and 10,000, inclusive.");
			}
		}
		return "";
	}

Div I Medium::BuildingSpanningTreeDiv1
In this problem, you are given a complete graph with n nodes, and some special edges. We want to count the number of spanning trees that contain all of these edges. This is a harder version of the div2 medium.
This is a classic problem (a similar problem can be found here: http://codeforces.com/problemset/problem/156/D). An editorial (only in russian) can be found here: http://codeforces.com/blog/entry/4005?locale=en, which I’ll briefly summarize. The first few steps are similar as in the div2 solution.
Namely, if there are any cycles in E, the answer is zero.
Otherwise, the actual topology of E doesn’t matter, what matters is the size of each connected component.
Let these sizes be s_0, s_1, …, s_{k-1}. The answer is (n)^(k – 2) * s_0 * s_1 * … * s_{k-1}.
The proof can be seen as a generalization of Caley’s formula on the number of trees with n nodes. You can also see this math stack exchange link for some more information: https://math.stackexchange.com/questions/2550064/proof-of-generalized-cayleys-formula
The complexity analysis is similar to div2 medium, where the time is dominated by needing to find the sizes of the components, which is O(n * \alpha(n)), where \alpha(n) is the inverse ackermann function.
C++ code:

#include<bits/stdc++.h>
#define SZ(X) (int)((X).size())
using namespace std;
const int SIZE = 1024;
const int MOD = 987654323;
int d[SIZE],num[SIZE];
bool uu(int x,int y) {
    while(x != d[x]) x = d[x];
    while(y != d[y]) y = d[y];
    if(x == y) return 0;
    d[x] = d[y];
    num[y] += num[x];
    return 1;
}
struct BuildingSpanningTreesDiv1{
    int getNumberOfSpanningTrees(int n, vector <int> x, vector <int> y){
        assert(1 <= n && n <= 1000);
        int m = SZ(x);
        assert(SZ(y) == m);
        for(int i = 1; i <= n; i++) {
            d[i] = i;
            num[i] = 1;
        }
        set<pair<int,int>>H;
        for(int i = 0; i < m; i++) {
            assert(1 <= x[i] && x[i] < y[i] && y[i] <= n);
            assert(H.count(make_pair(x[i], y[i])) == 0);
            if(!uu(x[i], y[i])) return 0;
            H.insert(make_pair(x[i], y[i]));
        }
        vector<long long> gg;
        long long ans = 1;
        int cnt = 0;
        for(int i = 1; i <= n; i++) {
            if(d[i] == i) {
                gg.push_back(num[i]);
                cnt ++;
                ans = ans * num[i] % MOD;
            }
        }
        if(SZ(gg) == 1) return 1;
        for(int i = 0; i < SZ(gg) - 2; i++) {
            ans = ans * n % MOD;
        }
        return ans;
    }
};

Div I Hard::HamiltonianCircuits
This is also a somewhat classic problem where we want to find a hamiltonian circuit in a tournament graph. There may already exist some resources online about it (see this link for example: https://math.stackexchange.com/questions/1682492/prove-that-every-tournament-contains-at-least-one-hamiltonian-path). This is an harder version of the div2 hard.
Another approach is as follows.
Let’s add the nodes in one by one. We will proceed by induction.
After each step, instead of maintaining a hamiltonian circuit, we will have a list of hamiltonian circuits for each strongly connected components of the nodes 0,1,2,…,i-1. In addition, since this is a tournament graph, the SCCs from a line from left to right, with all SCC edges in the left pointing to the right.
Now, to add node i, we will find the leftmost SCC that i has an edge to and the rightmost SCC that i has an edge to. Call these SCCs indices A and B respectively.
If A > B, then that means we need to insert a new SCC with only node i in between A and B.
If A == B, then that means we need to insert node i into SCC A, we can brute force where to insert i (there must exist such an insertion point because there is an edge to and from i in this component).
If A < B, then we can merge all components from A to B, and also merge their cycles together (we use node i to connect B -> i -> A to make a big cycle). Since we already have cycles in each component, we can rotate each one so that the appropriate node is at the beginning/end.
At the end, if there is only one SCC, we can return the cycle of that component, otherwise, return the empty list.
One step takes O(n) time, so the overall runtime is O(n^2).
Python Code:

class HamiltonianCircuits():
	def findCircuit(self, n, seed, a, b, c, d, e):
		value = seed
		conn = [[False for j in range(n)] for i in range(n)]
		for i in range(n):
			for j in range(i+1, n):
				if value % 1000 <= 250:
					conn[i][j] = True
					conn[j][i] = False
				else:
					conn[j][i] = True
					conn[i][j] = False
				value = (a * value + b) % c
		for x,y in zip(d,e):
			conn[x][y] = True
			conn[y][x] = False
		cycles = []
		for add in range(n):
			g1 = -1
			g2 = len(cycles)
			for ci in range(len(cycles)):
				if any(conn[i][add] for i in cycles[ci]):
					g1 = max(g1, ci)
				if any(conn[add][i] for i in cycles[ci]):
					g2 = min(g2, ci)
			if g1 < g2:
				cycles = cycles[:g2] + [[add]] + cycles[g2:]
				continue
			if g1 == g2:
				for i in range(len(cycles[g1])):
					if conn[cycles[g1][i-1]][add] and conn[add][cycles[g1][i]]:
						cycles[g1] = cycles[g1][:i] + [add] + cycles[g1][i:]
						break
				continue
			a1 = next(i for i in range(len(cycles[g1])) if conn[cycles[g1][i]][add])
			a2 = next(i for i in range(len(cycles[g2])) if conn[add][cycles[g2][i]])
			pref = cycles[:g2]
			suff = cycles[g1+1:]
			cycles[g1] = cycles[g1][a1+1:] + cycles[g1][:a1+1]
			cycles[g2] = cycles[g2][a2:] + cycles[g2][:a2]
			mid = []
			for i in range(g2,g1+1):
				mid.extend(cycles[i])
			mid.append(add)
			cycles = pref + [mid] + suff
		if len(cycles) != 1:
			return []
		return cycles[0]