How to solve this problem efficiently http://main.edu.pl/en/archive/oi/10/sum ? The time limit is 1 s (for 100 p) and the grading machines are quite slow.
In Looking for a Challenge there is a solution which time complexity is O(a_1*n*log(a_1)), but with a1 = 50000 and n = 5000 I don't think the solution is fast enough.
Also here: http://www.oi.edu.pl/old/download/oi10.pdf the time complexity seems to be something similar, though I don't know Polish so I'm not sure.
I came up with a bit different solution O(a_n*n) (also considering a graph but now with a_n nodes and edges with length of 1 and 0 depending if the go past the 0 mod a_n or not. I don't think it is important to describe the solution more here.) solution and also a O(a_n*a_n/32) solution using bitwise operations. But the first solution is too slow and I don't think the problem should be solved using bitwise operations.
Here is the solution in Looking for a Challenge:
Consider a graph with nodes representing values mod a_1. Then we want to find the shortest path to each node from node 0 mod a_1. This can be done using Dijkstra's algorithm.
Maybe there is again some trivial thing that I cannot see...
I solved the problem using Dijkstra on the graph of numbers mod a_1 and it got me 100 points without any optimizations on my part.
Here is my code.
I think I figured out what the problem is. Your complexity analysis is wrong. Dijkstra complexity is O(|E| + |V|log|V|) and not O((|E| + |V|)log|V|) as you have done.
Edit: This complexity is using Fibonacci heaps. Other methods have different complexities but better average case runtimes. Refer here for more details.
Oh, I just copied that complexity from the book and didn't think it much since I thought that in would anyway be slower than my O(a_n*n) solution. It seems that in every test case in main.edu.pl, the value of a_1 is always quite small. For example 8000 in the hardest test case... So that's why dijkstra is so much faster :D
Why does the solution have to be mod a_1? If an arbitrary modulus larger than a_1 were chosen, what would change about the solution? Is choosing the mod to be a_1 only to prevent TLE or is there another reason for it?
I know Polish and the solution is pretty the same as you describe. Here — http://oi.edu.pl/static/attachment/20110811/oi10-dysk.zip — you can find authors' codes.