DEVSTR - Editorial

[djdolls]

PROBLEM LINK:

Practice
Contest

Author: admin
Tester: Kevin Atienza
Editorialist: Ajay K. Verma
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng

DIFFICULTY:

Easy

PREREQUISITES:

Basic maths

PROBLEM:

Given a binary string and an integer k, flip the smallest number of characters of the string, such that the resulting string has no more than k consecutive equal characters.

QUICK EXPLANATION:

Handle the case of k = 1, and k > 1 separately. In case of k = 1, the resulting string must have alternating characters, and there are only two such strings (one starting with 0, and the other starting with 1), pick the one which can be obtained by fewer flips. In case of k > 1, partition the original string into substrings made of the same character. If a substring is of length n > k, then flip \lfloor n/(k + 1) \rfloor characters in this substring, so that it contains no more than k consecutive equal characters. Special care must be taken when n is divisible by k + 1
.

EXPLANATION:

We are given a binary string S and an integer k. The task is to flip the minimum number of characters of the given string such that resulting string has no more than k consecutive equal characters.

Let us split the string S into substrings such that all characters of a substring are the same, e.g., if the original string was “1100000011100101”, then the partition would have 7 substrings: “11”, “000000”, “111”, “00”, “1”, “0”, and, “1”. Now, any substring which has a length greater than k, will require some flips, so that after flip we can further split this substring into smaller substrings of equal characters, and of length not exceeding k.

For example, if a substring is “000000000”, and the value of k is 3, then we need to make two flips into this substring to convert it into “000100010”, which can then be split into “000”, “1”, “000”, “1”, “0”, none of which have a length higher than k = 3.

In fact, if a substring is of length n, then we need to make exactly \lfloor n/(k + 1) \rfloor flips to break it into substrings of length not exceeding k (we flip each (k + 1)-th character of the substring). However, there is one tricky case, when n is divisible by (k + 1). In this case, we would end up flipping the last character of the substring, which would increase the length of the substring following this substring. For example:

original string: “00011”, k = 2,
substrings: “000”, “11”
After flip: “001”, “11”
After merging back: “00111”

The final string still has 3 equal consecutive characters. Hence, we must make sure that we never flip the last character of a substring. This can always be achieved when k > 1, as instead of the last character, we would flip the second last character of the string, and it will not interfere with the next substring. For example,

original string: “1100000011100101”, k = 2,
substrings: “11”, “000000”, “111”, “00”, “1”, “0”, “1”,
after flip: “11”, “001010”, “101”, “00”, “1”, “0”, “1”,
after merger: “1100101010100101”

Note that, in the flip step, we flipped the second last character of second and third substring, instead of the last one. However, this is not possible in case k = 1, because if we flip the second last character, then it will interfere with the previous substring.

Special Handling of k = 1:

In case of k = 1, there can no two consecutive equal characters in the resulting string, i.e., resulting string must have alternating characters. There are only two such strings of length N: one which starts with “0” and then alternates between “0” and “1”, and the other which starts with “1”, and then alternates. We consider both of these as potential target string, and pick the one which could be obtained by using fewer flips.

Time Complexity:

O (N)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

[alankar63]

It can be done by DP too.

we can have 2 arrays dp0[n] and dp1[n].

dp0[i] implies minimum no of flips required to make the string end with 0.(string end means till ith position).

dp1[i] implies minimum no of flips required to make the string end with 1.(string end means till ith position).

finally we select the minimum of dp0[n] and dp1[n]

my sol—http://www.codechef.com/viewsolution/6889066

[dev987]

where is the mistake in my code

Ideone.com

My concept is also true but it’s not accepted. Why??

[imswapy]

Followed the same approach but still getting WA , can’t figure out what’s wrong with my code… can anyone help me? This is my code: http://www.codechef.com/viewsolution/6975797

[anshuman14021]

Another approach :

For K=1,proceed with the same approach as stated in the editorial.

For K>1 :

For contiguous segments of size less than 2k, flip the middle bit (as that is the minimum number of flips needed to remove a violation from a string of size less than 2k ).If the segment is of size greater than 2K, flip the (K+1)th bit from any one extreme and then process the remaining substring in accordance with these criteria. (This approach if flipping the (k+1)th bit is correct because if you flip any bit before K+1,it maybe not give the optimal answer and if you flip any bit after K+1,it will not remove the violation from the K+1 part).

[old_school]

yeah i followed the same logic,but i guess i went somewhere wrong in implementation, so could you point out the error in my code,you may try running my code against as many test cases because i would appreciate it even more if i could find which test case my code went wrong
http://www.codechef.com/viewsolution/6970007
thanks in advance.
P.S.-my solution got partially accepted

[kuruma]

Hi,

Can the editorialist, or someone else, explain in some detail the general idea of a DP solution?

During the contest I tried to think of one but wasn’t very successful

Best,
Bruno

[priyankpalod]

Hello,

I tried to implement the above algorithm and wrote this code.

http://www.codechef.com/viewsolution/6978550

It works great for whatever input I give but codechef shows WA in all test cases.

It would be great if someone could tell me the mistake.

Regards

Priyank

[shivam9753]

@priyankpalod

Wrong approach.
Check for n=20 k=4
11111111111111110000.

You will automatically end up with knowing what you did wrong.

[priyankpalod]

@shivam9753

Thank you for your help. Got the solution accepted

[curious1ab3]

please
give a test case for k=1 why same logic cannot be applied for k==1 i could not figure out this

[curious1ab3]

please give testcase for k=1

[curious1ab3]

please give testcase for k=1

[rahulkhairwar]

I’m getting a NZEC for my solution to this problem using the same logic, even though it’s working on my computer!
I also tried using the maximum value of n to check if the memory heap gets depleted but that isn’t the case!
can anyone help?
here’s the link to the solution : http://www.codechef.com/viewsolution/6978947

[raj_ankit744]

please point out the mistake in my code.i’m getting AC for 2 subtasks but not for the third one.here’s the link :[link text][1]http://www.codechef.com/viewsolution/6979326

[spagiarri]

curious1ab3: 1010101010110101010101

[ritz987]

Can someone point out where m i going wrong?? http://www.codechef.com/viewsolution/6945758
Its getting partially accepted… I couldn’t think of a test case where it will go wrong

[old_school]

hello i’ve posted a query before(please refer above),i’d used the same logic stated in the editorial,but my solution got only partially accepted,so it must have been some implementation problem,but since past two days i’ve been coding another solution using some other implementation method but its not being successful.
Could anyone please point out the error in my code,you may try running my code against as many test cases because i would appreciate it even more if i could find which test case my code went wrong Links-1.http://www.codechef.com/viewsolution/6970007
2.http://ideone.com/ShqsUA(in case link 1 doesn’t open)
thanks in advance.
P.S.-my solution got partially accepted

[sukkhi]

my code is exceeding time limit…Dont know why??

#include<stdio.h>
#include<string.h>
int main()

{
int cs, n, k, i = 0, j = 0, zero = 0, one = 0,t = 0;

    char str[100][20], temp [6], opr[100] = {0};

    scanf("%d",&cs);
    while(cs)
    {
    __fpurge(stdin);
    gets(str[t]);

    while(str[t][i] != ' ')
    {
            temp[i] = str[t][i];
            i++;
    }
    temp[i] = '\0';
    n = atoi(temp);
    i++;
    while(str[t][i] != '\0')
    {
            temp[j] = str[t][i];
            j++;
            i++;
    }
    temp[j] = '\0';
     k = atoi(temp);
   __fpurge(stdin);
    gets(str[t]);
    i=0;
    while(n)
    {
            if(str[t][i] == '0')
            {
                    one = 0;
                    zero++;
                    if(zero == k+1)
                    {       zero = 0;
                            str[t][i] = '1';
                            i--;
                            n++;
                            opr[t]++;
                    }
            }
            else
             {       zero = 0;
                    one++;
                    if(one == k+1)
                    {       one = 0;
                            str[t][i] = '0';
                            i--;
                            n++;
                            opr[t]++;
                    }
            }
    i++;
     n--;


    }

cs–;
t++;
i=0;
j=0;
}
while(t–)
{

    printf("%d\n",opr[i]);
    puts(str[i]);
    i++;
    }

}
.
.
.
.pls help if anyone???

[shivam9753]

@sukkhi
There are needless operations you used in you code.
There is a better approach.