Edvard's blog

Editorial of Educational Codeforces Round 13
By Edvard, history, 9 years ago, translation, In English

678A - Johny Likes Numbers

The problem was suggested by Abdrakhman Ismail bash.

We should find minimal x, so x·k > n. Easy to see that . To learn more about floor/ceil functions I reccomend the book of authors Graham, Knuth, Patashnik "Concrete Mathematics". There is a chapter there about that functions and their properties.

С++ solution

Complexity: O(1).

678B - The Same Calendar

The problem was suggested by Arthur Jaworski KingArthur.

Two calendars are same if and only if they have the same number of days and starts with the same day of a week. So we should simply iterate over years and maintain the day of a week of January, 1st (for example). Easy to see that the day of a week increases by one each year except of the leap years, when it increases by two.

C++ solution

Complexity: O(1) — easy to see that we will not iterate more than some small fixed constant times.

678C - Joty and Chocolate

The problem was suggested by Sheikh Monir skmonir.

Easy to see that we can paint with both colours only tiles with the numbers multiple of lcm(a, b). Obviously that tiles should be painted with more expensive colour. So the answer equals to .

C++ solution

Complexity: O(log(max(a, b))).

678D - Iterated Linear Function

The problem was suggested by Zi Song Yeoh zscoder.

The problem can be solved using closed formula: it's need to calculate the sum of geometric progression. The formula can be calculated using binary exponentiation.

I'll describe more complicated solution, but it's more general. If we have a set of variables and at each step all variables are recalculating from each other using linear function, we can use binary matrix exponentiation. There is only one variable x in our problem. The new variable x' is calculating using formula A·x + B. Consider the matrix z = [[A, B], [0, 1]] and the vector v = [0, 1]. Let's multiply z and v. Easy to see that we will get the vector v' = [x', 1]. So to make n iterations we should multiply z and v n times. We can do that using binary matrix exponentiation, because matrix multiplication is associative.

As an exercise try to write down the matrix for the Fibonacci numbers and calculate the n-th Fibonacci number in O(logn) time. The matrix and the vector is under the spoiler.

The matrix and the vector for the Fibonacci numbers
C++ solution

Complexity: O(logn).

678E - Another Sith Tournament

The problem was suggested and prepared by Alexey Dergunov dalex.

Let's solve the problem using dynamic programming. zmask, i — the maximal probability of Ivans victory if the siths from the mask already fought and the i-th sith left alive. To calculate that DP we should iterate over the next sith (he will fight against the i-th sith): .

C++ solution

Time complexity: O(2nn2).

Memory complexity: O(2nn).

678F - Lena and Queries

The problem was suggested by AmirMohammad Dehghan PrinceOfPersia.

Let's interpret the problem geometrically: the pairs from the set are the lines and the problem to find to topmost intersection of the vertical line with the lines from the set.

Let's split the queries to blocks. Consider the lines added before the current block and that will not deleted in the current block. Let's build the lower envelope by that lines. Now to calculate the answer to the query we should get maximum over the lines from the envelope and the lines from the block before the current query that is not deleted yet. There are no more than lines from the block, so we can iterate over them. Let's find the answers from the envelope for all queries of the third type from the block at once: we should sort them and iterate over envelope using two pointers technique.

C++ solution

Complexity: .

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

Comments Comments (34)
| Write comment?
»
9 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Please write the editorial for E

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

About problem E:

After some interesting discussion, I was wondering what exactly can we say about the optimal solution?

Let's assume that optimal sequence can be represented by a sequence a1, a2, ..., an of fighters in which a1 fights a2, then the winner fights a3, etc. Intuitively, the probability someone wins is higher the more to the right of the sequence it is: this implies an should be Ivan in an optimal sequence.

Now who do we want at the second to last position? That person will be given a greater chance to fight Ivan, so we want it to be the one that has the smallest chance to win against him.

Generalizing to all n players, we have the following O(n2) greedy solution: construct the sequence of fighters from the last to the first. For each pick, pick the available fighter that makes probability of Ivan winning in current sequence highest possible.

Code: 18489412

Of course, there's no such thing as "proof by AC", so I'm still curious if this solution is actually correct. If it is, I think it is quite interesting :)

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

    Some history: the setting was taken from Timus 1218. In 1218, we discovered a NlogN solution and included that problem into our contest at Petrozavodsk camp, where 7 teams out of 50 solved it.

    As my teammates just said, it became a tradition: all "Jedi Tournament" problems can be solved better than author initially thought. You could have done the same with your solution.

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

    Actually I've discussed with dalex that. And I thought about the same thing. But both of us agreed that greedy solution is incorrect here.

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

      If you discussed this before the contest, shouldn't you have included a test that fails the greedy solution?

      I'm also curious to know how you reached this conclusion.

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

        I thought about different greedy solution. This one passes random tests and must be correct.

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

        Oh you misunderstood. We have not a countertest, we just thought that greedy solution is incorrect.

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

Another solution for problem F in O(N*log2N).

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

    Could u please go for more detail about it?? I have difficulty in reading and understanding ur code :P

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

    Do you use the technique with storing the blocks of the sizes 2k?

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

      Problem to find the topmost intersection of the vertical line with the lines from the set can be solved with Convex Hull Trick.

      I builded a segment tree of CHT over time interval.
      For ith insertion query update the segment tree with this line in range [ i, time till ith line exists ].
      For every query of 3rd type it is equivalent to point query at that point of time.

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

        Nice. But I think it's more complicated.

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

          During contest I tried with the same approach as mentioned in editorial (Submission). But it timed out because my complexity was O(N1.5 * logN). So I had to go this way but it seems that logN factor can be removed.

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

    I solved the problem using your idea but with complexity O(N*logN). Submission here: 18842789

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

      Insertion in logN nodes is log2N, right ?

      P.S: Your N*logN is slower than mine N*log2N.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        Actually if you insert the lines in sorted order the overall complexity for insertion is because you insert in nodes in total linear time. This was mnaeraxr and I did (using your idea, btw) 18845711. You probably didn't look deeper into mnaeraxr code.

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

Can anyone explain a little more about the recurrence relation in E?

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

Can someone explain the editorials for Problem E in a somewhat detail manner, it would be a great help.

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

    My approach. First observe that our jedi should fight last. Then we exclude him from the set of siths. Let mask be some subset of set of siths (without jedi) and i is a sith of this subset. Then dp[mask, i] is maximum (among all sequences of siths) conditional probability that Ivan wins tournament given that siths from mask already fought and i-th is a winner.

    We init our dp with full mask:

    for (int i = 1; i < n; i++)
    dp[all, i] = p[0, i];

    where all is full mask. That means, if all siths already fought and i-th is a winner then probability that Ivan wins tournament is equal to probability of win this sith. Then we loop over smaller and smaller mask's and calculating their values from previous calculations. To find dp[mask, i] use formula from editorial. Should be more clear now. If not I can explain in more detail.

    And the end answer will be maximum of dp[mask_i, i]. It is conditional probability that Ivan wins tournament given that i-th sith is the first participant in tournament.

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

      Could you explain more about the formula. I want to ask some specific questions:

      • z(mask,i) is when the i-th wins so why do they + z(mask U j,j)*p[j][i] as well.

      • z(mask,i) is the "maximal probability of Ivans victory if the siths from the mask already fought and the i-th sith left alive". So is Ivans necessarily be i or some bit 1 in mask or some other siths?

      This contest has been so long but if you could answer these, I would be really thankful. I have comtemplating about this problems for a week but still didn't figure it out. Thanks <3

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

Please ,explain me the solution of Another Sith tournament.Please explain me in words how that formula comes??

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

In above code for problem F, I want to know why blen is 2500, not sqrt(n). Please tell me.. my submission also TLE when i set blen sqrt(n), but accept when i set blen 2500. sorry for my fool english

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

    we need sorting all query in each block. so complexity is O(N * N / size + N * log2(size) + size * size). for best we choose size = 2500.

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

Can someone explain how is the complexity of solution of Problem E , in the editorial O(N^2 * 2^N) ? I think it is O(N^3 * 2^N) as for every O(n^2) starting pairs we have an O(n) loop to set the next winner.

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

Problem F 线段树分治+斜率优化可以做到O(NlogN)吧

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

Could you explain more about the formula in problem E. I want to ask some specific questions:

  • z(mask,i) is when the i-th wins so why do they + z(mask U j,j)*p[j][i] as well.

  • z(mask,i) is the "maximal probability of Ivans victory if the siths from the mask already fought and the i-th sith left alive". So is Ivans necessarily be i or some bit 1 in mask or some other siths?

This contest has been so long but if you could answer these, I would be really thankful. I have comtemplating about this problems for a week but still didn't figure it out. Thanks <3

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

    • $$$z(mask, i)$$$ is not the probability that the $$$i$$$-th sith wins. Remember that we are calculating the probability of the $$$0$$$-th sith being the ultimate winner. It simply says that all siths in the mask have fought some match and the only sith alive out of those currently is the $$$i$$$-th sith.

    • Ivan corresponds to the $$$0$$$th bit. There are $$$2$$$ cases:

      $$$1$$$. $$$0$$$-th bit is $$$0$$$, which means Ivan hasn't fought yet.

      $$$2$$$. $$$0$$$-th bit is $$$1$$$. In this case, if $$$i \ne 0$$$, this means that Ivans fought but was killed. So, the answer for this state is $$$0$$$. Otherwise, Ivan is the survivor from all matches conducted so far and we proceed with the tournament.

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

678D - Iterated Linear Function How do we come from knowing that we have to find a matrix to the actual matrix? And what about the vector v, where that comes from?

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

    Here is a simple mathematical approach:

    After simplifying:

    gn(x) = (a^n)*x + b*( 1 + a + a^2 + a^3 ....... a^(n-1) )

    [ 1 + a + a^2 + a^3 ....... a^(n-1) ] forms a Geometric Progression, whose sum can be calculated as:

    S = b* (a^n-1)/(a-1)

    for the solution, see my submission 78952460

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

My solution to Sith Tournament (problem E) works without an extra index in DP. It is slightly different from the editorial.

Mask of (n — 1) bits represents which siths are still alive (as ivan will always stay alive, no need for keeping an extra bit for him). dp[mask] represents probability Ivan wins given that the siths in mask are alive. dp[0] is trivially 1 (as mask=0 means all other siths have died). We compute dp in increasing value of mask.

For computing value of dp[mask], we simulate the situation where Ivan has to choose two siths for a fight, and where one of them dies. We just run a loop through all pairs of distinct set bits (b1 and b2), and update our dp as follows:

probA = beats[b1][b2] * dp[mask ^ (1 << b2)]; // b1 beats b2
probB = beats[b2][b1] * dp[mask ^ (1 << b1)]; // b2 beats b1
totalProb = probA + probB;
dp[mask] = max(dp[mask], totalProb);

Before exiting, we also pair each sith with Ivan himself, updating our dp[mask] as follows:

dp[mask] = max(dp[mask], beats[1][bit] * dp[mask ^ (1 << bit)]

In the end, we print dp[(1 << (n - 1)) - 1].

AC Submission

→ Reply