Wierd Stuff in 319C — (incremental CHT with sqrt)

Revision en1, by RestingRajarshi, 2019-04-28 10:05:30

I was trying out implementing a incremental version of CHT with sqrt decomposition. I noticed a very wierd thing though. When I made my block size = 350, the code TLEd with >2000ms. However when i made it 351, it passed in 390ms

Here are two sets of submissions that differ in only 1 aspect, the block size.

blocksize = 350 : TLE

blocksize = 350 : TLE

blocksize = 351 : AC(389ms)

This seems very wierd to me, since blocksizes of <350 also give AC(although with more time. blocksize = 200 with AC in 1669 ms). However, its the specific value of 350 that times out.

What could be a possible for reason for this? I am just curious. (As far as i can see, my code does not have any undefined behaviour.)

Tags cht, sqrt decomposition, #code


  Rev. Lang. By When Δ Comment
en1 English RestingRajarshi 2019-04-28 10:05:30 882 Initial revision (published)