Back to news

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 ai and aj, i < j and ai < aj, 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 ai.

It can be proved in the same way that suppliers must be processed in order of increasing bj. 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 bj, 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][mask1] to update the value, here mask1 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 st is the closest to u vertex v, which lies on the st path. This vertex can only be one of the following:

 

  • s or t
  • LCA(s, t)
  • LCA(s, u), if it lies on the st path
  • LCA(t, u), if it lies on the st 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 |t1 - t2| < M, where t1 and t2 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

Log in

It.Mail.ru

Forgot password?

Registration

The instruction for password recovery
has been sent to your email