Блог пользователя Ahmed_Allawati

Автор Ahmed_Allawati, история, 18 месяцев назад, По-английски
problem statement
Code

I'm solving a problem where I can insert lamps on a street segment [L, R], and later need to answer queries like: “What’s the minimum number of lamps needed to fully cover [L, R]?”

In my solution (which passed all tests), each query walks from L to R using a greedy jump to the farthest lamp covering the current position. In the worst case — like when every lamp covers only one position — this query can walk every single position in [L, R], so O(N) per query.

Since there can be up to Q = N = 2·10⁵ such queries, isn’t the total worst-case complexity O(N²)?

Yet the solution is accepted . Why does it pass if O(N²) time is theoretically possible? Does the test data avoid this case? Or is there something I’m missing in the analysis?

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
18 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

You can EXACLY copy this blog and send it to GPT and you can get the answer:)

»
18 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

It walks in steps of size sqrt(n) so it is actually O(N * N / sqrt(N)) = O(N * sqrt(N))