### pikmike's blog

By pikmike, history, 22 months ago, translation, ,   Comments (33)
 » 22 months 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.
•  » » » 22 months 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?
•  » » 22 months 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
 » 22 months 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