I recently came across this blog post and decided to try some of its problems. I am stuck on this problem. I can think of a naive O(n^2) solution by iterating through all pairs but do not see any redundancy in this solution. I cannot see a way to make it sub-quadratic (other than using the fact that 1 ≤ ai ≤ 2.5 * 10^6, maybe?). Any hints would be appreciated.
Auto comment: topic has been updated by Neev4321 (previous revision, new revision, compare).
Actually, $$$O(n^2)$$$ is intended, however, not in the way you might think. If I recall correctly, as soon as 4 pairs of the same sum are present, there is always a way to choose 4 different indices among them. For larger
n
,n^2
solution will end up finding the solution without checking all the pairs, which makes it $$$O(min(n^2, C))$$$, where $$$C$$$ is a large, but not enought to TLE number.Do you mean that I should randomize the pair selection? Because If one uses a deterministic strategy of going through all pairs and quitting early when a solution if found, you can always create a worst case scenario counter test where there is only a single quadruplet answer and one of the pairs of that quadruplet is the one that you consider last in your strategy.
that will work good but think about it, in the worst case each pair gives you a different result but you have at most 5e6 possible sums of pairs so that means 5e6 sums to check so its still fast (im ignoring the fact that some of the equal pairs can have common elements but i think it changes the upper bound by not much)
I see now, thx. So, the bound on ai combined with the fact that "as soon as 4 pairs of the same sum are present, there is always a way to choose 4 different indices among them", gives an upper bound of 2 * 10^7.
after doing a lot of casework, youll be left with a case where all elements will be distinct. now run an (i,0,n)(j,i+1,n) loop some min(n^2, 5* 1e6 + 10) times. if a sum repeats nice. but in 5 * 1e6 iterations if you did not you can only have 5 * 1e6 distinct sums so pigeonhole or common sense any sum after these iterations is a repeat. keep in mind that if you encounter a sum twice, the previous sum indices [x, y] and currently [i, j] x < i && j < y always follows. (sorted distinct elements)
Actually there is no need for casework to remove duplicates, you can incorporate duplicates into your main strategy. Here is my code.
mine