Kaleab_Asfaw's blog

By Kaleab_Asfaw, history, 4 years ago, In English

The problem is this.

I guess it is a common problem. I have tried it solving with binary search.

My Approach
Python Code

Difficulty — TLE

Help Needed — I know python is slow, but there are many peoples solving it with python. My question is how this code can be optimized (especially the valid function taking O(n*k) operations)?

I have seen the editorial, using other methods. But I am learning how to implement binary search, that is why I am trying this way.

Thanks for taking the time for reading this!

UPDATE: Accepted

  • Vote: I like it
  • -3
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

n <= 10^5, O(nk log n), are you serious?

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

To solve this problem you can check binsearch answer faster.

To simplify the solution, you can check every letter C to be k-dominated. So, you need to do binsearch 26 times (for 'a', 'b' etc.)

So, imagine that you calculated the segment [L; L+k) and calculated the amount of letters C in this segment. Then, for the next segment [L+1; L+k+1) you don't need to recalculate the answer — just check elements L and L+k. If every segment has letter C, then it is k-dominated.