padfoot1717's blog

Need help to solve this problem from CSES problemset.
By padfoot1717, history, 4 years ago, In English

I am stucked at the problem Shortest subsequence. Can someone kindly explain an optimal algorithm to solve this problem?

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

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

Suppose we partition the string into $$$k$$$ contiguous subsegments such that the letters GCAT all appear at least once each in each partition. Then, it is clear that all $$$k$$$-character strings appear as subsequences.

We can construct such a partition greedily. Find the shortest prefix of the string that contains all characters GCAT, make that one subsegment, then recurse on the remaining string. Note that this might actually partition it into $$$k+1$$$ subsegments, where the last subsegment is ``incomplete''. The last character in each subsegment (besides the incomplete subsegment) also appears exactly once in that subsegment; greedily, if it appeared earlier in the subsegment, then we could have ended this partition earlier.

If $$$k$$$ is maximal, then we can show that there exists a $$$k+1$$$ length string that is not a subsequence. How? We can explicitly construct it as the last character in each of the partitions, plus some character not in the incomplete subsegment (or any character, if there is no incomplete subsegment).

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

    Thanks a lot.

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

    Shisuko Great explanation!
    I have a question. Is it possible to count the number of such subsequences in a reasonable time limit? If possible then what is the approach?

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

    Very nice explanation dude

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

    Can you explain why this is the optimal way?

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

      All strings of length at most $$$k$$$ appear as a subsequence, so the answer has to be at least $$$k+1$$$.

      But, we can actually do $$$k+1$$$. Thus, the minimum is exactly $$$k+1$$$.

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

        Ohh!! We have greedily selected the minimum possible. thanks :)

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

atcoder similar question with editorial

→ Reply