### awoo's blog

By awoo, history, 6 years ago, translation,
• +46

| Write comment?
 » 6 years ago, # | ← Rev. 2 →   0 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..)
•  » » 6 years ago, # ^ |   +4 Haven't tried but algorithms is not likely to work when n = 500, 000.
 » 6 years ago, # |   +3 Can we solve I using KMP?
 » 6 years ago, # |   +7 Nitpick: complexity of the problem D solution is rather O(n2).
 » 6 years ago, # |   0 Prob H: Can someone explain how to calculate dp(h, k) values
 » 6 years ago, # |   +1 Can someone explain the solution of E in a bit more detail.
•  » » 6 years ago, # ^ |   +6 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.
•  » » » 6 years ago, # ^ |   0 Thanks a lot. You explanation and your code helped me understand it.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 if it is instead too low, negate all the temperatures and apply the same procedure. Why we do that?
 » 6 years ago, # |   +16 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).
•  » » 6 years ago, # ^ |   0 How to prove correctness?
•  » » » 6 years ago, # ^ |   0 Consider the taps hotter than T.Supposed in the optimal solution, you use taps t1 and t2, where Ty, 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.
 » 6 years ago, # |   +6 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
•  » » 4 years ago, # ^ |   0 your solution has a better run time but it is still o(n^2)
•  » » » 4 years ago, # ^ |   0 Notice that I said O(m) not O(n).
•  » » » » 4 years ago, # ^ |   0 ah!
 » 6 years ago, # |   0 Thanks a lot
 » 6 years ago, # |   0 I don't understand how calculating the convolution helps in Problem I. Could someone elaborate?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 You need to reverse T in order to form a formula for convolution.
•  » » » 6 years ago, # ^ |   0 What do you mean?
• »
»
5 years ago, # ^ |
+8

## 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.

 » 5 years ago, # | ← Rev. 2 →   0 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)?
•  » » 5 years ago, # ^ |   0 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:)
 » 5 years ago, # |   -8 Can someone please tell me what is wrong in my submission for D ? 38697308
 » 4 years ago, # |   0 Why WA on test case 8 ?https://codeforces.com/contest/954/submission/57313165
 » 2 years ago, # |   0 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
 » 2 years ago, # |   0 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.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +10 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