Problem analysis v 0.9.

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.

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.

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 *x*_{1} ≤ *y*_{1} *dominates* the pair *x*_{2} ≤ *y*_{2}, if *y*_{1} ≥ *y*_{2} and *x*_{1} ≥ *y*_{2}. In this case if one can get *m*-perfect pair from *x*_{2}, *y*_{2} by certain sequence of actions, then one can get *m*-perfect pair from *x*_{1}, *y*_{1} 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:

*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.*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*= - 10^{18},*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 .

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 φ_{P}(φ_{Q}(*A*)) = φ_{Q}(φ_{P}(*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.

In this problem we need to find 2*n*^{2} 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 2*len* transfusions on the path of length *len*, so total number of transfusions is not greater than 2*n*^{2}.

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* = *gcd*(α_{1}, α_{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*, *x*^{2}, ..., *x*^{s}}, 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*, *x*^{2}, *x*^{3}, *x*^{4}, ..., *x*^{s}}. 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.

you can consider the case of (x,0) with maximum x. Apparently x<= log(4,n) . and general case (x',y') the x' s and y' s won't be larger than biggest x in (x,0)

That is not true. x can go upto 200 in fact, and 4^200 is much bigger than 20,000. The log4n bound doesnt hold because the 'distributed' ants can came back to the central axis, so its not always decreasing.

Can you illustrate how you were able to come to that bound of 200?

Honestly, during the contest, I coded the solution then ran it for 30,000, found the bound and then set it in the code. It wasn't 200, higher.

Even in the tutorial I found the bound to be 200 but when I checked some solutions there are people who have got it with just 140X140 square.

Is there mathematical approach to solve Div1B?

In "Ants" my simulation ends in 300ms, but 700ms is not enough for reading/writing. [edit: query counter used to be short] I rack a disciprine

In 317D - Game with Powers, it's there any non-math method to print the table q(s)?

Oh ,I think I solve it! Thanks for the helping of ydc!

Hi where can I find the English analysis?

You can change the language to English by click the flag at the top right of the current page..

Can someone please explain how to compute q(s) efficiently? Is it possible to compute within 1s (Total number of states is 10^9) ?

Yes, it is possible, because not all states are reachable. To be more precise, the number of reachable states is 711457. Also, hash table makes it possible to quickly process them. For example: 3898005

I think problem ``balance'' admits an solution with less than 0.5*n*n steps.

We only need to consider the following case: All the vessels are connected with eactly n-1 roads, and are formed into a tree.

Then, we can first pick a leaf vessel and make it balance, and then reduce it to a problem with n-1 vessels which are still a tree.

For making a leaf balance, we can do it in no more than n-1 steps.

So total steps is no more than (n-1) + (n — 2) + .. 1, which is no more than half of n^2.

You're right.I implemented the same idea and it took AC and I think it is easier :)

I can't understand why this code is givin me the WA. I've tryed everything and i dont get it ! Can anyone explain me ?

OK, so I will bring this one once again...

I started writing that post going to ask you why simulation in B runs in a reasonable time. Actually, while writing that I proved that it runs in Θ(

n^{2}) :PFirstly let's observe that ants won't get out of square with side , it's pretty easy to show, denote that side by

k.Firstly let's prove that

O(n^{2}) is sufficient. Letf(x,y) = (k- |x|)^{2}+ (k- |y|)^{2}. One can easily see that sum of values of that functions summed over points with ants decreases after each operation. Moreover this sum takes only positive integer values and is equal to Θ(n^{2}) at start, so we obtain an upper bound on number of moves.Now let's prove that Θ(

n^{2}) is necessary. Consider a horizontal liney=cand ants above it and letSbe the sum of distances from that line of ants above that line. One can easily see that thisSdoesn't change when we perform an operation strictly above or strictly under our line and increases by 1 when doing operation on that line, so we have to perforrm at leastSoperations on that line in whole process. One can see that for (Kis some sufficiently large constant, let it be 10, playing with exact values is not needed here) we have , so summing up we will obtain, that we have to perform at least Θ(n^{2}) operations.So, summing up, I don't think that setting

nto 30000 was a good idea. Maybe it has a little constant, but some contestants won't be afraid of bounding the number of moves (as I proved, fully understandable anxiety!) and in result won't code that. I should also mention that solution may be more clever and won't perform operations one by one, if there are for example 100 ants in a cell at the moment, because we can perform 25 operations at once, but for now I can't estimate that thing.For Div 1 problem A Perfect Pair, how do you prove mathematically the statement that if a pair

x_{1},y_{1}dominatesx_{2},y_{2}then it reachesmin equal or lesser steps thanx_{2},y_{2}?:D