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.