abhaypatil2000's blog

By abhaypatil2000, 3 years ago, In English

I have these two codes for the recent Codeforces Educational round 99.

AC
TLE

Both of these have a really small difference, yet one gives AC, and the other gives TLE.

I have used vectors, which allocate memory dynamically, (even though it is a function call), but I think reducing the allocations by just 24 is too less to make any difference at all, that too I am allocating a vector of size only 4.

In the case of AC, exec time = 1.5 seconds, where as int TLE case, exec time > 2 seconds.

In the AC case, the func function is called log2(109) = 30 times, and each time one dynamic allocation is done of size = 8 (2 vectors of size 4), total = 240.

Whereas in the TLE case, the func function is called log2(109) = 30 times, and each time 24 dynamic allocations are done of size = 8 (2 vectors of size 4), total = 5760.

Why is such a small difference in allocation making such a huge difference. These differ only by a factor of 24 in memory allocation. Considering the array size of only 8 * 8 bytes, and the memory allocation is very fast, why does this make a huge difference.

I was expecting both to have similar running time, but the reality was quite different, can someone tell me the reason.

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