awoo's blog

Educational Codeforces Round 40 Editorial
By awoo, history, 7 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +46
  • Vote: I do not like it

Comments Comments (28)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can we solve G using segment-tree ? (we search for the minimum value then we query on the second minimum on all intervals containing the first value and we update the interval that contain the maximum number of minimums and so on until we run out of reserve archers..)

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

    Haven't tried but algorithms is not likely to work when n = 500, 000.

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

Can we solve I using KMP?

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

Nitpick: complexity of the problem D solution is rather O(n2).

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

Prob H: Can someone explain how to calculate dp(h, k) values

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

Can someone explain the solution of E in a bit more detail.

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

    Try using the maximum amount of water for each tap. I'm going to assume the resulting temperature is too high, if it is instead too low, negate all the temperatures and apply the same procedure.

    Now that the temperature we have is too high, we want to lower it. Which tap should we reduce to lower the temperature the fastest? The hottest one! Reducing that lowers the temperature fastest per unit of water lost. Now we can greedily turn off the hottest taps until that would take us below the target temperature, and binary search or do some math to figure out how much of the last faucet to reduce.

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

      Thanks a lot. You explanation and your code helped me understand it.

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

      if it is instead too low, negate all the temperatures and apply the same procedure. Why we do that?

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

There is no need for binary search on E.

Take the taps that are hotter than T, and the taps colder than T separately. Sort the first set in increasing order, and the second in decreasing order.

Then just greedily turn on the coldest hot taps, and hottest cold taps, while keeping the temperature balanced at T.

The complexity is still O(NlogN) because of sorting, but the actual computation is O(N).

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

    How to prove correctness?

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

      Consider the taps hotter than T.

      Supposed in the optimal solution, you use taps t1 and t2, where T<t1<t2, and you don't use up all of tap t1. Then you can turn tap t1 up by some amount x, and turn down tap t2 by some amount y, where xt1=yt2, keeping temperature constant. Since t1<t2, this means that x>y, and this means the new solution uses more water.

      Thus, it's always correct to use the colder hot taps first. Similarly, it's best to greedily use the hottest of the cold taps first.

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

Problem D can be solved in O(m)

hint: for a 'x'-distant node from s, find the nodes which are less than D-x-2 away from t. It can be done using prefix sum. Then cancel nodes which already has edges with current node. details here

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

Thanks a lot

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

I don't understand how calculating the convolution helps in Problem I. Could someone elaborate?

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

    You need to reverse T in order to form a formula for convolution.

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

    I. Yet Another String Matching Problem

    I think you know how 'naive' solution works elaborated in editorial.

    Now, let's think how FFT works when matching two binary strings (having only 'a' or 'b'). To match pattern P into text T, you take coefficient 1 for 'a' and -1 (or 0) for 'b', reverse P and perform FFT on them. In the resultant polynomial if coefficient length equals to length of P, then there is a match at this position. It's one of the basic usage of FFT though this can be done with KMP (So guess KMP is a solution too).

    Now, let's come back to our original problem. Let's consider coefficient of all 'a' from S as 1, all 'b' from T as 1 and else 0 in both strings. So, if we run FFT we get all matched positions where 'a' can be 'b' and don't care for other character comparisons. Let's assume it as an edge between 'a' and 'b' for a graph at matched positions. Thus, consider for all other edges. Now, for a position's graph, we calculate unique vertices and components and thus find required answer.

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

Can someone please explain what does problem G (castle defense) wants us to find? I have read the problem over and over again but I just can't get it. Can someone please explain the problem (problem only)?

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

    Hi,

    This is a kind of typical binary search problem that wants us to maximize the minimum value. For any i in [1, n], there is a defense level value. For this whole array, it has a Reliability value, which can be calculated by defense level value. And we are asked to maximize Reliability value by distributing arches to some sections of wall.

    Hope it help:)

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

Can someone please tell me what is wrong in my submission for D ? 38697308

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

Why WA on test case 8 ?

https://codeforces.net/contest/954/submission/57313165

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

Regarding problem number I, how does this solution of _shanky pass the time limit of 4 seconds?

In my calculation this solution runs in almost length(a)*length(b) time, or I'm missing something? awoo, _shanky

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

It is possible to solve (read: cheese) H with arbitrary-mod FFT. My solution uses the observation in the first part of the editorial, that is, for each $$$d$$$, count the number of paths with depth of LCA equal to $$$d$$$.

It is not hard to think of a FFT-based solution; let's look at the subtree of the LCA and reassign depths so that depth of LCA = 0.

The first case is that both endpoints of the path are in different subtrees of the children of the LCA, in which the answer for paths of length $$$k$$$ is the coefficient of $$$x^k$$$ in $$${c\choose 2}(\text{cnt}_1x + \text{cnt}_2x^2 + \text{cnt}_3x^3 + ...)^2$$$, where $$$\text{cnt}_i$$$ is the number of nodes of depth $$$i$$$ in a LCA-child's subtree, and $$$c$$$ is the number of children of the LCA. This can be done with FFT in $$$O(n\log{n})$$$.

The second case is when the LCA is an endpoint of the path, which means that the answer for paths of length k is $$$c \cdot \text{cnt}_k$$$.

Summing both cases up and multiplying by the number of nodes at each depth, we can get the answer for all path lengths in $$$O(n^2 \log n)$$$.

I used KACTL's template for arbitrary-mod FFT which is reasonably fast, but even then my submission barely squeezed into the time limit.

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Sorry for necroposting, but you dont really need arbitrary mod FFT to multiply the polynomials, the polynomial of a subtree with root at depth i is equal to 1+ Ai*(poly at depth i+1), using this you can compute square of polynomial at depth i using square of poly at depth i+1 in O(n). This passes comfortably in the given time limit. 203601456

    → Reply