yashi's blog

By yashi, history, 4 years ago, In English,

Hello there,

Several days ago I came across this problem 100712L — Alternating Strings II in gym 2015 ACM Amman Collegiate Programming Contest

Given a string S consists of 0's and 1's only, and given K, we define the alternating string is that the string that starts with 0 and then alters 1 then 0... to the end of the string or vice versa starts with 1, for example, 101,01,010 are alternating strings, while 110,0,01011 are not.

1 <= K <= |S| <= 100000, you are to find the minimum number of cuts you have to make to break the string down into non-alternating strings that each of them has at most K digits .

I tried to solve it this way, let dp[i] be the minimum number of partitions that needed to split S as the problem states, assuming the indexing starts with 2 being the first character, and n is the length of the string, then the answer to the problem will be dp[n+1]-1

alt[i] contains the length of the longest alternating string that ends at position i.
Now let dp[1] = 0 and start iterating over the string from 2 to n+1, initially dp[i] = dp[i-1]+1 that we made a cut at position i then let's look at the longest alternating string in the range [i-k,i], let this value be e, if e is less than the length of the range [i-k,i] then for sure this range doesn't form an alternating string, so we look up the minimum value of dp in the range [i-k-1,i-1] and update dp[i] with min(dp[i],minValue+1) .

Here's my code, I keep getting WA I tried to figure out where I'm going wrong but no use, I would be so grateful if someone could indicate what's wrong with this algorithm/code .

Tags dp, gym
 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I didn't read your code but try this test case:

1

5 2

11111

your code prints 1 instead of 2 ,I hope it helps you.

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

    Ya, that's right.

    Thank you, I'm trying to fix it now.

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

Auto comment: topic has been updated by yashi (previous revision, new revision, compare).