Namritaansh02's blog

TLE with sparse table in Problem D of Round#736-Div2
By Namritaansh02, history, 3 years ago, In English

This is the problem. I am using sparse table and implementing it exactly as given in the editorial but I am getting, TLE on test 3. I have been stuck for 2 days now on this:-(

Can anyone point out the mistake? Thanks.

This is my submission : 124743771

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

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Let's look at the last for cycle in your solution. For every i your solution bruteforces all possible values of j (in increasing order). If array is something like this: $$$[2, 4, 6, 8, 10, ..., 2n]$$$ then for every i the correct j is n — i. In total, there would be $$$n + (n - 1) + ... + 1 = \frac{n(n - 1)}{2} = O(n^2)$$$ checks, it is too slow.

Instead of this, you should binary search on j. Then you wouldn't check more than $$$O(n\log{n})$$$ indices, that is much better.

NOTE: You might want to optimize your power function. It works in $$$O(\log{x})$$$, so if you will write binary search, the total complexity will be $$$O(n\log^2{n})$$$. It could also TLE. You can precompute all the logarithms in some array, thus deleting extra log factor.

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

    The power function could also be written like:return 31-__builtin_clz(x); to get rid of a factor of log(n)

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

    Thanks a lot. Really understood well where I was going wrong.

    → Reply