### awoo's blog

By awoo, history, 4 years ago, translation,   Comments (35)
 » 4 years ago, # | ← Rev. 2 →   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..)
•  » » Haven't tried but algorithms is not likely to work when n = 500, 000.
 » Can we solve I using KMP?
•  » » I thought about it several days and asked a few people (ranked specialist and above) and we couldn't find a solution with KMP
 » Nitpick: complexity of the problem D solution is rather O(n2).
 » Prob H: Can someone explain how to calculate dp(h, k) values
 » Can someone explain the solution of E in a bit more detail.
•  » » 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.
•  » » » Thanks a lot. You explanation and your code helped me understand it.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   if it is instead too low, negate all the temperatures and apply the same procedure. Why we do that?
•  » » » » After negating temperatures, our problem is converted into the case where the resulting temperature is too high and we can solve it using binary search.
 » 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).
•  » » How to prove correctness?
•  » » » 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.
 » 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
•  » » your solution has a better run time but it is still o(n^2)
•  » » » Notice that I said O(m) not O(n).
•  » » » » ah!
 » Thanks a lot
 » I don't understand how calculating the convolution helps in Problem I. Could someone elaborate?
•  » » 4 years ago, # ^ | ← Rev. 2 →   You need to reverse T in order to form a formula for convolution.
•  » » » What do you mean?
• »
»

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

•  » » » I don't understand 'naive' approach please can you elaborate ?
 » http://codeforces.com/contest/954/submission/36494543Where is my solution wrong please tell me
 » 4 years ago, # | ← Rev. 2 →   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)?
•  » » 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:)
•  » » » Thanks, it really helped!
 » Can someone please tell me what is wrong in my submission for D ? 38697308
 » Good educational round. Very interesting problems.
 » can someone explain what is wrong with my solution? linkI am just using simple maths logic after calculating the total number of vertex lies in the shortest path.Thanks in advance :)
 » if anyone can help me understanding solution of div 2 B string typing .thnks reply needed fast
 » Why WA on test case 8 ?https://codeforces.com/contest/954/submission/57313165
 » 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
 » 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.