bhagya.kjain's blog

How to solve this ??
By bhagya.kjain, history, 6 months ago, In English

Given a string, compress the string as optimal as possible by removing the consecutive characters if 3 or more consecutive characters .

This is like a candy crush game !

Eg : Input : "aabbbbac", output will be "c" .

First, you can remove all the "bbbb", then string turns to be "aaac".

Then, "aaac" turns to be "c" .

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

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

PS. Stack solution will not work, as order matters.

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

Any constraints? Some form of 2D DP [L][R] would probably work, but is only worth thinking about if the constraints are low enough.

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

    Assume low constraints. N = 60 (low enough for N^4 & high enough for bitmasking)

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +43 Vote: I do not like it

      I think the following should work, correct me if you don't think so.

      Let $$$S$$$ be the original string. Consider the following DP

      $$$F[L][R]$$$ = the maximum number of $$$S_L$$$ characters that the substring $$$S_{L...R}$$$ can be reduced to, or $$$-1$$$ if it cannot be reduced to only characters equal to $$$S_L$$$

      Note that $$$F[L][R]$$$ is a deterministic indicator of whether $$$S_{L...R}$$$ can be fully removed, since it only depends on whether $$$F[L][R] \geq 3$$$. This is because we can always postpone the removal of the substring that contains the very first character until the very end.

      Now let's compute $$$F[L][R]$$$.

      • If $$$F[L][R]\geq2$$$, then there must be some other character equal to $$$S_L$$$ in $$$S_{L...R}$$$ such that we have not removed it to the very end. As such, there exists some $$$k$$$ such that $$$S_k=S_L$$$ and the optimal value is $$$F[L][R]=F[L][k-1] + F[k][R]$$$, where none of the summands are $$$-1$$$.
      • Otherwise $$$F[L][R]=1$$$ if $$$F[L+1][R]\geq3$$$ (because we can just remove everything but the first character), and $$$F[L][R]=-1$$$ otherwise.

      You can just take the max of the two cases.

      So we can compute $$$F$$$ in $$$O(N^3)$$$. From there, it is trivial to compute the optimal compression in the original string via a 1D DP

      $$$G[i]$$$ = the shortest compression in $$$S_{1...i}$$$

      Using the fact that $$$F[L][R]\geq3$$$ implies you can fully remove $$$S_{L...R}$$$ you can compute $$$G$$$ in $$$O(N^2)$$$

      Total is $$$O(N^3)$$$, I haven't thought about optimizing any part.

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

        https://codeforces.com/contest/1132/problem/F i am asking for a very similar problem At first i did this will this dp works Enchom ?"in this problem i chosed dp state to be the dp[i][x] where it means the answer for the case for the length from 1 to x index of the string and last character we deleted is of x character, for transition state what i did was consider the case of dp[i+1][y] =min(dp[i][y],dp[i][x]+1) for all x not equal to y and if(s[i+1]==y? i am still thinking what would be the state transition for the case of s[i+1]!=y though.

        Also why first idea came of range dp to you , why not till some index dp calculation will always not work ?

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

          I didn't understand the idea of your DP, but if your state is [index][character], I'm doubtful of whether it can ever work.

          The problem you linked is very similar indeed and uses a very similar DP to what I described (a simpler one).

          Range DP here comes quite naturally even if you try to build a 1D state. Suppose I try to build $$$F[i]$$$ to be the solution in $$$1...i$$$. To make a transition I need to consider when the $$$i$$$-th character will be removed. Suppose it will be removed together with some other character at index $$$k<i$$$. Well, for me to know whether this is possible I must know whether $$$k+1...i-1$$$ is removable at all (and how quickly). So once you try a few ideas and it seems like you need to know the solution for arbitrary substrings, you naturally move to a range DP.

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

            now i get it how to get from 1D state to realizing its a 2D state thanks . actually my solution considered every possible character even if not possible to be deleted as last one from a i length subarray . so like if s[0]='a', i would make dp[1][x] where x !=a all zero and x==a one value as 1 and then make transition for rest bigger lengths. but seems like it will not work at all as for transition we have two choice whether to delete the s[i+1] character as last or not if deleted last i had the transition state being described above else case i was having trouble . seems like i got it from your method.

            One thing more i would like to know whether you have seen any problem which uses the last operation as in a dp state? like i have heard of a problem where we are given an array and in which we select e a element then the score we get is previouselement*element*nextelement and then we delete all those three . we need to maximise , like this you encountered any other problems ?

            → Reply
»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

This seems like a specialized variant of Clickomania. The decision problem version (i.e. can it be reduced to $$$0$$$ letters?) of Clickomania has been considered, and it yields a polynomial time solution for $$$1$$$ columns, using dynamic programming. (Forgot the time complexity, should be $$$O(n^3)$$$ or smth)

However, I have not seen any research on the optimization variant. It could be NP, or you might be able to find a polynomial time solution with ideas from existing articles. If it is NP, then the only feasible method should be DFS/BFS, likely with branching.

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

https://codeforces.com/blog/entry/67618

^

→ Reply
»
6 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Deleted

→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Once Errichto was trying to solve a similar kind of problem during his livestream. I think he did not solve it fully.

Spoiler
→ Reply