szawinis's blog

Optimizing n^3 DP
By szawinis, history, 8 years ago, In English

Problem Statement: There exists a single player game called "Pair of Fours". In this game, there are four types of cards, labeled 'U', 'B', 'O' and 'N'. There are N cards in total, and initially they are arranged so that no adjacent cards are of the same type. The game goes as follows:

  1. The player chooses a card and removes it. This means the cards on the left and the right are now adjacent.
  2. While the (now adjacent) left and right cards are of the same type, remove both cards and add one to the score.
  3. If there are no cards left, the game ends. Otherwise, go back to step one.

Sample case:

13
N U B O B U O N B O N U O

I came up with an O(n^3) DP solution, but since n <= 1000, it definitely gets TLE verdict:

dp[i][j] = max(dp[i][k]+dp[k+1][j], dp[i+1][j-1]+(a[i] == a[j]))

Is there a way to optimize this, or is DP not the correct train of thought?

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

What's exactly your O(n^3) solution?

I think for updating dp[i][j] you should pick an element for the player and then remove the characters from left and right. But then you can't call dp[i][p]+dp[q][j] cause these two parts aren't independent. Maybe your solution is something else, So I would like to know if it is.

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

    My solution was to define dp[i][j] as the maximum number of points we can get within the interval [i, j]. So if the cards i and j are of the same type, we can take dp[i+1][j-1]+1. Also, there is another case where we can take dp[i][k]+dp[k+1][j], since sometimes we don't actually want to add one to the score like in the previous case. Sometimes, within our interval, there are several disjoint intervals of removed cards, and we try to split the intervals and calculate DP there, to add to our answer when we don't add to the score. This is why the DP came out in this form.

    BTW, the DP equation above was incomplete. I've fixed it a little.

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

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

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

By saying "it definitely gets TLE" do you mean that this comes from some judge, and you tried submitting your solution? It does like n3 / 4 relatively simple operations, on CF with a standard time limit (2-3 seconds) it should be fine.

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

    I guess you're right. I tried submitting my n^3 solution and it passed.

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

Since I do not know what your dynamic programming stands for, I can't solve this one for you. However, judging by the form of the recurrence, one mathematical optimization that might work is the Knuth optimization, which would bring your time down to quadratic. It depends on a very specific pattern of behavior which your function might or might not have, so try to see if you can apply it. Here is a link if you want to learn more about this optimization, and others like it: http://codeforces.me/blog/entry/8219

→ Reply