Help me!!!

I’m trying to solve this problem : http://www.oi.edu.pl/old/php/show.php?ac=e180911&module=show&file=zadania/oi10/sum
It’s a nice problem, but I can’t know how to solve this problem.
I try to read the solution but it’s in Polish, so it’s really hard to read.
I just know we must use Dijkstra to solve this problems.
Could anyone help me to solve this problem?

P/s : Sorry for my bad English

can you give the link to it’s solution?

Polish is very hard language - I know. Imagine the graph with a1 vertices. Let’s number them from 0 to a1-1. They are remainders modulo a1. Now - edges : for each pair(element in A, remainder modulo a1) - let this pair be (x,y), we add edge from y to (y+x)%a1 with cost = y+x/a1 (integer dividing)
Now if we want to find out if b is in A’ just look in vertex b%a1 if it’s distance from 0 is less or equal to b/a1. I don’t have time know to explain why that works, but if you want an explanation just write me. Rate if you liked it.

1 Like

@gvaibhav21 : http://www.oi.edu.pl/old/download/oi10.pdf, you can find it at page 115, the name of problem is Sumy ^^

Could you tell me more about that? And the edge is undirected or directed?
Thank you very much!!!

Yeah. Of course.
The edges are directed and the cost is not y+x/a1, but (y+x)/a1 - sorry for that.

The intuition behind that is : each number x is in the form k*a1 + l, k and l are integers and l < a1.
Actually it means that x/a1 = k, x mod a1 = l.

Another interesting fact is that if we can reach number x we can reach x + a1 too.

So if we want to find out if number x is in A’ we just check iff distance from 0 to l = x mod a1 is not greater than k = x/a1.

If distance is lower or equal , than x is in the set(A’). If it is greater than x is not in the set.
For example : A = {5,11,14,16}
Than we have 5 vertices because a1 = 5.
0 1 2 3 4
11 = 1 mod 5, 11/5=2
14 = 4 mod 5, 14/5=2
16 = 1 mod 5, 16/5=3

for each pair(element in A, some vertex) - let this pair be (x,y) :
we add an edge with cost (x+y)/a1 from y to (y+x)%a1.
We can omit the edges from a1, because they have no sense at all. (0->0).

From 0 we have 3 edges : 0 -> 1 (cost = 2), 0 -> 4 (cost = 2), 0 -> 1 (cost = 3).
From 1 we have 3 edges : 1 -> 2 (cost = 2), 1 -> 0 (cost = 3), 1 -> 2 (cost = 3).
From 2 we have 3 edges : 2 -> 3 (cost = 2), 2 -> 1 (cost = 3), 2 -> 3 (cost = 3).
From 3 we have 3 edges : 3 -> 4 (cost = 2), 3 -> 2 (cost = 3), 3 -> 4 (cost = 3).
From 4 we have 3 edges : 4 -> 0 (cost = 3), 4 -> 3 (cost = 3), 4 -> 0 (cost = 4).

Than we just run dijkstra from 0.
Distances from 0 :
0 : 0
1 : 2
2 : 4
3 : 6
4 : 2

Now some checking :
x = 11 ? x%5 = 1, x/5 = 2, distance to 1 = 2. 2 <= 2 so it is in set (btw. that was obvious, 11 is in A)
x = 28 ? x%5 = 3, x/5 = 5, distance to 3 = 6. 6 is not less or equal than 5, so 28 is not in A’

I hope it helped.
Don’t forget to rate it and mark it as solved if you liked it.

1 Like

It’s very nice method ^^
Thank you very much!!!

got AC, but I have a question : let’s call d[u] is the minimum path from 0 to u, then what does d[u] mean? Is it the minimum value that d[u] * a1 + u exist?

Yeah. That’s what it means
Because if d[u] * a1 + u is in the set, than for all positive integers k : (d[u]+k)*a1 + u also is in the set.

And if you want to submit problems from Polish Olympiad in Informatics just go to http://main.edu.pl/en/archive

Thank you very much!!!