Hack my solution.....if you can

Revision en1, by StrongerInChaos, 2024-03-20 03:14:56

I solve the problem Sum of Three Values CSES problemset. According to my calculations, the n*n*log(n) solution (n<=5000) doesn't fit within time limit of 1s. So I used a fun fact for optimizing my solution. The fat is that if a<=b<=c and a+b+c=x, it yields that a<=ceil(x/3) and c>=floor(x/3) (that can be easily demonstrated using the method of proof by contradiction).

My solution is as follows: I sorted the array of numbers in non-descending order, then I used two nested for-loops(one from 1 to n and the other from n to 1) for iterating over a and c, respectively, using the aforementioned fact. I exit the loops if a or c stops holding the conditions. Now, for each possible a and c I used a map for verifying that there exists a number b such that a+b+c=x.

I'm not entirely sure what the worst-case complexity of my solution is, so I would be grateful if you could either attempt to hack it or provide a way to demonstrate the worst-case complexity.

Thanks in advance

Tags sort, hack

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English StrongerInChaos 2024-03-20 03:14:56 1113 Initial revision (published)