Hello friends, I was trying to solve this dynamic programming problem. The editorial proposes an $$$\mathcal{O}(N^4)$$$ solution to this problem, but I think it could be solved in $$$\mathcal{O}(N^3)$$$ time according to the following approach:
Say, $$$i \le e_k \le j \rightarrow$$$ kth occurence of $$$A[i]$$$ between $$$i$$$ and $$$j$$$, $$$K \rightarrow$$$ number of occurrences of $$$A[i]$$$ in $$$[i\dots j]$$$ . Transitions are as follows.
Unfortunately, this approach gives WA. I'd be grateful if anyone could share an $$$\mathcal{O}(N^3)$$$ or an intuitively more convincing $$$\mathcal{O}(N^4)$$$ solution as I was not able to follow the editorial completely.
I thought you can only pick consecutive plates, i.e. those that form a subarray. how does $$$kth$$$ occurence of $$$A[i]$$$ work in that case.
Yes say the subarray looks like this
A....A.......A...A Now if we want to take all the A's together in one shot then we'll first have to make them consecutive as you said, so we first remove all the elements which occur between any 2 occurences and then take all K occurences together
It can be solved in $$$O(n^3)$$$. Here is a good editorial
oh wait I can't read