PikMike's blog

By PikMike, history, 4 months 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  

»
4 months 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..)

  • »
    »
    4 months 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.

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can we solve I using KMP?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought about it several days and asked a few people (ranked specialist and above) and we couldn't find a solution with KMP

»
4 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 months 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?

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
4 months 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).

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to prove correctness?

    • »
      »
      »
      4 months 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.

»
4 months 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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks a lot

»
4 months 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?

  • »
    »
    4 months 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.

  • »
    »
    3 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

http://codeforces.com/contest/954/submission/36494543

Where is my solution wrong please tell me

»
3 months 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)?

  • »
    »
    3 months 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:)

»
7 weeks 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