Imthiyash786's blog

Need help with the following problem
By Imthiyash786, history, 4 weeks ago, In English

Given an array A of lower case characters $$$a_1,a_2,....,a_n$$$ we need to perform the following operation until it becomes empty,

  • Select a segment $$$(l,r)$$$ such that $$$a_l=a_{l+1}=a_{l+2}=....=a_r$$$ and remove the segment from the array.

  • Add the square of length of segment to your score and rearrange the remaining elements.

Output the maximum score that can be obtained.(score is initialized to 0).

Constraints: n <= 60

input

2
6
a a b b a c
12
a b a b a b a b a b a b

output

14
42
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Hi bro

My Hint

Spoiler

Hint2

Spoiler
→ Reply
»
4 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

It can be solved using Dynamic Programming by maintaining 2 states(l,r)

If there's only one element (l == r), then dp[l][r] = 1

If the segment A[l:r+1] consists of identical characters (A[l] == A[r] for all l <= i <= r), remove it as a whole to get dp[l][r] = (r-l+1)^2

For any two indices k where l <= k < r, split the segment A[l:r+1] into A[l:k] and A[k+1:r], and maximize the score by combining scores from these subarrays.

The complexity using this can go till O(n^3) which works for N <= 100

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

    I don't think this would work can you explain the subparts for the 2nd case which would lead to answer 42.

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

    wouldn't this break if

    aaaaaaaaabaaaaaaaaaaa

    obvious answer is to break the b and get 401

    if you did dp then dp[l][r] it would only get 203 i think

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

      Yea that's what I was trying to say, dp[l][r] doesn't work so is there any other way or idea of solving the above problem?

      → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
        ← Rev. 2   Vote: I like it +9 Vote: I do not like it

        $$$\mathrm{dp}[l][r]$$$ should still work, just the calculation is a bit more involved.

        Say we want to calculate $$$\mathrm{dp}[l][r]$$$. In addition to the obvious cases of $$$A[l] = \cdots = A[r]$$$ and $$$\mathrm{dp}[l][m] + \mathrm{dp}[m + 1][r]$$$, do something like this if $$$A[l] = A[r]$$$.

        Let's make a new array $$$\mathrm{xdp}[i][j]$$$, initialize it to $$$-\infty$$$ initially. Roughly, $$$\mathrm{xdp}[i][j]$$$ represents the maximum score we can get if we remove $$$j$$$ items among the first $$$i$$$ with the current operation (other items have already been removed with previous steps). Set $$$\mathrm{xdp}[l][1] = 0$$$. For each $$$i$$$, $$$l < i \le r$$$:

        • if $$$A[i] = A[l]$$$, set $$$\mathrm{xdp}[i][j] = \max(\mathrm{xdp}[i][j], \mathrm{xdp}[i - 1][j - 1])$$$ for all $$$j$$$;
        • for all $$$L$$$ and $$$j$$$, set $$$\mathrm{xdp}[i][j] = \max(\mathrm{xdp}[i][j], \mathrm{xdp}[L - 1][j] + \mathrm{dp}[L][i])$$$.

        To calculate $$$\mathrm{dp}[l][r]$$$ from this data, take the maximum of $$$\mathrm{xdp}[r][j] + j^2$$$ over all $$$j$$$.

        Complexity should be $$$O(n^5)$$$. This sounds a bit too slow for $$$n \le 60$$$, but it has a very good constant: for given $$$l, r$$$, we only need to look at $$$i, L \in [l, r]$$$ and $$$j \le r - l + 1$$$. So it's really more like $$$\frac{n^5}{20}$$$ maximums and additions.

        → Reply