Makise_Kurisu's blog

Need help in optimizing solution to a dynamic programming problem
By Makise_Kurisu, 3 years ago, In English

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:

$$$ DP[i][j] \rightarrow \text{Max score we can get from subarray }A[i \dots j] $$$

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.

$$$ \displaystyle DP[i][j]=\max(DP[i+1][j],\sum_{k=1}^{K-1} DP[e_k+1][e_{k+1}-1]+K^2) $$$

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.

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

Comments Comments (4)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It can be solved in $$$O(n^3)$$$. Here is a good editorial

→ Reply