vintage_Petr_Mitrichev's blog

By vintage_Petr_Mitrichev, history, 6 weeks ago, In English,

Hello , can anyone please clarify what the author is saying in editorial of problem d . I am not getting the dp state . how to think it recursively ?

why is author taking at most case ? what it mean ?

 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it  

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I'll try to explain my solution. Firstly, I hope you get that you never need to make more than 2 triples of the format [x, x + 1, x + 2] (Claim 1). Now create a tile frequency array from 1 to m. We'll apply DP on this starting from 1 till m. DP state is dp[i][j][k], where i is the last index of the prefix considered, j is the number of tiles remaining of size (i — 1) and k is the number of tiles remaining of size i. Because of the claim 1, we never need to store more than 2 tiles of size (i — 1) and 4 tiles of size i for later operation (Why?). To make the transition to (i + 1), you can iterate for all possible values of j and k. https://codeforces.com/contest/1110/submission/49606713. (Note that DP state with -1 as value is representing the impossible state.)

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Firstly, I hope you get that you never need to make more than 2 triples of the format [x, x + 1, x + 2] --> sorry , but i didn't get . what will happen if we take 3 triplets , will it lead to wa ?

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks PrakharJain , i get it . 4 tiles of size i is bcoz 2 for i-1 and i pair and 2 for i and i+1 pair . its quite hard to come up with this idea on own .

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No. Because you can always replace 3 triples of this format to 3 triples [x, x, x], [x + 1, x + 1, x + 1] and [x + 2, x + 2, x + 2].

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

At first, let's notice that it isn't worth taking 3 times or more [x, x + 1, x + 2], we can take [x, x, x], [x + 1, x + 1, x + 1], [x + 2, x + 2, x + 2] instead.

Now let's compute how many times number x is present for any valid x. Denote the value by cnt[x].

Now let's calculate dp[i][j][k] (in this dp we consider all numbers from the given array that are less than i - 1, cnt[i - 1]  -  k (k is up to 3) numbers which are equals to i  -  1 and j numbers which are equal to i (j is up to cnt[i]), dp[i][j][k] is the answer for these numbers)

How to calculate it? As we know, there is no point in taking 3 times [x, x + 1, x + 2], so dp[i][j][k] = max(dp[i - 1][cnt[i] - l][l] + (j - l) / 3), l < 3. That's because we can take [i - 2, i - 1, i] 0, 1 or 2 times. If we take it l times, than we have (j - l) numbers that are equals to i and we have to divide them into groups of the type [i, i, i]. Also we have to divide the other numbers, but we know that the answer, it is dp[i — 1][cnt[i] — l][l]

Hope, my answer will help you. Ask me if you have any questions :D

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    thanks i get it . Miraak

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

      Hi, Can you please explain why "it isn't worth taking 3 times or more [x, x + 1, x + 2]". Because in both the cases I am having the answer as 3. What advantage I am having by considering [x, x, x], [x + 1, x + 1, x + 1], [x + 2, x + 2, x + 2] instead of 3 times of [x, x + 1, x + 2].