Rei's blog

By Rei, 11 years ago, translation, In English

Problem analysis v 0.9.

318A - Even Odds

In this problem we need to understand how exactly numbers from 1 to n rearrange when we write firstly all odd numbers and after them all even numbers. To find out which number stands at position k one needs to find the position where even numbers start and output either the position of the odd number from the first half of the sequence or for the even number from the second half of the sequence.

318B - Strings of Power

In the heavy metal problem one needs to find the number of the substrings in the string S with a given prefix A and given suffix B. If we mark black all the starting positions of the entries of the string A in S, and white all the starting positions of the entries of the string B, then we come to the following problem: count the number of pairs <black position, white position> (in this order). To solve this it is enough to iterate from left to right counting the number of the passed black positions. Meeting black position we increment this number by one, meeting white position we add to the answer the number of pairs with this white position, which is exactly our memorized number of the already passed black positions.

317A - Perfect Pair

318C - Perfect Pair

This problem were more about accuracy then about ideas or coding. It is important to not forget any cases here.

On each step we replace one of the numbers x, y by their sum x + y until the pair becomes m-perfect (id est one of them becomes not lesser than m). It is clear that one sould replace lesser number from the pair x, y. Indeed lets say the pair x1 ≤ y1 dominates the pair x2 ≤ y2, if y1 ≥ y2 and x1 ≥ y2. In this case if one can get m-perfect pair from x2, y2 by certain sequence of actions, then one can get m-perfect pair from x1, y1 by the same or shorter sequence of actions. If x ≤ y, then the pair x + y, y dominates the pair x + y, x. Hence path from x + y, y to m-perfect is not longer than from x + y, x, and we may assume that we choose exactly this pair.

Consider following cases:

  1. x ≤ 0, y ≤ 0 In this case our numbers do not increase in the process. Hence either the pair is alredy m-perfect or it will never be.

  2. x > 0 and y > 0 In this case for each m pair will after several steps become m-perfect. To count precise number of those steps one needs to launch emulation. If x > 0 and y > 0, then pair "grows exponentionaly>> (more formally: easy to show that starting from secnd step sum x + y grows in at least 3 / 2 times each step) and emulation works pretty fast. However in the case x < 0 and y > 0 (or vice versa) pair might change very slowly. Most bright example is x =  - 1018, y = 1. Thus one needs to count number of steps until both numbers becomes positive before launching emulationt. For x < 0 and y > 0 number of those steps is exactly .

317B - Ants

318D - Ants

One may reformulate the problem ass follows. Non-negative integers A(x, y) are placed in the vertices of two-dimensional lattice We may imagine this construction as a function . On each step for each vertex P = (x, y) with A(x, y) ≥ 4 we perform operation φP, which substracts 4 from A(x, y) and adds 1 to A(x, y - 1), A(x, y + 1), A(x - 1, y), A(x + 1, y). We may think that operation φP applies to the whole function A. We need to find values of A after the iterations stops.

Key idea is that operactions φP and φQ for all points P and Q commutes, that is φPQ(A)) = φQP(A)). This means that the order of operations is unimportant. In particular, we may assume that from each given vertex run all possible four-groups of ants and not only one. After this observation one may run full emulation of the process. As an exercise contestants may check that ants will never leave square 200 × 200 with center in the origin 0 with given constraints.

317C - Balance

318E - Balance

In this problem we need to find 2n2 transfusions from initial configuration to the desired one. First of all we propose the following: if in each connected component overall volume of the water in initial configuration is the same as in desired one, then answer exist. We call the vessel ready, if current volume of its water equals desired one. Let us describe solution which is probably easier to code. We will make vessels ready one by one. Consider the pair of non-ready vessels s and t (there is more water in s than desired, and less water in t than desired), such that they are connected by the path P, and if one transfuses d litres from s to t then one of the vessels becomes ready. Now we need to find a way to transfuse d litres by path P from s to t. One may write recursive function pour(s, t, d) for this aim. Let t' stand before t in this path, then function works as follows: transfuses from t' to t as many water as possible (not more than d of course), then calls pour(s, t', d) and on the final step transfuses from t' to t all that left. It is easy to check that all such transfusions are correct. This algorithm makes 2len transfusions on the path of length len, so total number of transfusions is not greater than 2n2.

317D - Game with Powers

For each numner x denote sequence of its powers within [1..n] as Pow(x):

Game proceeds as follows: on each step one player takes still available number x from 1 to n and prohibits whole set Pow(x). Who can't make his turn loses.

This game may be decomposed in the sum of lesser games. Indeed, lets call number x simple (and corresponding sequence Pow(x) simple), if it is not a power of any number y < x. Then: 1. for each there is simple x, such that ; 2. for each simple distinct x and y sets Pow(x) and P(y) do not intersect. Indeed, for a given k there is exactly one simple x such that k is power of x. This may be showed from fundamental theorem of arithmetic: if and d = gcd1, α2, ..., αn), then .

Hence set [1..n] decomposes into primitive sets Pow(x), on each of those Pow(x) game proceeds independetly. Now one may use Sprague–Grundy theory to see that mexx of our game is just xor of all mexx of games on simple Pow(x). For fixed x, if Pow(x) = {x, x2, ..., xs}, then mexx of the game on Pow(x) depends only on s, but not on x. In our case s runs from 1 to 29, mexx for all such s may be directly precalculated. Now it is enough to find numbers q(s) of simple x with a given size of Pow(x) equal to s (actually we are interested in parity of q(s) not in q(s) itself).

Our constraints allows to do it directly: run x from 2 to , if it is not crossed out, determine the size Pow(x) [increment corresponding q(s)], and cross out all numbers from Pow(x).

This cycle finds all simple sequences of length at least 2. Quantity of non-crossed numbers is the number of all simple sequences of length 1. Now it is enough to look at parities of q(s) and xor coressponding mexx.

However one may find all q(s) for . Indeed lets look at the number and sequence {x, x2, x3, x4, ..., xs}. This sequence is not simple iff it is containd in some larger simple sequence. But number of subsequenes of size s in a given sequence of size t > s is easy to find: it is just [t / s]. Recalling that simple sequences do not intersect one gets the reccurent formula:

.

Now it is easy to find all q(s) from q(29) to q(1).

Remark: while coding it is important to remeber simple number x = 1.

317E - Princess and Her Shadow

In this problem princess Vlada should simply catch the Shadow. Here is the idea of a solution. If there is only one tree, then using it as a barrier to the shadow it is not hard to catch the shadow. Similar technique works if Vlada and Shadow are far from the square where all the trees grow. But what can she do in the dark depths of the forest? If there is no path at all between Vlada and Shadow, then there is no way to catch it. Otherwise consider a shortest path from Vlada to the Shadow and make Vlada follow it. This path gives Vlada a queue of the steps that she should perform. Additionaly if shadow moves, then we add her move to the queue (simply speaking Vlada follows the shadow). This is where the algorithmic part ends. Now we state that either Vlada catches the shadow in the desired number of steps, or steps out of the "forest square". To proof this we note that the length of the path between Vlada and Shadow may only decrease. And if it does not decrease long enough, then once in k steps (k is the length of the path) Vlada and Shadow shifts at the same vector over and over, and at some moment leaves the "forest square". Note that if the trees allow our heroes to step out of the "forest square" at the beginning, then we may just get them out from the start. But taking this approach we still need to catch the Shadow in a "labyrinth forest".

Apologies for the delay. There are probably misprints and mistakes here (thousands of them!), please feel free to point them out.

Full text and comments »

  • Vote: I like it
  • +129
  • Vote: I do not like it

By Rei, 14 years ago, translation, In English
Problem C.
Vladimir wins exactly when there is a pie with distance to the border not greater than 4. Indeed if there is such a pie, then Vladimir will move it to the border and then move it around the whole rim. Of course if there would be any chance to throw this pie from the board, Vladimir will use it. If he gets no such chance, then after mentioned moves all border is banned. But it means Vlad made at least 2n + 2m turns, when Vladimir only 2n + 2m - 1 as a maximum. A contradiction. Else, if there is no such pie, then during first 4 turns Vlad would ban sides adjacent to each corner of the board. After that, if some pie comes to the rim he would ban adjacent side (there is no more than one such side) ans so Vladimir will never get the pie.

So solution consists of only one distance check, but, as one may see, it is easy to make mistake.

Full text and comments »

  • Vote: I like it
  • +17
  • Vote: I do not like it

By Rei, 14 years ago, translation, In English
Problem B.
One just needs to calculate all possible answers and find the minimum. For example one may run on a set of numbers, for all pairs of numbers apply next operation to that pair and recursively run on a new set of numbers. When only one number remains, compare it to the already obtained minimum, and change that minimum if  it's needed.

Full text and comments »

  • Vote: I like it
  • +19
  • Vote: I do not like it

By Rei, 14 years ago, translation, In English
Problem A.
This problem is solved by simple emulation. After 2n jumps flea returns to initial position, because 1 + 2 + 3 + ... + 2n = n(2n + 1) is divisible by n. Moreover, after that, jumps would be the same as in the beginning, because 2n is divisible by n. So it is just enough to emulate first 2n jumps.
In fact one may see that it is enough to emulate first n jumps and moreover answer is "YES" exactly when n is power of two. Last gives alternative solution. For example: printf("%s", n&(n-1) : "NO" ? "YES");

Full text and comments »

  • Vote: I like it
  • +14
  • Vote: I do not like it