March CookOff Contest Problem Editorials

EXPCOMM (written by Anton Lunyov)

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

MONTRANS (written by Anton Lunyov)

You just simply need to perform this procedure no more than 10000 times and at each step update the maximal profit and optimal number of times to get it if needed. Also note that after 10000 times we definitely obtain some amount of money that we had before and hence after that we can't obtain better profit than earlier so it follows that for any input data the answer is not greater than 10000. The last sentence of the output specification was added just to make the problem trivial. In fact the maximal answer is less than 200.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

SNAKY (written by Anton Lunyov)

For each cell (r, c) of the grid we can compute the time T[r][c] when the snake makes this cell free. It means that for the next T[r][c]-1 moves this cell will be occupied by the snake and at the move T[r][c] tail will leave it (this cell can be immediately occupied by the head but we don't worry about that). For this just simply model the snake movements that given in the input and mark k-th cell in this sequence by the number k. (First cell is occupied by the tail and we marked it by 1 and really snake will leave it just in one move. Second cell will be free after two moves and so on). Since N, M <= 1000 we can do this using usual two-dimensional array. After that, model the movement of the snake head. If at k-th step the head visits the cell (r, c) then it collides with its body if and only if k < T[r][c]. Indeed, if k < T[r][c] then by definition of T[r][c] it means that the snake body still occupies this cell and collision happens otherwise all is fine. So if at some moment we obtain this inequality then we should output "BODY" and k-1, otherwise snake will collide with the wall. So the overall complexity is O(M N + L + max{M, N}) per test case (we need to clean corresponding two-dimensional array before treatment of the snake movement hence we have M N term, L corresponds to the analyzing of the snake movement and max{M, N} corresponds to the movement of the head.)

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

PALIPALI (written by Anton Lunyov)

Let s be the given string, n is its length and s[i] denotes i-th symbol of s (0 <= i < n). Also we denote by s[i, j) the substring of s from i-th symbol inclusive to j-th symbol not inclusive. Compute for each i the so-called palindrome radius d[i]. Namely d[i] is the maximal number k such that the substring s[i - k, i + k) is a palindrome. This can be done by the elegant Manacher algorithm in O(n) time. Here you can read about it. Also you can use hashes and binary search to find this in O(n log n) time. So now assume that we find numbers d[i] (0 <= i < n). Obviously the substring s[i - k, i+3*k) is beautiful if and only if j <= i + d[i] and d[j] >= 2 * (j - i) where j = i + k. (Since j <= i + d[i] then substring s[i - k, i + k) is a palindrome and since d[j] >= 2*k then s[i - k, i+3*k) is also a palindrome and has the form tt^rtt^r where t = s[i - k, i)). So for each i the number of beautiful substrings of the form s[i - k, i+3*k) is equal to number of those j <= i + d[i] such that 2*j - d[j] <= 2*i (and of course j > i). Let's sort all pairs (2*j - d[j], j) by the usual lexicographical comparator. For each i from 0 to n-1 we at first add all new values of j such that 2*j - d[j] <= 2*i to some data structure T then delete i from T and then add to the answer the number of elements in T that are not greater than i + d[i]. Obviously when we are finding the last quantity, T contains only those values of j such that i < j (since we delete i at each step) and 2*j - d[j] <= 2*i. So the last quantity is number of beautiful substring of the form s[i - k, i+3*k). What is T? We can use Cartesian tree or any balanced binary search tree that support order statistics as T. Also we can use segment tree for sum on the array of numbers from 0 to n-1. Then insertion (deleting) of the element is simply adding (subtraction) of one to (from) the corresponding element of the array and the number of needed beautiful substrings is the sum of values of the corresponding segment of the array. Finally you can use Fenwick tree instead of the segment tree (see author solution). So the overall complexity is O(n log n).

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

GROUPING (written by Anton Lunyov)

At first sort all employees by the numbers c[i] in decreasing order. So we can assume that c[0]>c[1]>...>c[n-1]. If we choose some friendly group i₁, i₂, ..., i_p then the quality of food in the kitchen will be 2^c[i₁]+2^c[i₂]+...+2^c[i_p]. Since all c[i] are different and 2ⁱ > 2^i-1+...+2²+2+1 then comparing friendly groups by food quality is equivalent to the lexicographical comparing.

Hence we can use greedy strategy to find the best friendly group: at each step we must add to the group the employee which compatible with all employees in the group with the largest value of c[i]. We can use several techniques in order to implement this approach efficiently. The simplest way is to loop through all employees and for each employee count the number of compatible with him employees that belong to the current friendly group. If this number coincides with the cardinality of the group then we add him otherwise not.

If we have some friendly group then in order to obtain next friendly group by the value of food quality we need to do the following. Throw away the last employee from the group and starting from the next employee follow the greedy strategy described above (in some cases you can't add any employees after that but it's fine it only means that the next friendly group is obtained by simply throwing away the last employee). Thus the overall complexity is O(n log n + k (n+m) ).

You can view solutions here:

Problem Setter Solution

Problem Tester Solution