Mikasa's blog

I've found a O(N) time complexity solution on Educational Codeforces Round 120 (Rated for Div. 2).
By Mikasa, history, 2 years ago, In English

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 2 seconds. 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: 140804991 this solution works in 15ms and its memory is 176kb

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

Thanks for reading :).

  • Vote: I like it
  • +46
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Mikasa (previous revision, new revision, compare).

→ Reply
»
2 years ago, # |
  Vote: I like it -27 Vote: I do not like it

I'm going to be that guy and point out that this is not technically O(N) because the modular inverse runs in logarithmic time.

→ Reply
»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I'm faster. 140828665

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Same here 140783017

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think it is designed to let the following solution pass: for $$$x$$$ from $$$1$$$ to $$$k$$$, count the way to rearrange the array when we move exactly $$$x$$$ number ones. Each version of $$$x$$$ needs $$$O(n)$$$ time complexity.

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Does anyone know an O(n^2) solution?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i thought its time complexity is o(nlog998244353) since you calculate nCr with inverse modulo. can you explain how does that code work in o(n)?

→ Reply