PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
This problem asks you to find out the Frobenius number for given n values. In mathematical terms, we need to find the greatest number M which does not have a solution to the following equation :
Sum(ai*xi ) = M with ai>=0, ai belongs to the integer set.
There are many ways to find the Frobenius number, but probably an easier and reasonably efficient solution is to model this problem into a shortest path problem. Lets denote the minimum of xi’s as X. We build a graph with X number of vertices where vi denotes the set of numbers y with y%X = i. For any pair (vi,vj) , there is a directed edge between vi and vj if for some k, (vi + xk)%X = vj with the weight of the edge being equal to xk.
We can see that if we consider any path with v0 as start vertex and weight w, it can only end at one vertex ( no matter the combination of edges taken ) = vertex numbered as w % X.
Let Sv denote the weight of any shortest path from 0 to v in this graph. Suppose that M ? v (mod X ). Then we assert that M is representable as Sum(ai*xi) if and only if M ? Sv . We know that v ? Sv (mod X ). If M ? Sv , then M is representable in terms of A because M = Sv + ba1 for some nonnegative b.
The largest nonrepresentable integer congruent to v (mod X ) is Sv ? X. Hence, we can take MAX(Sv-X) for all vertex v to get the largest number not representable as Sum(ai*xi).
Also notice that with the shortest path calculation, we can answer any query for some M in O(1) now. We just check if M>=S(M%X), if yes, then its possible to be represented as Sum(ai*xi) else no.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.