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

Recently I got accepted on the Shortest Routes I problem from the CSES problemset using the Bellman-Ford algorithm. If you don't know what relaxation means in this context or what the pseudocode of the Bellman-Ford algorithm looks like you should study the algorithm before continuing the reading.

Here's my idea for solving the problem

Firstly, I applied the typical optimization when all the edge weights in the given graph are positive, which involves stopping the algorithm once no relaxation operation occurs during an iteration. After getting TLE in 6 cases I thought in a way of ordering the edges in order to take advantage of the latter optimization. Finally, I deleted multi-edges(storing just the lowest weight of the repeted edges) and in a very intuitive manner I run a BFS from the source( node 1 in this case) and I sorted the edges in the same order the BFS had visited them (including back edges). Surprisingly, It passed the tests!!!!

I'm wondering if someone could be so gentle of hacking my solution or explain me why it works. I don't know how to filter by name in the hacking page of the CSES website in a certain problem, however, you can find my submission if you go to the hacking tab in the Shortest Routes I problem and then sort by maximum runnung time, my submission shows up in the 4th page with a max runtime of 0.95 seconds with the username Victor_Luis123. Thanks in advance.