161A - Dress'em in Vests!

Consider troopers in the sorted order, as in the input data. One can prove that for the current (minimal) trooper the best choice is the vest with the minimal possible b_j.

So we can solve this problem using “moving pointers” method. The first pointer iterates over troopers and the second one chooses minimal unused vest that b_j - x ≥ a_i.

The complexity of the solution is O(n + m).

Idea: Burunduk1

161B - Discounts

This problem can be solved greedy. Let us have x stools. One can prove that it is always correct to arrange min(k - 1, x) maximal stools into min(k - 1, x) carts one by one. All remaining stools and pencils should be put into remaining empty carts. Finally, we have either zero or one empty cart.

Idea: Burunduk2 and Burunduk1

161C - Abracadabra

Consider the case when the maximal character in the string is in the answer. Then the answer equals min(r₁, r₂) - max(l₁, l₂). Otherwise, we cut both strings around this character (here we might get empty strings) and run the algorithm recursively for every pair of strings we get. One can prove that this solutions works in O(k), where k is the values of the maximal character.

Idea: avm

161D - Distance in Tree

This problem can be solved using dynamic programming. Let us hang the tree making it rooted. For every vertex v of the tree, let us calculate values d[v][lev] (0 ≤ lev ≤ k) — the number of vertices in the subtree, having distance lev to them. Note, that d[v][0] = 0.

Then we calculate the answer. It equals the sum for every vertex v of two values:

• The number of ways of length k, starting in the subtree of v and finishing in v. Obviously, it equals d[v][k].
• The number of ways of length k, starting in the subtree of v and finishing in the subtree of v. This equals the sum for every son u of v the value: .

Accumulate the sum for all vertices and get the solution in O(n·k).

Idea: Burunduk1

161E - Polycarpus the Safecracker

We need to count the number of symmetric matrices with a given first row, where each row is a prime number.

Since the matrix is symmetric, it is determined by its cells above or on the main diagonal. Let's examine all possible values of digits above the main diagonal (at most 10⁶ cases). Now the values of the remaining unknown digits (on the main diagonal) are independent of each other because of each of them affects exactly one row of the matrix. Therefore, it is enough to count independently the number of possible values for each of the digits on the diagonal, multiply them and add received number to answer.

Moreover, it's possible to pre-calculate such numbers for each position of unknown digit and for each collection of known digits.

These observations are enough to pass all the tests.

One could go further, examining each next digit above the main diagonal only if it's row and column can be extended to prime numbers by some digits, unknown at moment of this digit placing. Such a solution allows to find answers for all possible tests in the allowed time, but it wasn't required.

Idea: avm

All the stuff around the problems has been prepared by (in alphabetic order): arseny30, at1, avm, Burunduk1, Burunduk2, burunduk3, Gerald, levlam, MikeMirzayanov

Hello everyone!

It's time for the first round of the VK Cup 2012. Let me remind you that the registration for this round is also required and it's closed five minutes before the start.

The problemset has been developed by various authors from VK, Codeforces and Saratov State University. We worked hard to make this time interesting for competitors and to have the best ones in the next round.

This round will be run according to Codeforces rules: with room assignments, hacks and usual score decrease. It will be rated for you either if you participate in VK Cup or just solve it as a normal round.

Top 700 competitors will advance to the second round immediately. 50 more competitors will advance to the second round via the first unusual rules wildcard round on March 18.

There's one wish for everyone from Burunduk1: “Please, to make the round even more interesting for you, read the statements of ALL problems.”

Good luck and try to win!

Update: congratulations to all competitors with 1712 or higher score: you advance to the second round!

Update2: editorial is available: http://codeforces.me/blog/entry/4097

Update3: Several cheaters have been removed, the results now slightly differ. All participants with 1684 or higher score advance now to Round 2. Everyone else is invited now to the first wildcard round, the last chance to advance.