March 31, 2019 Single Round Match 754 Editorials

Single Round Match 754
Saturday, March 30th, 2019

MissingDwarf

Used as: Division Two – Level One:

Value	250
Submission Rate	141 / 155 (90.97%)
Success Rate	126 / 141 (89.36%)
High Score	winterflame for 248.62 points (2 mins 7 secs)
Average Score	214.04 (for 126 correct submissions)

Statement

You’re given \(6\) numbers \(h_1,\dots,h_6\). You need to find smallest number \(h_7\) such that \(h_7 > h_k\) for \(k=1..6\) and mean value of all numbers \(\frac{h_1 + \dots + h_7}{7}\) is integer.

Solution

Find maximum \(h_k\), start with \(h_7\) being equal this number plus one, increase it until mean value becomes integer. You will do at most \(6\) increases, thus running time is \(O(1)\).

int getHeight(vector  otherHeights) {
	int sm = accumulate(begin(otherHeights), end(otherHeights), 0);
	int ans = 1 + *max_element(begin(otherHeights), end(otherHeights));
	while((ans + sm) % 7) {
		ans++;
	}
	return ans;
}

SeventhPowers

Used as: Division Two – Level Two:

Value	500
Submission Rate	114 / 155 (73.55%)
Success Rate	100 / 114 (87.72%)
High Score	ongchuviettel for 486.67 points (4 mins 43 secs)
Average Score	339.35 (for 100 correct submissions)

Statement

Consider integer \(A=a_{n-1}\dots a_1a_0\), You’re given \(B=a_{0}^{7}+a_{1}^{7}+\dots+a_{n-1}^{7}\). Construct any \(A\) which gives such \(B\) having no leading zeroes and length at most \(500\). \(B\) itself is at most \(10^7\).

Solution

One of possible ways to solve the problem is to greedily pick the largest digit \(x\) such that \(x^7\) is less than \(B\), then subtract \(x^7\) from \(B\) and append it to the answer. It may be directly checked that this will provide short enough output for all possible inputs

string reconstructA(int B) {
	string ans;
	int t = 9;
	while(B > 0) {
		while(pow(t, 7) > B) {
			t--;
		}
		ans += '0' + t;
		B -= pow(t, 7);
	}
	return ans;
}

MoreSquares

Used as: Division Two – Level Three:

Value	1000
Submission Rate	20 / 155 (12.90%)
Success Rate	4 / 20 (20.00%)
High Score	kektak for 586.75 points (28 mins 28 secs)
Average Score	500.18 (for 4 correct submissions)

Used as: Division One – Level One:

Value	250
Submission Rate	104 / 120 (86.67%)
Success Rate	56 / 104 (53.85%)
High Score	Egor for 237.29 points (6 mins 38 secs)
Average Score	171.60 (for 56 correct submissions)

Statement

You’re given set of \(N \leq 3000\) points \((x_1, y_1), \dots, (x_N, y_N)\). You have to calculate the number of point \((x,y)\) such that if you add them to the set, the number of quadruples of points which form square will increase.

Solution

If point \((x,y)\) increases the amount of squares among points, there should be two points \((x_i,y_i)\) and \((x_j,y_j)\) among the set forming the diagonal of that square, we can iterate over all such pairs in \(O(N^2)\).
For given pair we can determine that center of the square is at the point \(\frac{(x_i+x_j,y_i+y_j)}{2}\) and two other corners are in positions \(\frac{(x_i+x_j,y_i+y_j) \pm (y_i-y_j,x_j-x_i)}{2}\), thus if one of such points is present in the set and the other is not, you should add the one which is not present to the set of points constituting the answer. Note that you can’t simply increment answer because single point may add several squares and it will be counted multiple times in such a case.

typedef int ftype;
typedef complex point;
#define x real
#define y imag
auto comp = [](const point& a, const point &b) {
	return make_pair(a.x(), a.y()) < make_pair(b.x(), b.y());
};
int countLocations(int N, int SX, int SY, vector  Xprefix, vector  Yprefix) {
	vector X(N), Y(N);
	int L = Xprefix.size();
	for(int i = 0; i < L; i++) {
		X[i] = Xprefix[i];
		Y[i] = Yprefix[i];
	}
	for(int i = L; i < N; i++) {
		X[i] = ( X[i-1] * 47 + 42 ) % SX;
		Y[i] = ( Y[i-1] * 47 + 42 ) % SY;
	}
	set S(comp);
	for(int i = 0; i < N; i++) {
		S.insert(point{X[i], Y[i]});
	}
	set T(comp);
	for(auto it: S) {
		for(auto jt: S) {
			if(it != jt) {
				point dir = jt - it;
				if((dir.x() & 1) != (dir.y() & 1)) {
					continue;
				}
				point kt = it + (dir + point(0, 1) * dir) / 2;
				point lt = it + (dir - point(0, 1) * dir) / 2;
				if(S.count(kt) && !S.count(lt)) {
					T.insert(lt);
				}
			}
		}
	}
	return T.size();
}

OrthogonalProjections

Used as: Division One – Level Two:

Value	600
Submission Rate	15 / 120 (12.50%)
Success Rate	6 / 15 (40.00%)
High Score	Stonefeang for 277.42 points (43 mins 9 secs)
Average Score	260.52 (for 6 correct submissions)

Statement

Consider set of \(N\) distinct points \((x_1,y_1), \dots, (x_N,y_N)\) and a line \(L\). If point \(X\) lies on the line \(L\), the orthogonal projection of \(X\) onto \(L\) is \(X\) itself. Otherwise, the orthogonal projection of \(X\) onto \(L\) is the unique point \(Y\) on \(L\) such that \(XY\) is orthogonal to \(L\).
Suppose you are given a finite sequence \(S\) of points in the plane. Two lines \(L_1\) and \(L_2\) are equivalent if the orthogonal projections of points of \(S\) onto \(L_1\) are in the same order as the projections of points of \(S[latex] onto [latex]L_2\). You have to construct the set of \(N \leq 500\) points having exactly given number \(n \leq 10^5\) of equivalence classes.

Solution

First of all we have to determine how to calculate the number of equivalence classes for given set. Let’s look on two particular points \(X_i\) and \(X_j\). What relative configuration can they have? If the line is orthogonal to \(X_i – X_j\) then they have same projection on it, let’s call this line \(L_0\). Otherwise they lie in one order if line goes counter-clockwise from \(L_0\) and in the other order if it goes clockwise from \(L_0\).
If we consider lines \(L_0\) for all possible pairs of \((X_i, X_j)\), they will split the unit circle in \(2k\) segments in such a way that lines going through same segment have same configuration with respect to given set of \(N\) points. Also each endpoint will have its own configuration different from configurations in segments. It would provide you with \(4k\) configurations, but it also counts inverted configurations which should not be counted, thus the number of configurations will be exactly \(2k\) where \(k\) is the number of distinct \(X_i-X_j\) directions up to \(-1\) multiplier.
Some manual check also tells us that it’s impossible to obtain \(4\) configurations and it’s possible to obtain exactly \(1\) configuration if you use only one point. Otherwise making \(n\) configurations is possible if and only if \(n\) is even. Let’s consider one of possible explicit constructions to obtain \(n\) configurations. Let \(t = \lfloor \sqrt{n} \rfloor\), begin with \(t\) points \((0,0), (0,1), \dots, (0,t-1)\). It will initialize our number of directions with \(1\). Now if we add arbitrary point \((x,y)\) it will give us another \(t\) directions. To fairly control number of new directions we will add points \((1,0), (1,t),(1,2t),\dots,(1,kt)\), so with each new point we will have exactly \(t\) new directions. But for final point you will have to add some number \(x\) which is less or equal to \(t\). It can be done by placing point \((1,(k-1)t+x)\) instead of \(kt\).
For example, look on the following diagram:

1. \(A-B-C\) and \(D-E-F\) lie on same lines having pairwise direction \((0,1)\).
2. \(DC,DB,DA\) have directions \((-5,2),(-5,1),(-5,0)\) respectively.
3. \(EA,EB,EC\) have directions \((-5,-1),(-5,-2),(-5,-3)\) respectively.
4. \(FC,FB,FA\) have directions \((-5,-3),(-5,-4),(-5,-5)\) respectively.

Note that because we took \(F\) to be \(2\) points above \(E\) instead of \(3\), exactly one direction to set of points \(\{A,B,C\}\) was repeated. This solution works in \(O(\sqrt n)\).

vector  generate(int n) {
	if(n == 1) {
		return {0, 0};
	} else if(n == 2) {
		return {0, 0, 1, 1};
	} else if(n == 4 || n % 2 == 1) {
		return {};
	} else {
		n /= 2;
		vector ans;
		int t = 1;
		while((t + 1) * (t + 1) < n) {
			t++;
		}
		for(int i = 0; i < t; i++) {
			ans.insert(end(ans), {0, i});
		}
		int cur = 0;
		ans.insert(end(ans), {1, 0});
		n -= 1 + t;
		while(n) {
			int step = min(n, t);
			cur += step;
			n -= step;
			ans.insert(end(ans), {1, cur});
		}
		return ans;
	}
}

RestoreDrawing

Used as: Division One - Level Three:

Value	900
Submission Rate	5 / 120 (4.17%)
Success Rate	1 / 5 (20.00%)
High Score	tourist for 521.02 points (29 mins 9 secs)
Average Score	521.02 (for 1 correct submission)

Statement

You have to construct \(N \times M\) grid \(N, M \leq 100\) such that sizes of its 4-connected components are \(a_1,\dots,a_n\) and sizes of its 8-connected components are \(b_1,\dots,b_m\). Where for arrays holds \(n,m \leq 20\) and \(a_1 + \dots + a_n \leq 1500\).

Solution

Note that you may take arbitrary set of \(4\)-connected components, join it via diagonals and obtain single \(8\)-connected component. Thus the whole solution splits in two parts: splitting sizes of \(8\)-connected components into sizes of \(4\)-connected components and constructing the answer.
First part is an instance of bin packing problem. Author's approach to solve it is to fix some order on set \(b\) and calculate \(dp[mask]\) which is equal to \(1\) if it's possible to construct prefix of \(b\) (maybe with some remainder) such that it splits on two distinct subsets on \(b_1,b_1+b_2,b_1+b_2+b_3\) and so on, it may be calculated in \(2^n \times n\).
Tester approach is to use recursive function split(L, R, mask) which tries to split segment \(b_L, b_{L+1},\dots, b_{R-1}\) using only items presented in \(mask\). To do this you split \([L,R)\) into \([L,M)\) and \([M,R)\), iterate over all submasks of \(mask\) and try to split subsegment \([L,M)\) with such submask. If it was possible, you also try to split \([M,R)\) with its complement. It's hard to estimate working time of such solution but rough upper bound is something like \(3^n\) which, obviously, always way less on practice.
After you calculated possible splitting, you should compose \(4\)-connected components with such sizes and make them into \(8\)-connected components. One of possible ways to do it is to split the whole table by vertical line in half and fill 4-connected components alternatively, aligning them to the center. Another possible way is by using following pattern alternatively:

Thus each 4-connected component is either single `#` or it is preceded and succeeded by single `#`, so that those single `#`'s maintain connection between 4-components into 8-component. Please feel free to inspect the code for better understanding.

const int maxn = 1 << 20;
int sum[maxn];
template
vector split(T from, T to, int mask) {
	if(sum[mask] != accumulate(from, to, 0)) {
		return {};
	} else if(to - from == 1) {
		return {mask};
	} else {
		T mid = from + (to - from) / 2;
		for(int msk = mask; msk; msk = (msk - 1) & mask) {
			auto A = split(from, mid, msk);
			if(!A.empty()) {
				auto B = split(mid, to, mask ^ msk);
				if(!B.empty()) {
					A.insert(end(A), all(B));
					return A;
				}
			}
		}
		return {};
	}
}
vector  restore(vector  sizes4, vector  sizes8) {
	sort(begin(sizes4), end(sizes4));
	sort(begin(sizes8), end(sizes8));
	int n = sizes4.size();
	int mask_sz = 1 << n;
	for(int i = 0; i < n; i++) {
		sum[1 << i] = sizes4[i];
	}
	for(int i = 1; i < mask_sz; i++) {
		int j = i & (i - 1);
		sum[i] = sum[j] + sum[i ^ j];
	}
	auto msks = split(begin(sizes8), end(sizes8), mask_sz - 1);
	if(msks.empty()) {
		return {};
	} else {
		const int MX = 100;
		vector ans(MX, string(MX, '.'));
		int h = 0;
		for(size_t i = 0; i < sizes8.size(); i++) {
			int cur = 0;
			for(size_t j = 0; j < sizes4.size(); j++) {
				if((msks[i] >> j) & 1) {
					ans[cur] = '#';
					h++;
					if(sizes4[j] == 1) {
						cur ^= 1;
					} else {
						int t = cur;
						for(int k = 2; k < sizes4[j]; k++) {
							if(t >= MX) {
								t = cur;
								h++;
							}
							ans[t++] = '#';
						}
						if(ans[cur] == '#') {
							h++;
						}
						ans[cur] = '#';
						cur ^= 1;
					}
				}
			}
			h++;
		}
		return ans;
	}
}

By adamant

Topcoder Member