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 ?
Auto comment: topic has been updated by anupamshah_ (previous revision, new revision, compare).
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).
Can you please explain what does last1 and last2 indicate ?
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.
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.
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]--;andfreq[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.
Thanks for the efforts bro.
Got it accepted :)Good job.. Anytime!