### Mastermind222's blog

By Mastermind222, history, 4 weeks ago,

Problem C

My Accepted Solution

According to me, the time complexity of the above code is O(sum*n*n)(sum= sum of the array passed to the function) and hence should result in a TLE verdict(Correct me if I am wrong).Help me in clearing this doubt. Thanks in advance. :)

• +24

 » 3 weeks ago, # |   0 I think the time complexity is maxSum*n which would be 2000*100*100 =2*10^7 which will pass in the given time constraints.
•  » » 3 weeks ago, # ^ |   0 maxSm*n is the time complexity for the partition function and an additional *n for the iteration I guess.
 » 3 weeks ago, # | ← Rev. 3 →   0 I think this code should give tle for this test case: N=100 , 4 4 4 .....4 2 2(98 times-4 and 2 times-2).
 » 3 weeks ago, # |   +18 Try this test Spoiler100 1428 448 732 1864 1944 60 788 536 1924 1468 1544 1220 104 40 1872 1360 920 1492 1972 1340 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2 2
•  » » 3 weeks ago, # ^ |   0 Yes,recevied a TLE verdict.
•  » » 3 weeks ago, # ^ | ← Rev. 5 →   0 Can someone try to uphack my solution with this? I feel like Mastermind222's solution got hacked because he's passing the vector without reference and hence your sys tests time is 1.6 secs on the other hand, mine is 0.9 secs. I feel like mine will still pass with this testcaseHere is the proofI think that is the case. I get 1.6 secs on my desktop with this test case.
•  » » » 3 weeks ago, # ^ |   +5 Passed in 1263ms on that test case.
•  » » » » 3 weeks ago, # ^ |   +1 Yup I passed with 1.6 secs, I guess passing the vector without reference is the problem
•  » » » » » 3 weeks ago, # ^ |   +5 You are doing approx 2000*100*100*100 ≈ 10⁹ operations, which is on the edge.
 » 3 weeks ago, # |   +4 Yes it should TLE. Weak test cases.A lot of people have done the same.
•  » » 3 weeks ago, # ^ |   +1 Exactly!!!!