KFOLD - Editorial

editorial
, , , , , ,
42

Hey there! my logic is same as that given in editorial but still getting wrong answer this is my code
If someone could tell the test case where it is failing,
I would be highly grateful

43

It has been told to provide lexicographically smallest string. So it is possible that

  1. When N==K, It is not smallest string.
  2. Same applies here, Given string might be K-fold but not lexicographically smallest. Hope this helps.
1 Like
44

Your code is printing strings starting with ‘1’ then ‘0’, but we need lexicographically smallest strings, i.e first ‘0’ then ‘1’.

45

In the last FOR loop just swap the conditions for if-else statements, it should work. because it has been told to answer lexicographically smallest string. Yours is not the smallest.

46

I don’t know what’ s wrong but if I try to give multiple testcases like

45
5 5
11100
… (here comes the next input)

fiist testcase will not print anything (according to my ide, check yours)
But this works

1
5 5
11100

maybe there is some problem with I/O

47

Doesn’t the 2nd point contradicts this statement ?
(possibly leaving this string unchanged)
This was the only reason i was not able to solve this problem, just some problem statement confusion.

48

s = 10011001, k = 2;
What will be the answer according to you ?
I think it should be :
10011001 not 01100110

49

both the strings 10011001 and 01100110 are k-foldable, but as it is mentioned in the question, in case there exist multiple answer you have to provide lexicographically smallest string. So the answer would be 01100110 and not 10011001.

1 Like
50

hello brother… i solved this problem during contest but i also want to know your logic behind your code. can you explain please?

51

Thanks a lot buddy, it worked didnt read lexiographically

52

Thanks a lot buddy, it worked, didnt read lexiographically

53

this is my final AC code which is using the same logic as my previous submission CodeChef: Practical coding for everyone .
My logic -

  1. Store the num of zeroes and ones of the given input string( str)
  2. Lets divide the string into n/k partitions each of size k. (let them be S1 , S2 … )
  3. According to the given operations, S(i) and S(i+1) are mirror images of each other.
  4. So i will make a pattern which will be used to cover str[1] to str[k] (assuming 1 based indexing)
  5. Now we first try to put first letter of pattern as 0 . If countZeroes >= n/k , it is possible . Otherwise we try to put 1 over there. That is possible if countOnes >= n/k. Otherwise we cant put anything and its IMPOSSIBLE ( flag variable takes care of this ). Of course i will update CountZeros and COuntOnes . (countZeroes -= n/k , and same for countONes).
  6. Final string will be n/2k time concatenating this pattern. If one partition still remains( i.e. n%k !=0 ) , then take the second half of this pattern. Reverse it and then append to final string.
  7. Print final string as output.
54

Thanks bro. That was also a good idea. :grinning: I didnot think of that.
Have a look at my code. I hope you like it.
https://www.codechef.com/viewsolution/37138568

55

That’s because of fast i/o I guess. All the output will be printed after all test cases are typed by the user

56

https://www.codechef.com/viewsolution/37148753
can anyone help,why my solution is giving WA.

57

On line 21, you have written print(s) instead of print(''.join(s)). I think it should work once that is changed.

58

That was a really good explanation . Thanks :smiley: