Why does this solution time out ?

Revision en1, by chari407, 2018-05-06 09:06:06

This is my submission for Mollys Chemicals. Can someone tell me why it times out ? I calculated the Time complexity as follows — please correct me if I am wrong. 1. The preProcess function would work in O(46 log(46)). 2. The prefix sum computation takes O(n); 3. The subarray generation part (in the while loop) takes O(n^2 * log(46)) . (Because the set size would atmost be 46).

So adding them, O(46 log(46)) + O(n) + O(n^2 * log(46)) and with the constraint over n as 10^5, 46*5 + 10^5 + (10^10)*5.

Assuming 10^9 operations per second, the time limit given for the problem is 2.5 secs which means 10^27 operations can be allowed. Then why does my solution give TLE?

Please help me.

Tags #timelimit

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English chari407 2018-05-06 10:10:48 10 Tiny change: 'ich means 10^27 operation' -> 'ich means *2.5 * 10^9 operation'
en1 English chari407 2018-05-06 09:06:06 849 Initial revision (published)