chinesecoder's blog

Help in this problem.
By chinesecoder, history, 6 years ago, In English

The problem , 814c , my approach was , for each segment [l, r ] , check whether its possible to color it with at most m colors or not.

since there can be 26*n queries and n^2 segments , the solution will work in 26*n^3 which will give TLE .

The editorial mentions some prefix based approach but i couldn't understand the 2nd part , how its optimizing the solution .

How to reduce 26 * n ^3 to 26*n ^2 .

is there any dp solution possible to it . ?

  • Vote: I like it
  • -14
  • Vote: I do not like it

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

let f(l) be the biggest r that you can color [l, r] with at most m colors. then it's clear that if l1 ≤ l2 then f(l1) ≤ f(l2). so you can find answer for all queries in O(n) with two-pointer.

I think this solution works too:

let DP[i][j][c] be maximum number of continuous character of c ending at i if we color exactly j characters. then DP[i][j][c] is equal to DP[i - 1][j][c] + 1 if s[i] = c and DP[i - 1][j - 1][c] otherwise.

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

    Thanks , two pointer method is quite tough to implement .

    in 2nd method do we have to add any more coding or they r sufficient.

    Sigyn

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

      For every query mi ci, you should get the maximum value for every 1 ≤ i ≤ n: DP[i][min(n, mi)][ci].

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

Here is my approach as requested.

Let f(x, r) represent the maximum length of substring of character x with EXACTLY r replacements. How do we calculate it for a given x ?

We visit every range [L, R]. The number of replacements in this range is the number of characters that are not x. 

    for(int ch = 0; ch < MAX_ALPHABETS; ch++)
    {
        for(int left = 0; left < length; left++)
        {
            int replacements = 0;

            for(int right = left; right < length; right++)
            {
                replacements += (S[right] != 'a' + ch);

                maximum_segment[ch][replacements] = max(maximum_segment[ch][replacements], right - left + 1);
            }
        }
    }

This takes O(σ N2)

Now let g(x, r) represent the maximum length of string if we do at most r replacements.

g(x, r) = max{f(x, 0), f(x, 1), f(x, 2), ... , f(x, r)}

    for(int ch = 0; ch < MAX_ALPHABETS; ch++)
    {
        for(int replacements = 1; replacements <= length; replacements++)
        {
            maximum_segment[ch][replacements] = max(maximum_segment[ch][replacements], maximum_segment[ch][replacements - 1]);
        }
    }
→ Reply