Codechef January Cook-Off 2019 will be on Sunday 20, 11:00 PET. See you in the ranklist!
Congrats to the winners!
Div 1:
Div 2:
Hints for some of the problems:
ADAMTR
Every element can be at A[i][j] or A[j][i], construct a logic expression of n variables (one per each row) and solve with 2sat
ADAFUN
Add the numbers to a trie, and calculate the following dps: W(u) = W function if we consider only the numbers that are leafs of u, R(u) = the element that gets unmatched after applying the algorithm if we consider only the numbers that are leafs of u. Using this dps and iterating over the trie is possible to find the W function after removing each leaf.
ADAPWNS
Find the distances between each pair of pawns, performing one operation means decreasing one distance and increasing another. The grundy number of the game is the xor sum of distances of even index looking from right to left.
ADAROKS
Since the number of cells is 1e3, then there should be a dimension of size <=31. Let's suppose that the number of rows is smallest than the number of columns. Rooks cover horizontal and vertical directions. After placing rooks no king should be attacked, so the number of rows covered is at most 16. Brute force the rows covered (2^16 possibilities). Now we have to find the minimum number of columns to separate all kings. This is equivalent to finding the minimum number of lines that cuts a given set of intervals.