Valeri_Stanchev's blog

Interesting problem about strings :)
By Valeri_Stanchev, history, 9 years ago, In English

Hello everybody,

I need your help! Given a string S (|S| <= 10^5) consisting of uppercase letters and an integer K (K <= |S|). Consider a set consisting of all uppercase letters. We are to choose some letters from that set and replace their occurences in S with a star ('*'). Our goal is to make at least one star appear in each substring of length K and we need to do this choosing minimum number of different letters from the set. Output the minimum number of letters and the letters in different lines. If multiple solutions exist, we can print any of them. For example, if S="ABA" and K=2, then we can choose either 'A' or 'B' and receive "*B*" and "A*A" respectively.

Thanks in advance! :)

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

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

OK, it was overkill

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

does O(26 * 2 ^ 26) solution become accept ?

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

    I always take 108 computations per second as a standard worst case for a solution to pass in online judges. So if time limit per test is  > 2 seconds it will

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 5   Vote: I like it -9 Vote: I do not like it

      Shouldn't it be 10^6 in 1 sec? (Although I've seen 10^7 in 1 sec solution pass at times)

      Ref: Competitive Programming 1 [Competitive Programming]

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

        I think you are deducing that by looking at size of array like arr[100000] in code. That is not correct method

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

          Nope I didn't mean that. Competitive Programming 1 states that 'CPU can do 1M operations in 1s' [See pg 18 of the pdf]. I suppose they were trying to be extra careful. Correct me if I'm wrong.

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

            Computers have improved a lot after that book is written.

            Normal computers can do about 3 * 109 bit operations which means something like 108 summations.

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

For each K sized subsequences(there are N — K + 1 of them) find the mask of the letters that does not occur in that subsequence. Lets call them bad subsets.

Afterwards you need to eliminate all the subsets which is subset of one of the above bad subsets. We can do this by somekind of top bottom dp approach which leads to O((2^26 + N)26) complexity. It might be possible to eliminate factor 26. I did not think about it enoubh yet.

→ Reply