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

Правка en2, от Mikasa, 2021-12-27 19:32:09

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 :).

Теги education round 120

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Mikasa 2021-12-27 19:35:20 87 (published)
en2 Английский Mikasa 2021-12-27 19:32:09 4
en1 Английский Mikasa 2021-12-27 19:31:34 927 Initial revision (saved to drafts)