Russian Code Cup Qual 1 — Editorial

Правка en1, от RussianCodeCup, 2017-04-02 21:05:19

A. Martian Volleyball

First note that in order to end the game as soon as possible only the currently leading team must get points.

Consider the condition that one of the teams wins. It must score at least k points and have at least 2 points advantage.

So the answer is max(k, min(x, y) + 2) - max(x, y).

B. Painting the Wall

First note that if the maximal length of the continuous segment is L, at least L colors are needed to paint the wall. On the other side L colors is always enough.

Consider a square L × L, fill the first line with integers from 1 to L, fill the following lines with all its possible circular shifts. Use these squares to cover the given wall rectangle like this (L = 4):

1 2 3 4 1 2 3 4 1 2

2 3 4 1 2 3 4 1 2 3

3 4 1 2 3 4 1 2 3 4

...

Now each vertical and horizontal segment of length L or less has all tiles of different colors. All that is left is to bring back the lamps.

C. Magic Artifact

Let us denote advantage that Maxim gets if he finds artifact as ci, so ci = ai - bi.

Let Maxim first complete levels in order 1, 2, ..., n. If he finds the artifact at the i-th level, the time he needs to complete the game is equal to bj plus c1 + ... + ci. So the expected time of completing the game is:

b1 + ... + bn + p1·c1 + p2·(c1 + c2) + ... + pn·(c1 + ... + cn).

b1 + ... + bn doesn't depend on level order, so let us try to make the rest as small as possible. Expanding the sums, we get sum of all ci·pk for such i, k that i ≤ k.

Let us now swap levels i and i + 1 in our order. For the given i among ci·pk terms only the one equal to ci·pi + 1 changes — it is replaced with ci + 1·pi. If the order was optimal, it must be ci·pi + 1 ≤ ci + 1·pi, in the other case it was optimal to swap them and get a better answer. Transform this to:

ci / pi ≤ ci + 1 / pi + 1.

In the optimal answer for all i from 1 to n - 1 this inequality must be satisfied. Therefore it is optimal to sort levels according to the key ci / pi. Note that if pi = 0, you may consider ci / pi = ∞.

Sorting according to the key ci / pi should be done carefully. If the fractions are compared using floating-point division, the case ci = pi = 0 will lead to error because 0 / 0 = NaN. If the fractions are compared using the comparator ci·pk < ck·pi, the case ci = pi = 0 will also lead to error because the result of that comparison will always be false. That means that levels with ci = pi = 0 should be handled separately. Such levels can be completed at any time because they do not affect the result besides fixed terms bi. For example, they can be placed at the end.

After sorting the desired expected value can be found using the formula above, use prefix sums for ci to get it fast.

D. Memory Manager

First for each query qi let us find goi — the minimal j, such that among qj, qj + 1, ..., qi there are at most k different blocks — that would mean that it is possible to place pointers before the j-th query in such way that queries j, j + 1, ..., i are performed immediately. This can be made in O(sum(|qi|)), using, for example, two pointers.

Now let us use dynamic programming, denote as dpi the minimal time needed to perform the first i queries. If goi = 0 then dpi = 0. If the equation is not satisfied, dpi = minj = goi..i(dpj - 1 + sj) — we choose the query j to perform the pointer movement before. Since values goi do not descend, this value can be maintained using either std::set of dpj - 1 + sj, or queue with minimum query support.

E. LISA

First let us consider the problem for given two strings: to solve it calculate the number of occurrences of each letter in the first string, the number of occurrences of each letter in the second string, not including the first letter of the first string and the last letter of the second string, that must be used any way. Now the answer is the product of string lengths, decreased by the sum of values cnt1[letter] * cnt2[letter] for each letter. Let us leave proof as an exercise, such problem was at Northern Subregional Contest of NEERC 2015 http://neerc.ifmo.ru/archive/2015/northern/north-2015-statements.pdf, Problem C. Unlimited participants could solve this problem at Three Quaterfinals Cup.

For n strings similar ideas can be used. Put all strings to a prefix trie, all strings to a suffix trie, the total number of ways to get a string is the product of the number of vertices in these tries. What we need to subtract is similar product of number of occurrences of letters in tries, first/last letters of each word must not be considered.

Now we need to answer segment queries. Let us make sqrt-decomposition, divide all strings to groups based on sum of their lengths. Let us greedily add strings to a group until their sum of lengths is more than sqrt(total sum of lengths). Note that the last string can have a big length.

Now use Mo's algorithm, sort queries using the block of the left end as a key, move right end only forward between left end block changes. To add/remove a string to a trie one must maintain the number of active vertices in a trie subtree for each vertex, and the number of entries of letters to a trie.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский RussianCodeCup 2017-04-02 21:05:19 8409 Initial revision for English translation (published)
ru1 Русский RussianCodeCup 2017-04-02 21:04:31 9314 Первая редакция (сохранено в черновиках)