August 8, 2017 2017 TCO Algorithm Round 3A Editorials

TCO17 Algorithm Round 3A Editorials are now published. Once again thanks to Egor for the editorial and overview of TCO17 Algorithm Round 3A.
2017 TCO Round 3A presented algorithm contestants with the very first opportunity to advance to the finals in Buffalo, NY. Congratulations to those who seized this chance: tourist, W4yneb0t, bcip, scott_wu and -XraY-. They will be joined by the winners of Round 3B and the special wildcard round.
 
2017 TCO Algorithm Round 3A – Division I, Level One  – CoprimeMatrix
In this problem you were given an NxN matrix coprime of Ys and Ns. Is there a such positive integer X that gcd(X + i, X + j) = 1 if and only if coprime[i][j] = ‘Y’?
The basic solution is quite straightforward: for each prime p < N we need to find the remainder of X with respect to p which would be consistent with this matrix. If coprme[i][i + p] = ‘N’ for some p then X mod p = (p – i mod p) mod p. If there is no such i for given p and 2 * p <= N, then the answer is “Impossible”. Now, if we find a remainder for each p there are some X that would have corresponding remainders due to the Chinese remainder theorem. We would then check the table for consistency with this (note that we would not be able to calculate X directly without long arithmetics as it would not fit the 64-bit integer type).
But there are quite a few corner cases – first, if coprime[0][0] = ‘Y’ the only possible X is 1. All other elements on the main diagonal should be N. Also, coprime[i][j] should be equal to coprime[j][i]. Coupled with the fact that samples in this problem were quite weak this lead to quite a brutal challenge phase with only 36.9% of 84 submissions that ended up being correct (and that considering quite high resubmit ratio for this problem as well).
See nika’s solution for reference
2017 TCO Algorithm Round 3A – Division I, Level Two   – MaidensBunraku
In this problem you were given a set of N points and 2 directions. For each point you selected one of 2 directions and drew the ray in that direction. What is the maximal number of regions with finite area you can achieve?
Here we can move points a bit and adjust directions such that those points are all laying in the centers of cells in an NxN square.  No 2 points lay in the same row or column and directions are “right” and “down”. After this it can be easily seen that if there are 2 points A and B, A is to the left and to the bottom of B, then it is never optimal to draw a ray from A down and ray from B right. Using this fact you can use dynamic programming to get O(N^2) solution. Refer to rng_58’s solution for details.
 
2017 TCO Algorithm Round 3A – Division I, Level Three – HiddenRabbits
In his problem you have a tree with N vertices and M rabbits. Each rabbit wants to live in some vertex of the tree (not necessarily distinct) and there are several conditions of the form “given rabbits a and b if we root tree in vertex r least common ancestor of vertices a and b is x.
Let us consider for each rabbit i and vertex j boolean variable s(i, j) – rabbit i lives in subtree with root j. This way we have several conditions on this variables:

• s(i, 0) is true (every rabbit lives in whole tree)
• s(i, j) -> p(i, p[j])
• if j and k is not an ancestor of each other in the tree then !s(i, j) or !s(i, k) is true
• if x is not an ancestor of r, then s(a, x) is true, s(b, x) is true and for each vertex v such that p[v] = x !s(a, v) or !s(b, v) is true
• if x is an ancestor of r (suppose t is the first vertex on path from x to r) then s(a, t) is false, s(b, t) is false, s(a, x) or s(b, x) is true
• and for each vertex v such that p[v] = x !s(a, v) or !s(b, v) is true

These conditions are necessary and sufficient. Hence we reduced our problem to a classic 2-SAT.
For implementation details you can look up tourist’s solution.