PROBLEM LINKSDIFFICULTYHARD PREREQUISITESSimple Math, Dynamic Programming, Shortest Path Problem PROBLEMYou are given N types of coins. The i^{th} type of coin has the value V_{i} and the color C_{i}. You have an infinite number of each type of coin. You have to answer several queries of the following type
You just have to report the number of distinct colors in such a selection. QUICK EXPLANATIONLet us look at a much easier problem and work out a solution. The solution to that problem would give several insights into how to solve this problem. Ignore the requirement to optimize the number of colors used. Now, the problem reduces to finding whether it is possible to choose coins whose values sum up to exactly S, or not. This can be done through use of some clever math, as below
Now, consider a table
The benefit of such a table is that to test a target value S, we can
Note that such a selection only tests for possibility, but not optimality. The quesiton arises, how do you construct the table DP? EXPLANATIONLet us iterate over all the values v in V  { V_{1} } For each x, which is a residue modulo V_{1}, we can update DP(x + v) by DP(x) + v, if it is smaller. This looks eerily similar to the Shortest Path problem.
Since we need the shortest distances to all vertices from 0, one way we can do this is by using Dijkstra's shortest path algorithm. But, we will look at the Bellman Ford shortest path algorithm. Let M = V_{1} repeat M times for all v in V  { M } for x = 0 to M1 relax( DP( (x+v) % M ), DP(x) + v ) But this is very inefficient! That is because, we assume no guarantees of the order in which we are encountering edges. If we could access all the edges in simple paths / cycles, we would have been able to trigger the relaxations from the right vertices and along the paths. For this problem we are going to essentially do what the Bellman Ford algorithm does in the manner of relaxing over the edges, but we will do this in a very optimal order of edge selections; due to which, we are able to accomplish the same result the naive algorithm would in much lower complexity. Let us look at the interesting trick to target the best complexity class for our solution. We know that we need to call
for all x between 0 and V_{1}1 and for all v in V  { M } Firstly, we can consider all the edges for each v separately and never consider it again. This is due to the property of this graph that
Thus, we consider v in some order and process all edges for each v in bulk. There is an interesting property in the relaxations we want to perform for some v. The edges are arranged in several disjoint cycles. In this case, we can consider each cycle independently and start with the vertex that has the shortest distance till now. From this vertex, we update the distances to all the vertices, onwards in the cycle. This way, we never have to visit those edges again! Let us elaborate
From elementary number theory we know that (x + kv) % M goes through as many as M / gcd(M,v) residues. Thus, we can establish that we need to consider only those gcd(M,v) cycles that contain the first gcd(M,v) items respectively. Thus, Let h = gcd(M,v) for i = 0 to h1 Let S = {} for j = 0 to M/h S union ( (i + v*j) % M, (i + v*(j+1)) % M ) /* notation: ( tail, head ) */ Find the vertex y with shortest distance from 0 from the set of vertices in the cycle S consider edges e in cycle S, starting from vertex y relax( DP(e.head), DP(e.tail) + v ) The above step is of complexity O(M). Thus the algorithm is of the complexity O(M*N). Accounting for colorsFirst, realize that no matter what range for C, we only ever worry about N unique colors. Now, we can maintain N DP arrays similar to how we describe above.
We can relax DP( k+1, (i+v)%M ) with DP(k,i) when using v, which is of a new color. To take care of not undercounting the colors we can construct the new DP in decreasing order of k. for k = maxK1 to 0 for each v in V for x = 0 to M1 relax( DP(k+1, (x+v)%M ), DP(k,x) + v ) call procedure described previously to relax all the values within the same k using V Now the answer for a query S is the largest K such that DP(K, S % M) ≤ S. The overall complexity of this approach is O(N*N*M + Q*N). SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 13 Mar '13, 05:15

My algorithm is at least O(N * N * min(V1, ... Vn)), but may have a big constant factor. All comes from the fact that I use a BFS instead of simple 'relaxation' approach as in the official solution, the closest reference I know is answered 14 Mar '13, 04:24

We have 3 tests where N=30 and all colors are different: I see now that we should pay more attention to such tests by adding at least several random tests. answered 14 Mar '13, 04:58
