anupamshah_'s blog

By anupamshah_, history, 7 weeks ago, In English,

Here is the link to the problem . I have gone through the editorial but didn't got the approach ( Although I got that we don't need to take more than 2 occurences of a partical triplet [x1,x1+1,x1+2] ) ,I was thinking of DP with three states position i, frequency of i-1th character we took and frequency of i-2nd character we took.

But wasn't able to come up with a solution. Can anybody help me with the solution ?

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

»
7 weeks ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

The problem is very difficult.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by anupamshah_ (previous revision, new revision, compare).

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't read the editorial but here's my approach:

At first, make a frequency array (let's call it $$$freq$$$), where $$$freq_i$$$ is the number of $$$i$$$s you have in the array. Here's an important tip: you won't try taking consecutive triples $$$x1,x1+1,x1+2$$$ three times. because you can take them like $$$x1,x1,x1$$$ , $$$x1+1,x1+1,x1+1$$$ and $$$x1+2,x1+2,x1+2$$$. Both will give the same answer.

Now we have $$$dp[i][last1][last2]$$$ is the maximum number of triples you can achieve when you're trying the $$$i_{th}$$$ number and you took $$$last1$$$ consecutive triples from $$$i-1$$$ and $$$last2$$$ consecutive triples from $$$i-2$$$.

Now you have $$$freq_i - ( last1 + last2 )$$$ numbers (because $$$last1+last2$$$ numbers were took by the previous consecutive triples from behind you). you can either take all of them as "all the same" triples which is: $$$dp[i+1][0][last1] + \frac{x}{3}$$$, or make one consecutive triple from here and the rest are "all the same" triples and this is: $$$dp[i+1][1][last1] + \frac{x-1}{3} + 1$$$ (here $$$+1$$$ is for the one consecutive triple), and the same for making two consecutive triples from here, just make sure you have enough numbers to do so.

Here's my submission for a better understanding.

Storing the frequency for the previous two numbers costs a lot of memory and time, so in all DP problems you'll need something smart to reduce time complexity and memory usage (like we did here for trying taking at most two consecutive triples from a single position).

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

    Can you please explain what does last1 and last2 indicate ?

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

      As I said, $$$last1$$$ is the number of consecutive triples made starting from $$$i-1$$$ and $$$last2$$$ is the number of consecutive triples made starting from $$$i-2$$$.

      Consider a consecutive triple $$$x,x+1,x+2$$$, it started at $$$x$$$. So when you're at $$$i_{th}$$$ position and tried making a triple from $$$i,i+1,i+2$$$, you need to tell the following two numbers that you made a consecutive triple starting from $$$i$$$ because this will affect their answer.

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

        Just clarifying, I am somewhat getting the idea .

        Is last1 triplets of type [x-1,x,x+1] and last2 of type [x-2,x-1,x] ?

        And since both of them involve x so will somehow affect it.

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

          No, always when taking a consecutive triple I'm taking them like $$$x,x+1,x+2$$$. (It's my implement, of course you can implement it in another way).

          But when taking a consecutive triple like $$$x,x+1,x+2$$$, you should decrease $$$x+1$$$ and $$$x+2$$$ by one, of course you can't just do freq[x+1]--; and freq[x+2]--; because this will affect the whole dp and will be a lot of mistakes, so you'll just say: How many consecutive triples I did in $$$i-1$$$ and $$$i-2$$$?

          Here, $$$last1$$$ is the number of consecutive triples I took in $$$i-1$$$ and $$$last2$$$ is the number of consecutive triples I took in $$$i-2$$$, so in the beginning of the DP function I declared $$$x$$$ as $$$freq[i]-(last1+last2)$$$, because when there are $$$last1$$$ numbers I took making the consecutive triples starting at $$$i-1$$$ and $$$last2$$$ numbers I took making the consecutive triples starting at $$$i-2$$$, so these numbers I can't use right now.