### yashi's blog

By yashi, history, 4 years ago, ,

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 .

• +7

 » 4 years ago, # |   +12 I didn't read your code but try this test case:15 211111your code prints 1 instead of 2 ,I hope it helps you.
•  » » 4 years ago, # ^ |   +1 Ya, that's right. Thank you, I'm trying to fix it now.
 » 4 years ago, # |   0 Auto comment: topic has been updated by yashi (previous revision, new revision, compare).