jugal_sahu's blog

By jugal_sahu, history, 9 years ago, In English

I was reading editorial editorial for problem here.There was a problem link here and editorial for that here. I got what is written in editorial but don't know why that works.Can anybody comment on correctness of algorithm.thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Firstly note that C mod X1 is less that 10^6. So now create 10^6 nodes starting from 0, 1 ... to 10^6 — 1. Now for every node add an edge for every bucket i.e for node numbered i adding an edge of bucket j means adding edge between i and (i + bucket[j]) % X1. So adding edges like this we get X1 * (number of buckets) number of edges. Now basically our problem is reaching from 0 to C mod X1. So apply djikstra's algorithm with 0 as root and find the shortest route to C mod X1. If the value of shortest path is less than C then clearly we have a solution as coefficient of X1 could be increased appropriately, otherwise there is no solution as the shortest coefficient of X1 would have to be negative which is not allowed