I've found a O(N) time complexity solution on Educational Codeforces Round 120 (Rated for Div. 2).

Revision en1, by Mikasa, 2021-12-27 19:31:34

The reason why I'm writing this blog is that the constraint of N and K is only 5000 also the time limit per test was 2seconds. Wasn't the problem supposed to be solved in like O(NlogN) or O(N^2).

My approach:

First, check if the answer is 1.

Second, for each char in S, I calculate the number of strings that I can generate which differs at the position $$$i$$$.

if char at $$$i$$$-th position is '1' we have to replace it with 0 and all possible solutions which we can calculate in O(1) with a preprocessing. otherwise, if $$$i$$$-th position is '0' we have to replace it with 1 and all possible solutions which we can calculate in O(1) with a preprocessing.

here is my solution: Link.

If you have any solution that's different from mine can you share it with me?

Thanks for reading :).

Tags education round 120

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Mikasa 2021-12-27 19:35:20 87 (published)
en2 English Mikasa 2021-12-27 19:32:09 4
en1 English Mikasa 2021-12-27 19:31:34 927 Initial revision (saved to drafts)