Dmitry_Egorov's blog

By Dmitry_Egorov, 13 years ago, translation, In English

I am sorry for mistakes in English and I will be glad if you tell me about them.

168A - Wizards and Demonstration Аuthor PavelKunyavskiy.

In this task, it was necessary to write exactly what has been described in statement. In particular, it was necessary to have people, who come to the meeting. For this it was necessary to create clones.

168B - Wizards and Minimal Spell Аuthor PavelKunyavskiy.

In this problem you had to write exactly what has been described in statment too. Read lines one by one. Also keep the last block of lines that are not amplyfying. If the next line is amplyfying (which can be checked by linear search), we print the last block, if any, and the line itself. Otherwise, remove all spaces from the string and add to the last block. It only remains to distinguish between an empty block and a block of empty lines.

167A - Wizards and Trolleybuses Аuthor Alex-Gran.

This was the first problem where you had a little bit away from translating statements to a programming language. Because acceleration trolleybuses are all the same and they can slow down immediately, the answer for the next trolleybus is the maximum of the time when it would come if it were not to stop when he reach the rest trolleybuses which was traveling in front of him and the arrival time of the previous trolleybus.

It remains only to calculate the arrival time of each trolleybus if ignore others. Here, the easiest way to analyze two cases. If , then trolley should accelerate as long as it can and the answer is equal to . Otherwise the trolley should accelerate all the time and the answer is equal to .

167B - Wizards and Huge Prize Author PavelKunyavskiy.

This problem can be solved using dynamic programming.

Let d[i][j][m] — the probability we won j of first i days and get bags total capacity of m. For convenience, we assume that the bag is also a prize and the prize is a bag of capacity 0. To do that, retaining a task we must add 1 to all a[i]. Then from d[i][j][m] we can go to the d[i+1][j+1][m+a[i]] with probability p[i]/100, and to d[i+1][j][m] with probability 1-p[i]/100. The answer will be the sum of d[n+1][j][m] for all j,m such that L ≤ j ≤ m + k. This solution works for 2004, and do not fit into the time limit.

It remains to note that if we have over 200 places for prizes, it does not matter how many exactly. So we need to calculate states with m ≤ 200 and now solution works for 2003.

167C - Wizards and Numbers Author Alex-Gran.

Consider the position (a, b). Let a < b. From this there is a move to . Recursively check if this position is a winning or a losing. If it is losing, then (a, b) exactly winning. Otherwise, no one will take the remainder. So everyone will subtract from larger number nonnegative degree of smaller. Then the left to learn to solve such problem. You can subtract the nonnegative powers of a from x, and player who cannot move losses. And solve it for . This problem can be solved as follows. If a is odd, then all odd number are wining. In other all the numbers, giving an odd residue modulo a+1 or -1 residue on the same module are wining. This can be easily proved by induction.

167D - Wizards and Roads Author PavelKunyavskiy.

This was the first really hard problem in the contest. One of the challenges was to understand the statement. I hope that we had written the statement as clear as it possible in this problem.

Consider this graph. In particular, we consider more closely the point with the largest y.

1) It is connected with the highest points on the left and right of it.

2) It is not connected to all other points.

3) It is inside all corners on points from different sides of it.

All three of these properties are seen quite clearly in the pictures.

So,

1) Building roads on the left and right sides are independent.

2) The graph is a tree.

Once a graph is a tree, the maximum matching in it can be found greedy, or with a simple dynamic. But it works in linear time, which clearly is not enough to answer all of 105 queries.

But this is not just a tree! Those who know what it is probably already noticed, that it is Cartesian tree (also known as treep). This allows to get a tree for the subsegments in time which is O(h), counting all the necessary dynamics, where h is the height of the tree.

Well, since the city built at random points (the method for the construction of cities guarantees this), the height of the tree h = O(K + logN).

167E - Wizards and Bets Author Dmitry_Egorov.

This task was about the pathes from the sources to sinks. For this pathes there was a condition which made them dependent — they should not interfere at vertexes. But in any combinatorics is much easier when everything is independent. So we should try to get rid of the condition of the absence of crossings at the vertices. It is very easy — just forget about it. Lets understand why the answer will not change: Suppose that a certain set of ways in which the two paths intersect. We show that taking into account this way, we at the same time take into account an another with the opposite sign. To do this, change the endings for paths that intersect. The signum of the permutation in this case has changed, so this set of paths is taken into account with the opposite sign and their sum is 0.

How can it helps us? If we fix the permutation, the number of sets of paths that it corresponds well to the product of the number of paths for each pair of corresponding source and sink.

Suppose that from the i-th source in the j-th sink there are cntij paths. This value can be calculated by depth-first-search and simple dynamic.

Then the answer is

. This value is called the determinant of matrix cnt, which can be calculated using Gauss method in O(S3) time where S is the number of sinks and sources.

And we had to remember about isolated vertexes. Deleting one of them either do not change the answer or multiply the answer by -1.

It remains to see that after deleting all isolated vertexes , and 3003 fine fits into TL.

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

| Write comment?
»
13 years ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

Would you please submit writers' solutions on Codeforces? So we can learn from the code.

»
13 years ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

In B-DIV-1, Those who missed min(200, now + a[i]) and used now + a[i], and got WA on test-27, minus this post.

»
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Div2 B, Wrong answer on test 20

Checker Log wrong answer Eoln expected, EOF found(line 1575,character 0)

What does it mean?

  • »
    »
    13 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    You need EOLN( i.e "\n"), and maybe text after it, but your answer is ended

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

    Maybe you print less lines than needed

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

    Probably that you are not outputting the last end of line character under some conditions.

  • »
    »
    13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks all. Got it.

    I used in.hasNext() before. Once I changed it to in.hasNextLine(), it passed.

    Not very sure about the difference for this test case.

»
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it

168A, it was necessary not to forget avoid division by 0, when Y = 0, you should correct the post, because the problem statement says Y >= 1

»
13 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

In Problem B of Div 1, why this case has the right answer of 0.93 not 1.0 ?

1 0 0

7

-1

In my opinion, we can always perform well in 0 round whatever the result of the first tour is, is that correct ? Thanks!

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

    During the contest my opinion is same with yours. But now I understand .In this problem ,the one must play all the tours. then at all , if he won at least l and he can take all prices back home ,it will be consider perfect. So in this case , if he won he can't take the price home so isn't perfect, But if he lost , it will be consider perfect...

    • »
      »
      »
      13 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks for your comments. However, I still have a silly question. If we only consider perfect win, why the sample input

      3 1 0

      10 20 30

      -1 -1 2

      gives 0.3? The only valid way is to lose the first two rounds and win the last one, of which the probability is 0.9 * 0.8 * 0.3 ?
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In that case last round's award — bag of size 2 compensates first two rounds, so if you win in the last round you can do whatever you want on first two, because now you have bag which can carry all other awards.

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

        I approached the problem the same way you did — I assumed that I can carry a "huge prize" after a tour win only if I have room in bags for it at that point. I got 0.216 for that case as well.

        The worst part is that I tried to fix my code to produce 0.3 still maintaining the same assumption. It took me a while to realize that all it matters is to have enough room in bags after all tours.

        Now when I read the statement I am not sure how I misunderstood it, but a lot of other people did — maybe the explanation of the sample should have been a bit more verbose.

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

          Exactly! I always think that I should be able to take all the prize home right after each round... Thank you!

»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can somebody throw more light on solution for 167C - Wizards and Numbers as to how one obtains the relation to solve the subproblem of subtracting a non-negative degree of smaller number from the larger one?

  • »
    »
    13 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Let's say the larger number is B, the smaller one is A. If A is odd, the case is pretty simple -- after each turn B % 2 changes, so we win if and only if B%2 = 0.

    If A is even, we win if B % (A+1) is even. To prove it we need to prove that each winning state has a move to a losing state, and that any move from the losing state only goes to a winning state.

    If B % (A+1) is even, we can always make it odd by subtracting one, if B % (A+1) is not zero, or by subtracting A, if it is zero. That proves that from every winning state there's a move into a losing state.

    If B % (A+1) is odd, any turn will make it odd. This can be proven by induction: If you subtract A^0=1, B % (A+1) will obviously become even. Let's say we have proven that subtracting A^k changes oddness. Since subtracting A^k * (A+1) obviously doesn't change oddness (since it is divisible by A+1), subtracting A^(k+1) = A^k * (A+1) — A^k does change it. That proves that from any losing state you can only move to a winning state.

    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks,I got that..,but I am still confused as the two moves(b->bmoda && b-a^k) are being taken independently to solve the problem.I mean after changing b->bmoda one can take b->b-a^k so why is that not being considered?

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

      Actually you can prove that every turn B % (A+1) must change odd/even, because you can only take A^k for some k>=0, and it is A^k = (A+1 -1)^k = p*(A+1) + (-1)^k which is +1 or -1 when mod (A+1). In the end it is zero, so you win iff B % (A+1) is even. See rng_58's solution.

      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        +/-1 in general doesn't change odd/even for B%(A+1), if A is even. If B%(A+1) = 0, then (B-1)%(A+1) = A -- oddness doesn't change.

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

          thanks for pointing the error. The statement should read: let m = B % (A+1) if m is even, then there is a move that will make it to odd else m is odd, then every move will make it even

          Proof: If m is even, then either m=0 or m>0 for m=0, we can take a move of A, then m become B-A = 1 mod (A+1) it is odd for m>0, we can take a move of 1, then m become B-1 = even-1 = odd mod (A+1)

          If m is odd, then any move is of the form A^k = (A+1 -1)^k = (-1)^k mod (A+1) So after the move m become odd — (-1)^k = even mod (A+1)

    • »
      »
      »
      13 years ago, # ^ |
      Rev. 7   Vote: I like it 0 Vote: I do not like it

      If %(a+1),I can get accepted but what's wrong with %(a-1) (a-1>1) ? It get wa when test b=449843221913123719 a=16 (test 3)

      Let's define function F[x]={0,1}: when stat x can make first win F[x]=0,else F[x]=1;

      if F[x]=0,there must be a k (k>=0&&b-a^k>=0) makes F[x-a^k]=1;

      if F[x]=1,for all k (k>=0&&b-a^k>=0) F[x-a^k]=0;

      When F[x]=(x%(a-1))&1.

      if F[x]=0. x%(a-1) must be a even,and for all k:

      (x-a^k)%(a-1) =x%(a-1) — (a^k)%(a-1) =even + odd= odd

      if F[x]=1. x%(a-1) must be a odd,and for all k:

      (x-a^k)%(a-1) =x%(a-1) — (a^k)%(a-1) =odd + odd= even

      so F[x]=(x%(a-1))&1 satisfy two condition above. What's wrong with this function? Please tell me ,Thx!

  • »
    »
    13 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    (double post)

»
13 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

in 168b, if the input is

#

#

how should the output is ? i think the right is :

#

#

but my code generate:

#

#

and it's accepted (even if tested after the contest), because that kind of test case is not appear,

the test case itself is just 11, if possible, add hacking after contest too

sry for my bad english

  • »
    »
    13 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I'll tell you big secret: we can't see difference between your three test datas.

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

      i mean, if the input is #(two new line)#, the output in my mind is supposedly #(two new line)#, but my code generate #(one new line)# and accepted

      what is the right answer for that ? thx for the reply

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

        From the problem statement: Note that empty lines must be processed just like all the others: they must be joined to the adjacent non-amplifying lines, or preserved in the output, if they are surrounded with amplifying lines on both sides (i.e. the line above it, if there is one, is amplifying, and the line below it, if there is one, is amplifying too).

        So, two consecutive empty lines should be joined into one.

»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why answer for the first test is 0.3 ?
3 1 0
10 20 30
-1 -1 2

we need to lose first two days (the probabily of this event is 0.9 * 0.8) and win 3 day so finish probability is 0.9 * 0.8 * 0.3

and in pretests 5 we have
1 0 0
7
-1

so the probability that we lose first day is 0.93 and this is the answer.

I can't understand if we don't count lose probabily in example test, why we need to count it in pretest 5?

Thanks

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

    You don't have to lose first two games. If you win the third game, you will have a bag big enough to fit any presents from first two days, should you win any.

»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't not understand the problem description because of my poor English... What a easy problem , however, so little people got accepted...

»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks!

»
13 years ago, # |
Rev. 9   Vote: I like it 0 Vote: I do not like it

What's the expected output format of test case 3 for div2 B? My result has 4 lines and 2 characters as described:

newline

# with newline

newline

# with newline

I got a error saying "expected EOLN" but didn't find out any bug myself. Can someone help me?

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

    What you mentioned is not what you are printing to the output. Look at the judgement protocol carefully. The third line has two spaces in the input and you are printing these two spaces in the output as well instead of removing them — you can see that when you mark the lines. So the judge is expecting an EOLN but finds a space instead.

»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it

why is my comment written with so big letters ?

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

    You can edit your post. Instead of pasting your code, you could give the link to it (you can retrieve the link by clicking the upper right "#" when you open the code).

    Anyway, on Codeforces you can't use the function system(), just delete it before submitting the code!

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

For some reason, I am not able to see the codes of "168B — Wizards and Minimal Spell". Even I can't see my own code!! I've got "Wrong Answer of Test 1" verdict btw.

Am I the only one facing this problem?

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In problem 167B — Wizards and Huge Prize editorial, it says "The answer will be the sum of $$$d[n+1][j][m]$$$ for all $$$j,m$$$ such ...".

I have the question about this: What if there are some $$$d[n + 1][j + 1][m + ...]$$$ that will include $$$d[n + 1][j][m]$$$ (What I means is they are not distinct to each other), so can we just sum all of them so simply like that?.

I learned that: Only if all the events A, B, C, .. are pairwise distinct, $$$P(A + B + C + ...) = P(A) + P(B) + P(C) + ...$$$. So how are all the $$$d[n + 1][j][m]$$$ are pairwise distinct anyway?

Sorry for my bad English, thanks for reading <3 <3.

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

    Anybody can help me :<< ?

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

    Any..body kind in this awesome Codeforces community :< ?

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

    I suspect the reason nobody has answered so far is that nobody has looked at this editorial for about 3 years.

    d[n+1][j][m] is the probability that, at the end, you have won exactly j contests, and have exactly m bags. You can't have won both exactly j and exactly k contests unless j and k are equal, and you can't have exactly m1 and exactly m2 bags unless m1 and m2 are equal, so these events are clearly distinct from each other.

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

      Thank you for clarify it out <3 <3. At first, I was thinking $$$d[n + 1][j + 1][m + X]$$$ can include $$$d[n + 1][j][m]$$$ somehow but it turned out to be wrong.

      Love you <3 for answering my question.

»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone please explain the part For convenience, we assume that the bag is also a prize and the prize is a bag of capacity 0. To do that, retaining a task we must add 1 to all a[i] in div1 B's editorial ?

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

    d[i][j][m] is the probability that, you have participated in contests of first 'i' days , you have won exactly j contests, and have exactly m bags. Now this m is the total capacity you gain after all the contests.

    So if we assume a prize is a bag, it will not contribute to the overall capacity. Since a[i]=-1, we add one to make it zero and from d[i][j][m] we can go to the d[i+1][j+1][m+a[i]] (capacity remains then same if we win a prize),

    Now we are also assuming bag is a prize and going from d[i][j][m] to the d[i+1][j+1][m+a[i]] state meaning, we are increasing j(the number of prizes won) and assigning that extra capacity ( a[i]+ '1' (this one)). to the bag we considered as a prize. Increasing j here means we considered bag as a prize so we increase the bag capacity by one to accommodate the same bag we considered as a prize.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E is as the same as a well-known lemma: Lindström–Gessel–Viennot lemma