I wrote this
(https://www.codechef.com/viewsolution/14335656) for [MAXSEGM](https://www.codechef.com/LTIME49/problems/MAXSEGM/) what is causing TLE.You are making a function to check the uniqueness!!
Also, your algorithm is O(N^3)!! Since N is <= 10^4 , O(N^3) takes 10^12 instructions for N=10,000 (TLE given if instructions more than range 10^8 to 10^9)
Read the editorial to see how you can optimize your approach, the editorial for this problem is really good.
N is of the order of 10^6.
And your solution has a loop inside a loop inside a loop. I didn’t read the entire code. But if you are targeting O(n^2 + some linear) for a 1 sec limit, then it would definitely time out. You can easily solve it in linear time. Just calculate the sum as you move forward and whenever you find a repeated element, just subtract the beginning element from the running sum.
You can look at the editorial https://discuss.codechef.com/questions/103056/maxsegm-editorial
Rule of thumb: Every time check for the maximum value of N in any question. If it is in the order of 10^6 and time limit is 1 sec, then almost certainly, the solution asked is of linear time.
2 Likes
Consider the following test case:
9 1 0 2 5 2 1 9 8 4 70 54 87 60 12 4 7 9 1
If i go by ur approach then the array considered will be 1 0 2 5 2 which is not unique as it contains two 2’s .and i will end up with a wrong answer.to avoid this i wrote the unique function and got tle so that also wont work. How can i optimise my code.
You simple need to maintain a boolean array to see if element is unique or not. No need for loops. See if my solution helps you - https://www.codechef.com/viewsolution/14332401
I went through the editorial and understood their approach of solving the problem in linear time. Although solving in O(n2) also holds good. But the logic behind solving it in O(n) was fabulous.
Vijju123 ur solution was awesome.i understood every bit of it and utkalsinha thanks for your golden rule shall remember it next time.
1 Like
Glad to hear that dear. The only tricky part was understanding the use of “limit” variable, else all was similar to your code. Great job understanding it dear, its not easy to get things just by looking at code ^^
I agree with @utkalsinha. I have solved this question very similar to his approach. It is clean, concise and fast. Just one loop is enough for it. Got it passed in just 0.12 secs. Below is my code:
1 Like