kllp's blog

10th Polish Olympiad in Informatics — Sums
By kllp, 9 years ago, In English

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...

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like 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.

→ Reply