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
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
Hello ,
Same code , only changed to n+5 and AC
I learnt something new today
Thanks a lot @choudhary463 !!
3 Likes
Declaring 10^5 for every test case ---- TLE
Declaring n+5 for every test case ----- 0.18 secs , AC
Interesting …
4 Likes
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
5 Likes
another way to solve is declare only once the array.
solution
2 Likes