PROBLEM LINKS
DIFFICULTY
HARD
PREREQUISITES
Simple Math, Dynamic Programming, Shortest Path Problem
PROBLEM
You are given N types of coins. The ith type of coin has the value Vi and the color Ci. You have an infinite number of each type of coin. You have to answer several queries of the following type
- Among all the ways of choosing coins whose values sum up to exactly S
- How would you choose coins such that the number of distinct colors among the chosen coins is maximum
You just have to report the number of distinct colors in such a selection.
QUICK EXPLANATION
Let 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
- Let V = { V1, V2 …, Vn } be the values of the n coins.
- Without loss of generality, we can assume that V1 is the smallest value in V.
Now, consider a table
- DP( 0 … V1-1 )
-
DP(i) = smallest sum that can be built from values V - { V1 } such that
- DP(i) % V1 = i
The benefit of such a table is that to test a target value S, we can
- Given d = DP(S % V1)
-
if S < d
- the smallest value that could be constructed from all other values is larger than the given value
- hence, S cannot be constructed
-
if S = d
- S can be constructed using all the other values
-
if S > d
- S can be constructed using all the other values
- plus, V1 as well (to meet the remaining deficit)
Note that such a selection only tests for possibility, but not optimality.
The quesiton arises, how do you construct the table DP?
EXPLANATION
Let us iterate over all the values v in V - { V1 }
For each x, which is a residue modulo V1, we can update DP(x + v) by DP(x) + v, if it is smaller. This looks eerily similar to the Shortest Path problem.
- We can think of the residues as graph vertices
- and |V - { V1 }| * V1 edges, that depict using a value v to jump from x to x+v.
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 = V1
repeat M times
for all v in V - { M }
for x = 0 to M-1
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
- relax( DP( (x+v) % V1 ), DP(x) + v )
for all x between 0 and V1-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
- if there is a path from 0 to x { v1, v2 …, vk }
- then there is also a path from 0 to k { vP(1), vP(2) …, vP(k) }
- where P is a permutation of { 1, 2, …, k }.
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 some x, we have to consider the edges
- (x+v, x)
- from x+v, we have to consider the edge
- (x+2v, x+v)
- from x+2v, we have to consider the edge
- (x+3v, x+v)
- and so on till we get (x+M-v, x)
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 h-1
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 colors
First, 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.
- DP(k,i) = the smallest value x, such that x % V1 = i and the maximal number of colors used in the representation of x is k.
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 under-counting the colors we can construct the new DP in decreasing order of k.
for k = maxK-1 to 0
for each v in V
for x = 0 to M-1
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 SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.