TLE for my code but AC for almost same code?

help
, ,
1

Hello guys ,

Today i was solving this problem from november cook off : CodeChef: Practical coding for everyone and it gave TLE and i couldnt find a better method to solve the problem
After the contest , i checked some solutions and was literally shocked to know that both of us have almost same code and he got AC and i got WA

Pls let me know how to optimize my approach

Solution : https://www.codechef.com/viewsolution/27932379on
My solution : CodeChef: Practical coding for everyone

Can someone pls tell me how to optimize my code ?

Thanks !!

3 Likes
2

you are declaring vectors of size 100005 for every test case …
either declare those vectors globally or declare vectors of size ‘N’(because it is given that sum of N over all test cases does not exceed 10^6)

3 Likes
3

Hello ,

Same code , only changed to n+5 and AC
I learnt something new today
Thanks a lot @choudhary463 !!

3 Likes
4

Declaring 10^5 for every test case ---- TLE
Declaring n+5 for every test case ----- 0.18 secs , AC

Interesting … :face_with_raised_eyebrow::thinking:

4 Likes
5

this is obvious because given range of T is 3*(10^5) and in first case your time complexity is O(T* 100005) so in worst case(T=3*(10^5)) you will get TLE …
but in second case your time complexity is O(N1+N2+…+Nt) (where Ni is value of N for i’th test case) and it is given the sum of N over all test cases does not exceed 10^6 i.e(N1+N2+…+Nt<10^6) …

BTW i am talking about simple case so i did’t considered sorting time complexities… you can also prove same for general case :slight_smile:

5 Likes
6

another way to solve is declare only once the array.
solution

2 Likes