I know there was a lot of fuss over bad test cases in CHEFTET this competition, but after the competition, we all realized that there were a lot of O(N^3) solutions that ran under time. Do people think this is because of bad test cases or because of O((10^3)^3)=O(10^9) can potentially run under one second time limit if the number of operations per loop is very low?
Personally, I think this could be because of bad test cases because my solution had binary search and DSU so I thought it was O(N^2\log N), but my DSU is very basic, so it could have been unbalanced. There is also an inner while loop on line 119 of my solution which I did not account for in the complexity, making the amortized complexity O(N^3) if there are many duplicates in the array. Therefore, once I realized this (although I only realized it after the competition), I tested it against N=1000 with all A_i=1 and it took about three seconds on my computer, definitely more than the one second time limit. However, on the other hand, this could just be my computer being slower than CodeChef’s servers.
How much time did your solution take to be accepted?
Even the algorithm i devised to program this problem is of O(n^3)…
However, for all 1’s with N=1000, within no time… it’s producing the result as 0…
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
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.
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: https://www.codechef.com/viewsolution/10810203
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”? ._.
I do think the test cases are weak. Here’s my O(n^3) code that passed. https://www.codechef.com/viewsolution/10726768
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.
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…
@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…