 # Bad Test Cases in CHSGMNTS

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

``````
 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.

: 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…