Complexity Analysis - SHTARR

general
, ,
1

Hi,

I recently tried SHTARR problem and I maintained a sorted list of numbers for each block. (Code)

Update (+) : I deleted my previously sorted block and remake the sorted list again

Query (?) : First traverse current block naively & then binary search on other blocks.

I run a test case with following constraints
t=1
n=1000000
q=100000

I was amazed to see the time taken by my code is 107.515 sec and 50715 calls to blockprocessor.

According to me the complexity is decided by update in this code which should at most take O(t*BS*q)

BS = Block Size =1000

which in this test case should not exceed 10e8 operations(Simply copy & comparison) & I thought this should at most take 10sec, at least not more than that even if I consider my CPU frequency not same as server.

Can please someone point out the mistake I am doing :slight_smile:

2

Reduce the block size to, may be 100 or so. 1000 is high if you create the sorted list again.

3

Hello @anushi int r = max(n, l+BS) ; shouldn’t it be min(n, l+BS) in line 28 ?

1 Like
4

Thanks a lot!
Such a stupid mistake I did, It was the sole reason of TLE!

5

100 is not acceptable bcoz that would result in higher blocks and thus more time in query (?) operation and sqrt decomposition always gives best result with sqrt(n) operations consider all way