# 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, C^{2},… 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 **K ^{th}** 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/C**notes of value^{2}⌋ % C**C**^{2} - …

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 **K ^{th}** binary number, which has

**exactly S**

*ones*.

Using elementary combinatorics, the number of **n digit binary numbers** whose digit sum is exactly **S** is ** ^{n}C_{S}**. 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

ndigit numbers (in base C) whose digit-sum iss.

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

G

_{S}(M) = how many numbers ≤Mhave digit sum(in baseC) equal toS.

It is clear that G_{S} is an increasing function of **M**, and we want to find the smallest **M** for which **G _{S}(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
```_{S}(mid)>=K) // we maintain that G_{S}(high)>=K and G_{S}(low)< K
high = mid
else
low = mid
answer = high

G_{S}(M) can be computed as:

G

_{S}(M) = F[n-1, S] + F[n-1, S-1] + … + F[n-1, S-X+1] + G_{S-X}(M - X * C^{n-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(=>G_{S-X}(M - X * C^{n-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 X_{1} notes of values 1, X_{2} notes of values C, … , X_{n} notes of values C^{n-1}.

Consider any alternative scheme, which uses Y_{1} notes of values 1, Y_{2} notes of values C, … , Y_{n} notes of values C^{n-1}.

We have M = X_{1} + X_{2} * C … X_{n} * C^{n-1} = Y_{1} + Y_{2} * C … Y_{n} * C^{n-1}.

Let **i** be the smallest index such that **X _{i} ≠ Y_{i}**, then we have

(Y

_{i}- X

_{i}) = (X

_{i+1}- Y

_{i+1}) * C + (X

_{i+2}- Y

_{i+2}) * C

^{2}… (X

_{n}- Y

_{n}) * C

^{n-i}

Now, since **X _{i} < C**, and

**(Y**, we must have Y

_{i}- X_{i}) is a multiple of C_{i}≥ C > X

_{i}≥ 0. Therefore, the number of notes in scheme

**Y**can be further reduced by removing

**C**notes of value

**C**and adding one note of value

^{i-1}**C**.

^{i}We can thus keep reducing number of notes in configuration **Y**, till we reach configuration **X**.