PROBLEM LINKS
PRE-REQUISITES
Binary Search, Greedy algorithms, dynamic programming
Problem:
The currency of Dholakpur is in the form of notes of values 1, C, C2,… You always pay any amount of money by using as few notes as possible. You are given the value of C, S and K, and you have to report the Kth amount that requires exactly S notes to be paid, if all amounts are paid using fewest number of notes.
Solution:
For a given amount of money M, the optimal change can be obtained by paying as follows(Justification # 1 in next section):
- pay M % C notes of value 1
- pay ⌊ M/C ⌋ % C notes of value C
- pay ⌊ M/C2 ⌋ % C notes of value C2
- …
Where % represents modulo operation, and ⌊ x ⌋ is the largest integer ≤ x. The above is equivalent to writing M in base C, and summing up the digits.
K=1 subtask
Can be interpreted as: what is the smallest number M, whose digit-sum is S when written down in base C.
It is straight-forward to see that M, when written down in base C, should look like XYY…(i times Y)…Y, where Y = C-1, i = ⌊S/Y⌋ and X = S % Y.
C=2 subtask
Can be interpreted as: What is the Kth binary number, which has exactly S ones.
Using elementary combinatorics, the number of n digit binary numbers whose digit sum is exactly S is nCS. This can be used to first find the number of digits of the answer, then the first(most significant) digit, then second digit, and so on. Find psudo code below.
n = s
while (choose(n,s) > k)
n++
// the ans has exactly n digits in binary representation
ans = 0
for(i = n; i > 0; i--)
if(choose(i-1, s) >= k) // the i-th digit from right can be set as '0'
countinue;
else
ans += 1 * power(2, i-1) // the i-th digit has to be set to '1'
k -= choose(i-1, s) // remove those in which i-th digit was '0'.
s -= 1 // one less '1' to be accounted for
// the new problem is: find k th i-1 digit number whose digit sum is s
K is small
From K=1 subtask, we know that when K=1, the answer is XYY…(i times Y)…Y.
It can be reasoned out that for K=2, the answer would be X’Y’YYY…(i-1 times Y)…Y, where X’=X+1, Y’ = Y-1.
Similarly, for K=3, 4, … i, the answers would be X’YY’YY…(i-2 times Y)…Y, X’YYY’Y…(i-3 times Y)…Y, … X’YYYY…(i-2 times Y)…YY’.
The constraints on K translate to K ≤ i, so the above is sufficient to solve this subtask.
The general solution
Define the following functions:
F[n, s] = number of n digit numbers (in base C) whose digit-sum is s.
Then we clearly have:
F[1, s] = 1 if s < C # the number is s
= 0 otherwise
F[n, s] = F[n-1, s] + F[n-1, s-1] + ... F[n-1, s-C+1] # last digit is 0, or 1, ... or C-1
The above can be used to first find the number of digits, then the first (most significant) digit, the second digit, so on, just like we solved for C=2. Find psudo code below:
//compute F, and find smallest n so that F[n, **S**] >= **K**
ans = 0
for(i = n; i > 0; i--)
thisdigit = 0;
count = 0;
while(count + F[i-1, S-thisdigit] < k) // the i-th digit is more than 'thisdigit'
count += F[i-1, S-thisdigit]
thisdigit++;
k -= count
ans += thisdigit * power(C, i-1) // the i-th digit has to be set to 'thisdigit'
S -= thisdigit
// the new problem is: find k th i-1 digit number whose digit sum is S
The problem can be solved in another way, though a bit less efficient:
Given a value of M, let
GS(M) = how many numbers ≤ M have digit sum(in base C) equal to S.
It is clear that GS is an increasing function of M, and we want to find the smallest M for which GS(M) ≥ K. So, we can do a binary search over M as follows:
low = 0
high = 40000000
while (low < high-1)
mid = (low + high)/2
if(G<sub>S</sub>(mid)>=K) // we maintain that G<sub>S</sub>(high)>=K and G<sub>S</sub>(low)< K
high = mid
else
low = mid
answer = high
GS(M) can be computed as:
GS(M) = F[n-1, S] + F[n-1, S-1] + … + F[n-1, S-X+1] + GS-X(M - X * Cn-1)
// nth digit is 0(=>F[n-1, S]), or 1(=>F[n-1, S-1]), or … or X-1(=>F[n-1, S-X+1]), or X(=>GS-X(M - X * Cn-1))
X being most significant digit of M, n being number of digits of M.
Justifications:
Justification 1:
Lets say following above scheme, we use X1 notes of values 1, X2 notes of values C, … , Xn notes of values Cn-1.
Consider any alternative scheme, which uses Y1 notes of values 1, Y2 notes of values C, … , Yn notes of values Cn-1.
We have M = X1 + X2 * C … Xn * Cn-1 = Y1 + Y2 * C … Yn * Cn-1.
Let i be the smallest index such that Xi ≠ Yi, then we have
(Yi - Xi) = (Xi+1 - Yi+1) * C + (Xi+2 - Yi+2) * C 2 … (Xn - Yn) * C n-i
Now, since Xi < C, and (Yi - Xi) is a multiple of C, we must have Yi ≥ C > Xi ≥ 0. Therefore, the number of notes in scheme Y can be further reduced by removing C notes of value Ci-1 and adding one note of value Ci.
We can thus keep reducing number of notes in configuration Y, till we reach configuration X.