Codeforces Round #328 Problem Analysis

Revision en2, by Morphy, 2015-10-31 17:46:17

Problem A. PawnChess

Player A wins if the distance of his nearest pawn to the top of the board is less than or equal to the distance of the Player’s B nearest pawn to the bottom of the board (Note that you should only consider pawns that are not blocked by another pawns).

Problem B. The monster and the squirrel

After drawing the rays from the first vertex (n - 2) triangles are formed. The subsequent rays will generate independently sub-regions in these triangles. Let's analyse the triangle determined by vertices 1, i, i + 1, after drawing the rays from vertex i and (i + 1) the triangle will be divided into (n - i) + (i - 2) = n - 2 regions. Therefore the total number of convex regions is (n - 2)2

If the squirrel starts from the region that have 1 as a vertex, then she can go through each region of triangle (1, i, i + 1) once. That implies that the squirrel can collect all the walnuts in (n - 2)2 jumps.

Problem C. The Big Race

Let D be the length of the racetrack, Since both athletes should tie

Unable to parse markup [type=CF_TEX]

. Let M = lcm(B, W), then D = k·M + r None of the athletes should give one step further, therefore r ≤ min{B - 1, W - 1, T} = X. D must be greater than 0 and less than or equal to T so  - r / M < k ≤ (T - r) / M. For r=0, the number of valid racetracks is floor(T / M), and for r > 0 the number of racetracks is floor((T - r) / M) + 1. Iterating over all possible r, we can count the number of racetracks in which Willman and Bolt ties: Note that floor((T - r) / M) = v ≤ ftrightarrow T - v·M - M < r ≤ T - v·M. That means that floor((T - r) / M) = v for exactly M values of r. We can count the number of values of r in which floor((T - r) / M) = floor((T - 0) / M) = v1, and the values of r in which floor((T - r) / M) = floor((T - X) / M) = v2. Each of the remaining values v_1-1, v_1-2,...,v_2+1 will appear exactly M times.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English Morphy 2015-10-31 22:14:55 0 (published)
en9 English Morphy 2015-10-31 20:14:24 382
en8 English Morphy 2015-10-31 18:09:29 11
en7 English Morphy 2015-10-31 18:07:33 215
en6 English Morphy 2015-10-31 18:03:52 27
en5 English Morphy 2015-10-31 17:58:40 1545
en4 English Morphy 2015-10-31 17:52:13 49
en3 English Morphy 2015-10-31 17:49:51 1201
en2 English Morphy 2015-10-31 17:46:17 1189
en1 English Morphy 2015-10-31 17:33:12 753 Initial revision (saved to drafts)