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?
Thank in advance!!!
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.
@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.
If not than ask me about the thing you don’t understand.
Don’t forget to rate it and mark it as solved if you liked it.
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!!!