DEVSTR - Editorial

editorial
, , ,
21

@sunya

I think, here is the problem.

for (int x = 0; x < tmpCount; x++)
{
sequence[i + 1 + x * K] = opositChar;

suppose if k=3,n=13.
0001111111111.

Your o/p would be flips=2
string 0001011101111.

So the string after the flips…will be contradicting the condition(more than k consecutive characters not allowed).

                                                                                       REGARDS.
22

@shivam9753
would be much grateful if you could address my previous query also ^

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.CodeChef: Practical coding for everyone 2.ShqsUA - Online C Compiler & Debugging Tool - Ideone.com(in case link 1 doesn’t open) thanks in advance. P.S.-my solution got partially accepted

thanks in advance :slight_smile:

23

@oldschool

I think its faulty implementation.
You cant flip anywhere.
Do it as follow.

Count the consecutive 1’s or 0’s if they are greater than K, name it K1.(K1>K)

If K1 mod K not equals to 0

flip every K+1th character.

Else if K1 mod K==0

Start with flipping kth character first

then flip every (k+1)th character.

24

hmm thanks very much @shivam9753,i had understood the editorial in quite a different way and thanks for rectifying that error
i still have one thing in my mind if you would be so kind to clear them too…
actually i’m not flipping anywhere,i flip when in a continuous substring count >=k
Case 1: count>k at a character “inside” the substring(i.e a character not the last character of the substring),in this case i flip the current character,count is reset to 0
Case 2:count>k at the last character of substring,in this case the previous character is flipped(we should avoid flipping the last character of substring right?),count again reset to 0
eg.-in 00000011,k=2,the 0s at index 2 and 4 will be flipped(edited substring-00101011)
so in which way/case/path can this method go wrong?
thanks very much again

1 Like
25

@old_school
Great to see that you are still trying to do the hair-skin test of the problem even after getting 100 points :).
Your case1 and case2 are quite not clear to me,although this approach seems to be correct.

26

yeah thanks @shivam9753 for helping all along,those 100 points i had got were implementation of my friend’s logic who had got AC with 100 points,but i was still unsatisfied with my code not being AC and so tried that again,anyways looks like i’d have to just give up on the code and move on
thanks once again :slight_smile:

27

@shivam9753 my solution with comments if you are not already annoyed/irritated/bored :stuck_out_tongue:
http://www.codechef.com/viewsolution/6993607
thanks in advance

28

@old_school

Just do one thing.
dont break the while loop when count becomes greater than k.
Let it go untill (a[i]!=a[i+1])

Now suppose your count =20.
And your k was 5.

now check whether count%k+1 ==0 or not.
If not then make changes at 6,12,18.

second case :your count =20.
And your k was 3.

here (count)%(k+1)==0
so you can make change at 3rd, followed by 7 11 15 19.(last character not flipped).

29

@shivam9753
yeah thanks very much but that’s what’s exactly written in editorial,so i guess that might be the only way to go and my implementation might be go wrong at some higher test cases
thanks:)

30

I am getting the right answer for all the test cases but still it is giving wrong answer. Can someone please look at my solution and tell me what I am doing wrong. Thanks in advance.
Solution link: CodeChef: Practical coding for everyone

31

@sakshamsingh Your cause of error is you are not terminating the a and b arrays.Just after the for loop add a[i]=‘\0’; and b[i]=‘\0’; because string termination wont take place and if for a test case where k=1 your code gives wrong output when more than 1 test case is processed at a time. Here is your accepted version of code- http://www.codechef.com/viewsolution/7062721

32

can someone find my mistake in implementing the above algo
http://www.codechef.com/viewsolution/7062711

33

@mohit0749 you have not given \n in case you print s1 so be careful as your output wont match. Here is half accepted version of code.http://www.codechef.com/viewsolution/7062982

34

Thanks a ton @apptica

35

Thanks for helping @apptica
but why my solution not getting fully accepted

36

@mohit0749

bad_allocation

37

@mohit0749 check whether you are accessing the strings properly or not. It seems to be error in the loop in case when k>1 you are running a loop from i=1 to n which is accessing s[n] also. When i make it strictly less than n it gives WA but a SIGABART in the last subtask is reduced. You try it i.e. check whether all the strings and arrays are accessed properly or not.

38

@mohit0749

your iterative variables going out of bound.

39

please check why it is giving WA CodeChef: Practical coding for everyone I have checked all possible test cases,it is running fine on my machine

40

Hi,

can anybody explain a DP solution for this problem?