Rei's blog

Codeforces Round #188 (analysis)
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 φ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.

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 = 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, 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.

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

Comments Comments (18)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
Thank you for the nice contest and editorial. 
In "Ants" problem, Is there any way to expect the simulation will be converge so fast before we writing brute force code? how to make sure n = 30000 is the worst case?
→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Is there mathematical approach to solve Div1B?

→ Reply
»
11 years ago, # |
← Rev. 5   Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

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

    #include <string.h>
#include <cstdio>
#include <map>
using namespace std;
map<long long ,int>SG;
int DFS(long long state) {
    //printf("%I64d\n",state);getchar();getchar();
    if(state==0) return 0;
    if(SG[state]) return SG[state];
    int len=0;long long tmp=state;
    while(tmp>0) {
        len++;
        tmp>>=1;
    }
    bool cnt[100];memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=len;i++) {
        long long k=(1<<(i-1)),tmp=state;
        while(k<=tmp) {
            tmp&=(((1<<(len+1))-1)^k);//printf("%lld\n",k);
            k<<=i;
		}//printf("%lld\n",tmp);
		if(tmp==state) continue;
        int ret=DFS(tmp);
        cnt[ret]=1;
    }
    for(int i=0;;i++)if(!cnt[i]){
        //printf("%d %d\n",len,i);
        return (SG[state]=i);
    }
}
int main()
{
    for(int I=1;I<=29;I++) {
        printf("%d\n",DFS((long long )((1<<I)-1)));
    }
    return 0;
}
    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hi where can I find the English analysis?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Finally a solution that calculates the MEX values.. Thank you very much!

      → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 Θ(n2) :P

Firstly 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(n2) is sufficient. Let f(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 Θ(n2) at start, so we obtain an upper bound on number of moves.

Now let's prove that Θ(n2) is necessary. Consider a horizontal line y = c and ants above it and let S be the sum of distances from that line of ants above that line. One can easily see that this S doesn'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 least S operations on that line in whole process. One can see that for (K is 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 Θ(n2) operations.

So, summing up, I don't think that setting n to 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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the bound of 200 in problem d- Ants

→ Reply