Hi, I was going through the solutions for this question Mike and Distributions and wrote this ->Solution<- using some hints from some others solution.
https://codeforces.com/blog/entry/74510
Help me, I can’t figure out why this solution even passes as it would have given TLE. Thanks in advance.
1 Like
Yes, It can in theory give a TLE, but let’s do some calculations.
A single run trough the while loop is \mathcal{O}(n\log n). Given the bounds it would take about 10^5\cdot\log_2(10^5)\approx1.66\cdot10^6 instructions. Given that a computer can roughly do 10^9 instructions per second we can do about 600 runs trough the while loop in a second.
If we want to have an probability of passing a test case of \geq99.99\% then the probability of finding a solution in a single iteration needs to be at least 1-(1-0.9999)^{1/600}\approx1.52\%.
As Abdelrahman_Elhawary mentioned the linked question mentioned: there are a lot of possible unfair sequences, therefore I would guess that indeed the the probability of finding a solution in a single iteration is at least the 1.52\%.
In conclusion:
It could happen that this solution gives TLE. The odds of that happening however are so low that that is likely not going to happen. When a solution is found it is guaranteed to be correct, so the only other option is AC.
P.S. The 10^9 figure and such calculations is how I have been teached them and are not really instruction counts
3 Likes
Got it, Thanks