# Russian Code Cup 2016 — 2nd qualification Round — Short Editorial

## A. Peter and the Textbook

This is standard "do what is asked" problem. Let's store an array *isDeleted* of size *n*, where *isDeleted*[*i*] means whether page *i* was already torn away. To process the first type of query assign *isDeleted*[*i*] and *isDeleted*[*n* - *i* + 1] to false, to process the second type of query find the index of the *p*-th true value in the array.

Time complexity: *O*(*t*·*q*·*n*).

## B. Gregory and Bank

The solution is greedy. Fix any arrangement of clients and suppliers, give numbers to clients in order they are processed, give numbers to suppliers in order they are processed.

Let there be two clients such that their amounts are *a*_{i} and *a*_{j}, *i* < *j* and *a*_{i} < *a*_{j}, where *i* and *j* are their indexes in which. If we swap them, the same suppliers can still be satisfied, the amount of money on Gregory's account only increases between the moments he gets money from the *i*-th and from the *j*-th client. Therefore it is optimal to process clients in order of decreasing *a*_{i}.

It can be proved in the same way that suppliers must be processed in order of increasing *b*_{j}. But there is a trick, if we don't have enough money to process the current supplier, we don't skip him, but rather say that we would not send money to the supplier with the greatest available *b*_{j}, and continue modelling, trying to satisfy the current supplier again when we meet "-".

## C. Name Generator

If the length of the given string is at least *k*(*k* + 1) / 2, it is always possible to divide it into *k* different strings. To do this, take its substrings of length 1, 2, ..., *k* - 1 and *n* - *k*(*k* - 1) / 2. Since *k* ≤ 5, that means that it is possible to create the required division for all string of length at least 15. For shorter strings we can just iterate over all possible divisions to *k* parts and check if it is correct.

## D. T-shirts

To solve this problem use dynamic programming with t-shirt subset as a part of the state. Let *dp*[*i*][*mask*] denote the optimal number of t-shirt that the *i*-th participant can get if it's his turn and he has the set of t-shirts available that correspond to 1-bits in *mask*. To find the value, iterate over t-shirts and try to remove any one. Use *dp*[(*i* + 1)%3][*mask*1] to update the value, here *mask*1 is obtained from *mask* by zeroing the corresponding bit.

## E. Bridge testing

We'll process all queries independently. First, find the intersection of these two paths and discard everything else.

How to find an intersection of 2 paths? Let's "project" each endpoint of second path on the first path. Projection of vertex *u* on path *s*→*t* is the closest to *u* vertex *v*, which lies on the *s*→*t* path. This vertex can only be one of the following:

*s*or*t**LCA*(*s*,*t*)*LCA*(*s*,*u*), if it lies on the*s*→*t*path*LCA*(*t*,*u*), if it lies on the*s*→*t*path

Path between these two projections will be the intersection of two paths, let's call it *s*'→*t*'

After we find the intersection, there are two cases:

- Testers move in different directions. In this case we can find time, when both testers are in the same location (note that this time might not be an integer). After that just check that this moment in time corresponds to an edge and not to a vertex.
- Testers move in the same direction. In this case it's possible to prove that if two testers were on the same edge at some moment, then it's also true for the maximum edge on that path. If the length of the maximum edge on
*s*'→*t*' is equal to*M*, then output «YES» if and only if |*t*_{1}-*t*_{2}| <*M*, where*t*_{1}and*t*_{2}are the starting times.

The solution above assumed that you are able to find LCA, maximum edge on path and distance between two vertices in a tree. All this can be implemented using jump pointers technique in *O*((*n* + *q*)*logn*) time and *O*(*nlogn*) space.

## More news

- Solution of the final round of RCC2016 The final round of RCC2016 is over! We congratulate the winners! Here you can find solutions for the final tasks. 18.09.2016
- Russian Code Cup 2016 — Elimination Round — Short Editorial 17.06.2016