Have you tried compiling your code with the -O2 flag? If not, compile this way:
g++ -O2 filename.cpp
Also, you can check the number of operations you had to to by making a global variable in the program. Like in my case, my solution is not a perfect N^3, nor N^2 * logN. It’s somewhere between that, more towards N^2 * logN. On testing my code on random input, I got a time of 0.30 secs and number of operations ~ 1.02 * 10^6 when number of test cases are 5 and N in each test case is 1000, A[i] less than 10^9. On limiting A[i] to <= 1000 for repetitions, the code ran in approx 0.87 secs with about 5.1 * 10^6 operations per test case. On further limiting the values to <= 100, the time got to 1.01 secs for the file, with 11.5 * 10^6 operations per test case. On further reducing the values to <= 10, the number of operations increased to 13.5 * 10^6 per test case, however the time improved to 0.75 secs per file. This was because the smaller the numbers are, the lesser is their access time. We can also see that the maximum operations per test case in an improved N^3 is a maximum of about 14 * 10^6, and for 5 test cases, it goes to about 7 * 10^7 per file, and hence codes like this should pass in 0.7 secs approx, whatever the input may be.
My code: Submission 10777456 CHSGMNTS
Also, I have made N^3 submissions to the problem, which gave a TLE everytime.
1 Like
In my opinion, the test cases were not weak. My solution(JAVA) was O(n^3) in worst case if all elements were different. I tested it on my machine and it took around 2.8s for T=5 and N = 1000, for all test cases with no same element in array. It ran under 2s if the test cases had few same elements in the array.
Even I saw many people with O(n^3) solution(for all test cases and not just worst case) AC in C/C++. Will try submitting my solution in C++ and see if its AC. It was frustrating to see others with same solution getting AC due to difference in choice of language.
Here is the link to my solution: CodeChef: Practical coding for everyone
I do think the test cases are weak. Here’s my O(n^3) code that passed. CodeChef: Practical coding for everyone
for me the longest task required .43 seconds while my
[1] is in java.
I tested my code for different inputs and the maximum time it took for 1000 elements and single test
case was 0.16 seconds on my local computer.
[1]: https://www.codechef.com/viewsolution/10802927
Mine took just 0.08 sec for the longest task… coded in C… underlying algorithm i devised although is of complexity O(n^3)…
I managed to device one algorithm which in most of the cases could use the pre-calcualted values from the table… so. the inner most for loop comes not often…
However its not fully dynamic programming… but most of the part resembles dynamic programming…
To put it into clearly… its some kind of mixture of dynamic programming with less contribution of backtracking…
According to CodeChef, the longest task required 0.64 seconds.
Thanks for the tip about -O2! However, while my code is now under one second for one test case, when I add five test cases that are the same, it now takes about five seconds to complete, so I think CodeChef did not have a subtask with five test cases and all test cases having N=1000 and same elements each time.
Can’t comment on that. I would suggest you to not run the code on your computer but some IDE like code.hackerearth.com or maybe codechef IDE. This is because the runtime in a PC is determined by various factors, like background processes, etc. After running on an online IDE, note the time. This time will be more close to the real codechef time.
I find many parts of your code a bit weird. For instance, you typedef’d long long to “test_cases”? ._.
That’s a good idea! I ran it on CodeForces and it told me it took 3010 milliseconds against this subtask, so I should’ve TLEd. Yours, however, only took 186 milliseconds.
Interesting. Thanks for sharing!
At first, my algorithm was similar to this (O(N^3) all of the time) and it also did not pass in C. However, I have also seen O(N^3) all of the time solutions pass AC and I think the reason they pass is because they are simpler than most solutions, which means they have a low constant, and because they use the STL, which is very optimized.
@mightymercado No, I did typedef long test_cases and typedef long num so I could differentiate between variables that hold numbers and the test_cases numTestCases variable. I also did typedef long long num_nums because num_nums is the answer type for the number of disjoint intervals. I do this typedef stuff a lot because it makes it easier to keep track of my variables.
@kishu_invain_1 Can you provide a link to your code?
How to provide it?>
let me paste it over here
I thik you couldn’t get the underlying algorithm i used by having a look at my code…
but i will paste my code here…
kishu_invain_1 and kishore1… both are same…
actually… when i was participating in july long challenge i was in that account… now as having two accounts is against code of conduct of codechef…i informed it to codechef help desk…
seems that… mine is the fastest solution for this problem 