January 15, 2019 Single Round Match 746 Editorials

SRM 746 was held on Jan 15, 2019. Thanks to majk for the preparing the round and the editorials.

Div2 Easy: KidsInAYard

Phrased mathematically, we are given a system of three modular equations to solve for x:

	x mod 2 = r2
	x mod 3 = r3
	x mod 5 = r5

Let the smallest positive solution be y. Observe that for z = y-30, the set of equations also holds as 30 is divisible by 2,3 and 5. Since we picked y to be the smallest positive solution, it holds z<=0, hence y <= 30.
We can try all possible values up to 30 and see that every input has an answer in this range.

class KidsInAYard {
int howMany(int r2, int r3, int r5) {
		int x = 1;
		while (x%2 != r2 || x%3 != r3 || x%5 != r5) ++x;
	return x;
}
};

For more details on what we just did, and how to find the answer for larger moduli, consult the entry on Chinese remainder theorem.

Div2 Medium: PairProduct

We are given an array A. The task is to find two of its member whose product is exactly p.
There are two cases. Either p=0, and then we can find an answer if and only if the input array contains a zero as well. Alternatively, for each a in A we can find p/a, the number with which a produces p. To find the index of p/a, we use simple map.

class PairProduct {
std::vector  findPair(int n, int a0, int step, long long p) {
	std::map<int, int> I;
	for (int i = 0; i < n; ++i) { I[a0] = i; if (a0 == 0) { if (p == 0) return {i,i}; } else if (p % a0 == 0) { auto it = I.find(p/a0); if (it != I.end()) return {i,it->second};
		}
		a0 += step;
	}
	return {};
}
};

The complexity is O(n log n).

Div2 Hard: FindStringEasy

In this task we are asked to find a string having exactly n palindromic substrings.
We try to guess that there will be solutions of some form, for instance aaa..abbb.baaa.a , where the lengths of the runs of the same character are x,y,z, respectively. The number of palindromes of this arrangement is, provided y>0, equal to x(x+1)/2+y(y+1)/2+z(z+1)/2+min(x,z). We enumerate all triples x,y,z having sum at most 100 and check whether they are solution for given n.
When we run this code for all possible n, we find no solution for n=5 and n=19. Observe that a string of length k has at least k palindromic substrings of length 1. We can use this fact and enumeration of all binary strings of length up to 5 to prove that the case n=5 indeed has no solution.
For n=19, we can find a solution either by hand, or trying four runs of the same character instead of three, to find the solution “aaabbbaab”
Code (by misof):

class FindStringEasy:
string withPalindromicSubstrings(int n) {
if (n == 5) return "";
if (n == 19) return "aaabbbaab";
     		for (int x=1;x<101;++x) {
     			for (int y=0;y<101-x;++y) {
   				int current = x*(x+1)/2 + y*(y+1)/2;
      			if (current == n) return string(x,'a') + string(y,'b');
  				if (current < n && b > 0)
    					for (int z=1; z<101-x-y; ++z)
     						if (current + z*(z+1)/2 + min(x,z) == n)
                           			return string(x,'a') + string(y,'b')
+ string(z,'a');
			}
}
}
}

Div1 Easy: ChangeDistances

In this task we are given graph G and are asked to construct graph H such that d_G(u,v) != d_H(u,v) for all u!=v.
We can simply pick the complement of G as H. Clearly, each pair of vertices u!=v is connected by an edge in exactly one of the graphs, having distance d(u,v) = 1. The distance in the second graph is strictly larger than 1.

class ChangeDistances {
	vector findGraph(vector g) {
		int n = g.size();
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				g[i][j] ^= i!=j;
			}
		}
		return g;
	}
}

The runtime is O(n2).

Div1 Medium: FindStringHard

In this task we are asked to find a string having exactly n antipalindromic substrings, where antipalindrome is a string that differs from its reverse in all positions.
There are many heuristic solutions that work. We cover two of them.

1. Generate string (ab){x}c{y}, where c is a random character, x is integer between 1 and 35 and y is integer between 1 and 30. This approach can generate answers for all inputs in less than a second.
2. Use backtracking to find a solution, returning early when we are over the needed number of antipalindromes. When picking whether to use a or b, try the one that maximises the number of antipalindromes in this prefix.

If your solution is somewhat slower, you can always find all the answers offline and hardcode the solutions.
Below is code for the first approach, minus the code that counts the antipalindromes of a string by brute force.

class FindStringHard {
	string withAntipalindromicSubstrings(int N) {
		String S = "a";
		while (antipalindromes(S) != N) {
			int X = rand()%35;
			int Y = rand()%30;
			S.resize(2*X + Y);
			for (int i = 0; i < X; ++i) { B[2*i] = 'a'; B[2*i+1] = 'b'; }
			for (int i = 0; i < Y; ++i) B[2*X+i] = "ab"[rand()%2];
		}
		return S;
}
}

Div1 Hard: SpaceProbes

In SpaceProbes, we are given two lines a, b and a point P. We are asked to pick A on a, B on b to minimise distance between P and the midpoint of segment A and B.
First case is when the lines a,b are parallel (or identical). In such case the set of all possible centers is clearly a line p parallel and coplanar with a and b equidistant from both of them. The solution is to find point-line distance in 3D. This can be done, for instance, by finding a plane orthogonal to p, going through P, and find its intersection with p.
Otherwise, let the lines a and b be skew. To show what is the set of all midpoints, we first solve the problem in two dimensions.
Let a, b be two lines in a plane intersecting at point T. Pick an arbitrary point P outside of both lines (the case where P lies on one of the lines is trivial). We will construct the triangle ABT, where A lies on a, B lies on b and P is midpoint of segment AB. Observe that TP is a median of the triangle, and the centroid S lies in two thirds of this line segment. Project line a using homothety with coefficient -2 across S to obtain a’. As a’ is parallel with a (property of homothety), it intersects b in a single point called A. It is now easy to construct the needed triangle. Hence, the set of all midpoints coincides with the plane.
Back to the three dimensions, rotate the space so that both a and b are parallel to plane z. This transformation preserves all angles and distances, hence we can solve this instance and then perform the inverse rotation to find solution of the original problem. The z coordinate of all midpoints is now constant and independent of x,y, reducing the problem to two dimensions. Hence, the set of all midpoints coincides with a plane parallel to a and b and equidistant from both. To find the answer, we construct this plane and then return point-plane distance.