## UVA Problem 10696 – f91 Solution

UVA Problem 10696 – f91 Solution:

Solving Technique:

This is a simple DP problem (OR, so it looks but there’s a better way). It can be solved both iteratively and recursively with or without memoization. Still it will get accepted. But still the runtime is slow due huge input. So using a faster io may help it get accepted with a better rank.

For the matter of practice i will show all four methods i know of to solve this problem. Codes are given in this order,

1. dynamic programming solution.
2. Recursive solution without Memoization.
3. Recursive solution with Memoization.
4. Shortcut Trickery.
5. Maybe extend the shortcut Trickery with memoization or other technique by yourself ? try it !!

#### Solution explanation:

Here the formula is given, we just need rearrange it and get the recurrence relation,

If N ≤ 100, then f91(N) = f91(f91(N+11));
If N ≥ 101, then f91(N) = N-10.

So from the given statement generating recurrence relation will be,

```f(n) = { f(f(n+11)), if n <= 100
{ n - 10,     if n >= 101
```

Here base case is for any n greater than or equal to 101 is return n – 10. No more recursive call on that.
This can be simplified but i won’t go into that. The codes below will give a better idea.

Now, just create a function named f and use if else or ternary to implement the given relation and it’ll work.

#### Memoization:

Since we’ve found out the recurrence relation it won’t be hard to memoize the code. We can use a memo array to store the already calculated results. We need not change much from the previous recursive solution to memoize it.

Add an if condition in the beginning if the value is already calculated and stored in memo array just return. Other wise when returning just store the return values in memo.

That’s it.

#### Dynamic Programming ( bottom up method ):

Our recurrence relation will never change. Since there is no other function needed we just calculate and store values in memo array. I started from 1,000,000 because the problem statement said an integer may be at most 1,000,000. Just loop through that many times and store results in memo array.

##### Last Solution Trick:

It come to me when i was testing my own inputs. Anything less or equal 100 result in 91. Any greater value results in that value minus 10. Take a look at the code below to get the idea.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

Input:

```500
91
1
5
190
100
101
0```

Output:

```490
91
91
91
180
91
91```

### Code Bottom Up (Iterative) Dynamic Programming:

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10696 - f91
* Type:    Bottom Up (Iterative) Dynamic Programming
*/

#include<cstdio>
#include<sstream>

using namespace std;

#define N 1000000

static int F[N];

int main(){
int n, i;

for(i = N; i >= 0; --i){
if(i >= 101)
F[i] = i - 10;
else
F[i] = F[F[i + 11]];
}

while(scanf("%d", &n) && n)
printf("f91(%d) = %d\n", n, F[n]);

return 0;
}
```

### Code Top Down (Recursive) Without Memoization:

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10696 - f91
* Type:    Top Down (Recursive) without Memoization
*/

#include<stdio.h>

int f(int n){
return (n >= 101) ? n - 10 : f(f(n + 11));
}

int main(){
int n;

while(scanf("%d",&n) && n)
printf("f91(%d) = %d\n", n, f(n));

return 0;
}
```

### Code Top Down (Recursive) with Memoization:

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10696 - f91
* Type:    Top Down (Recursive) with Memoization
*/

#include<stdio.h>

static unsigned F[1000000];

unsigned f(unsigned n){
if(F[n])
return F[n];

if(n >= 101)
return F[n] = n - 10;
else
return F[n] = f(f(n+11));
}

int main(){
unsigned n;

while(scanf("%u",&n) && n)
printf("f91(%u) = %u\n", n, f(n));

return 0;
}
```

### Shortcut Technique:

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10696 - f91
* Type:    shortcut technique
*/

#include<stdio.h>

int main(){
unsigned n;

while(scanf("%u", &n) && n){
if(n <= 100)
printf("f91(%d) = 91\n", n);
else
printf("f91(%d) = %d\n", n, n - 10);
}

return 0;
}
```

## UVA Problem 147 – Dollars Solution

UVA Problem 147 – Dollars Solution:

Solving Technique:

This problem is very very very very similar to uva 674 ( Coin Change ) and uva 357 ( Let me count the ways ). These problems can be used as hint or template for this problem. So if you want to solve on your own don’t look down.

##### In this problem a few key points are,
1. The amount doesn’t exceed \$300.00
2. Exit / terminate program for the input of 0.00
3. Amount can be / is a floating point number
4. There are different values that can be used make up the decimal and the fractional portion
5. Output should be justified with width 6 before printing input amount and width 17 afterwards then the number of ways the amount is made up of.

#### Solution Technique:

Instead of calculating the decimal and the fractional portion separately we can use one method to calculate the count. Since a Dollar can be made up of coins that is, \$1 = 100 cents. So we can just calculate how many ways the coins can be made and that will be the answer.

###### For example,
• \$4.70      =      470 cents
• \$2.00      =      200 cents
• \$6.75      =      675 cents
• \$300.00  =  30000 cents

So we can put all the ways the coins can be divided to an array. Then use that calculate the count. Now whenever we can divide the amount with a specific coin we increase the count. We need calculate for all the specific coins.

Here I have given two codes, they are essentially the same. Only difference is in the second code instead of using an array to calculate the count, I have split the loop to show the calculations.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Compile with C++ to be safe from compile errors although some codes do work with C compiler.

Input:

```0.20
2.00
4.90
6.70
8.45
0.00```

Output:

```  0.20                4
2.00              293
4.90             5698
6.70            19187
8.45            49007```

## Code:

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 147 - Dollars
*/

#include<stdio.h>

#define N 30002

static long long c[N];
static const unsigned coins[] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};

int main(){
unsigned i, j;
float n;

c[0] = 1;
for(i = 0; i < 11; ++i){
for(j = coins[i]; j < N; ++j)
c[j] += c[j - coins[i]];
}

while(scanf("%f", &n) == 1 && n){
// Rounding error fix
unsigned coin = (unsigned)((n + 0.001) * 100);

// 6 width justified including the input amount and 17 width afterwards including count
printf("%6.2f%17lld\n", n, c[coin]);
}
return 0;
}
```

## Code (Loop Split):

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 147 - Dollars ( Loop Split )
*/

#include<stdio.h>

#define N 30002

static long long c[N];

int main(){
unsigned i, j;
float n;

c[0] = 1;

/*
* Loop Split
*/

for(j = 5; j < N; ++j)
c[j] += c[j - 5];

for(j = 10; j < N; ++j)
c[j] += c[j - 10];

for(j = 20; j < N; ++j)
c[j] += c[j - 20];

for(j = 50; j < N; ++j)
c[j] += c[j - 50];

for(j = 100; j < N; ++j)
c[j] += c[j - 100];

for(j = 200; j < N; ++j)
c[j] += c[j - 200];

for(j = 500; j < N; ++j)
c[j] += c[j - 500];

for(j = 1000; j < N; ++j)
c[j] += c[j - 1000];

for(j = 2000; j < N; ++j)
c[j] += c[j - 2000];

for(j = 5000; j < N; ++j)
c[j] += c[j - 5000];

for(j = 10000; j < N; ++j)
c[j] += c[j - 10000];

while(scanf("%f", &n) == 1 && n){
// Rounding error fix
unsigned coin = (unsigned)((n + 0.001) * 100);

// 6 width justified including the input amount and 17 width afterwards including count
printf("%6.2f%17lld\n", n, c[coin]);
}
return 0;
}
```

## 0-1 Knapsack:

This problem can be solved be dynamic programming. Given some weight of items and their benefits / values / amount, we are to maximize the amount / benefit for given weight limit.

##### Background:

Suppose we are thief trying to steal. We got a knapsack with a weight carry limit. We go to a house there are a few items. The items have weights and also resale value. Now with our limited weight in the knapsack and many valuable items to take, we need to maximize our gain. We can do so by trying all items and filling the weight limit.

We will be given a few things as input. Such as number of items, each of their weights, each of their monetary value / cost ( if it represents cost ) and a weight limit. We are to find that by trying all items and the weight limit what is the maximum possible benefit.

If it is unclear the Wikipedia article on 0-1 knapsack may be helpful. I will show the table fill and items taken in the knapsack in another post.

##### Recurrence Relation:

The recurrence relation for this problem follows,

cost[ i, w ] = cost[ i – 1, w ] if, Wi > w
cost[ i, w ] = max( cost[ i – 1, w ], cost[ i – 1, w – W] ) if, Wi <= w

##### Question:
```items | weight | benefit
========================
1     | 6      | 10
2     | 1      | 5
3     | 2      | 7
4     | 5      | 12
5     | 4      | 8
6     | 3      | 6
```

For weight of 10 what is the maximum possible benefit by trying all item?

For this problem max benefit is 26.

The answer is always found in cost[ item_count, total_weight ]
Our item_count was 6 and total_weight was 10.
Here the answer is in cost[ 6, 10 ] which is 26.

## Code:

#### Iterative:

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: Zero one knapsack iterative
*/

#include<stdio.h>

#define N 128

int CostTable[N][N];
int Weight[N];
int Benefit[N];

int total_weight = 10;
int item_count = 6;

inline int max(int a, int b){
return a > b ? a : b;
}

void dynamicKnapsack(){
int i = 0;

/*
* Set each column in first(zeroth) row to zero
*/
for(; i <= total_weight; ++i)
CostTable[0][i] = 0;

/*
* Set each row in first(zeroth) column to zero
*/
for(int i = 0; i <= item_count; ++i){
CostTable[i][0] = 0;

/*
* calculate till required weight
*/
for(int w = 1; w <= total_weight; ++w){
/*
* Get value from row above
* or,
* the value from a left column (w - Weight[i]) in the row above with added benefit
*/
if(Weight[i] <= w)
CostTable[i][w] = max(Benefit[i] + CostTable[i-1][w - Weight[i]], CostTable[i-1][w]);
else
CostTable[i][w] = CostTable[i-1][w];
}
}
}

void printCostTable(){
for(int i = 0; i <= item_count; ++i){
printf("%d:  ", i);
for(int w = 0; w <= total_weight; ++w)
printf("%d ", CostTable[i][w]);
printf("\n");
}
}

int main(){

Weight[1] = 6;
Weight[2] = 1;
Weight[3] = 2;
Weight[4] = 5;
Weight[5] = 4;
Weight[6] = 3;

Benefit[1] = 10;
Benefit[2] = 5;
Benefit[3] = 7;
Benefit[4] = 12;
Benefit[5] = 8;
Benefit[6] = 6;

dynamicKnapsack();

printf("Max Benefit: %d\n\n", CostTable[item_count][total_weight]);

printCostTable();

return 0;
}
```

#### Recursive:

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: Zero one knapsack recursive
*/

#include<stdio.h>

#define N 128

int CostTable[N][N];
int Weight[N];
int Benefit[N];

int total_weight = 10;
int item_count = 6;

inline int max(int a, int b){
return a > b ? a : b;
}

int RecursiveKnapsack(int i, int w){
if(i == 0 || w == 0)
return 0;

if(Weight[i] > w)
return RecursiveKnapsack(i - 1, w);
else
return max(RecursiveKnapsack(i - 1, w), RecursiveKnapsack(i - 1, w - Weight[i]) + Benefit[i]);
}

int main(){

Weight[1] = 6;
Weight[2] = 1;
Weight[3] = 2;
Weight[4] = 5;
Weight[5] = 4;
Weight[6] = 3;

Benefit[1] = 10;
Benefit[2] = 5;
Benefit[3] = 7;
Benefit[4] = 12;
Benefit[5] = 8;
Benefit[6] = 6;

printf("Max Benefit: %d\n", RecursiveKnapsack(item_count, total_weight));

return 0;
}
```

#### Recursive Memoized:

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: Zero one knapsack recursive memoization
*/

#include<stdio.h>

#define N 128

int CostTable[N][N];
int Weight[N];
int Benefit[N];

int total_weight = 10;
int item_count = 6;

inline int max(int a, int b){
return a > b ? a : b;
}

int RecursiveKnapsack(int i, int w){
if(CostTable[i][w] != -1)
return CostTable[i][w];

if(Weight[i] > w)
CostTable[i][w] = RecursiveKnapsack(i - 1, w);
else
CostTable[i][w] = max(RecursiveKnapsack(i - 1, w), RecursiveKnapsack(i - 1, w - Weight[i]) + Benefit[i]);
}

int main(){

Weight[1] = 6;
Weight[2] = 1;
Weight[3] = 2;
Weight[4] = 5;
Weight[5] = 4;
Weight[6] = 3;

Benefit[1] = 10;
Benefit[2] = 5;
Benefit[3] = 7;
Benefit[4] = 12;
Benefit[5] = 8;
Benefit[6] = 6;

/*
* Set all values of 2D matrix CostTable to Minus 1
*/
for(int i = 0; i <= item_count; ++i)
for(int w = 0; w <= total_weight; ++w)
CostTable[i][w] = -1;

printf("Max Benefit: %d\n", RecursiveKnapsack(item_count, total_weight));

return 0;
}
```

## UVA Problem 10405 – Longest Common Subsequence Solution

UVA Problem 10405 – Longest Common Subsequence Solution:

Solving Technique:

This one is a fun problem. For this problem we need to find Longest Common Sub Sequence length of two given strings. We can solve this using LCS Algorithm discussed in Introduction to Algorithms book. This algorithm is explained in Wikipedia and other programming language implementations can be found here.

I have provided two dynamic programming implementations below with one top down memoized ( *Slower ) and a bottom up ( *Faster ) solution.

Take the string inputs carefully there may be empty lines in between.

Overview:

Simple explanation for solution technique is we apply Dynamic Programming techniques. There are overlapping sub problems that we can combine to get original solutions.

Starting from the end of both strings. If both of the characters in string are same then we can reduce both string size by 1 length. So now if do the reverse meaning add 1 we get original solution.

In case both characters are not same keeping one string same we reduce the other one by 1 length and try to match the last characters again.

This way if two characters are  same we increase LCS length count. Among the sub problem we choose the one with longest length.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.

Input:

```bcacbcabbaccbab
bccabccbbabacbc

a1b2c3d4e
zz1yy2xx3ww4vv

abcdgh
aedfhr

abcdefghijklmnopqrstuvwxyz
a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0

abcdefghijklmnzyxwvutsrqpo
opqrstuvwxyzabcdefghijklmn```

Output:

```11
4
3
26
14```

### Bottom Up Memoized Code:

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10405 Longest Common Subsequence ( LCS )
* Method:  Memorized Recursive / Top Down Solution
*/

#include<stdio.h>;
#include<string.h>;
#define SIZE 1024

static char x[SIZE], y[SIZE];
static int lcs[SIZE][SIZE];

int maxval(int a, int b){
return a > b ? a : b;
}

/*
* If the value is not -1 then it means the value of that sub problem is
* already calculated. Just return that calculated value
* If both of the characters in string are same then we can reduce both string size by 1 length and calculate rest
* Else among sub problems by reducing one string and keeping the other one same find the one with the max length
*/
int LCS(int i, int j){
if(lcs[i][j] != -1)
return lcs[i][j];

if(x[i-1] == y[j-1])
lcs[i][j] = LCS(i-1, j-1) + 1;
else
lcs[i][j] = maxval( LCS(i-1, j), LCS(i, j-1) );

return lcs[i][j];
}

int main(){
register unsigned i, j;
while(gets(x) && gets(y)){

int xlen = strlen(x);
int ylen = strlen(y);

/*
* Set -1 to all positions to indicate there are no calculated value
*/
for(i = 1; i <= xlen; ++i)
for(j = 1; j <= ylen; ++j)
lcs[i][j] = -1;

printf("%d\n", LCS(xlen,ylen) );

}
return 0;
}
```

### Top Down DP Code:

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10405 Longest Common Subsequence ( LCS )
* Method:  Top Down Dynamic Programming Solution
*/

#include<stdio.h>
#include<string.h>
#define SIZE 1024

static char x[SIZE], y[SIZE];
static int lcs[SIZE][SIZE];

int maxval(int a, int b){
return a > b ? a : b;
}

int main(){
register int i, j;

while(gets(x) && gets(y)){

int xlen = strlen(x);
int ylen = strlen(y);

/*
* If both of the characters in string are same then we can reduce both string size by 1 length and calculate rest
* Else among sub problems by reducing one string and keeping the other one same find the one with the max length
*/
for(i = 1; i <= xlen; ++i){
for(j = 1; j <= ylen; ++j){
if(x[i-1] == y[j-1])
lcs[i][j] = lcs[i-1][j-1] + 1;
else
lcs[i][j] = maxval(lcs[i-1][j], lcs[i][j-1]);
}
}

/*
* The max length is at the bottom right corner of the table
*/
printf("%d\n", lcs[xlen][ylen] );

}
return 0;
}
```

## UVA Problem 357 – Let Me Count The Ways Solution

UVA Problem 357 – Let Me Count The Ways Solution:

Solving Technique:

At first have a look at UVA 674 – Coin Change. Both of these can be solved with dynamic programming and they are almost same with only minor differences. Again we are asked to count the number of ways we can distribute given amount of money with 1, 5, 10, 25, 50 Dollar coins.

One gotcha for this problem is that output is so large int can’t hold that value. Using long or long long can solve this problem. Rest just modify the while loop as the given output format.

Here the first code is almost the same as the coin change problem. In the previous code i split the loops in two ways. But here in the second code I combined all the loops into a single loop. Although this may be slower.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.

Input:

```17
11
4```

Output:

```There are 6 ways to produce 17 cents change.
There are 4 ways to produce 11 cents change.
There is only 1 way to produce 4 cents change.```

### Split Loop Code:

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 357 – Let Me Count The Ways Solution
*/

#include<stdio.h>
#define N 30002

static long long a[N];
static const long long coins[4] = {5, 10, 25, 50};

int main(){
register unsigned long long i, j;
long long n;

for(i = 0; i < N; ++i)
a[i] = 1;

for(i = 0; i < 4; ++i){
for(j = coins[i]; j < N; ++j)
a[j] += a[j - coins[i]];
}

while(scanf("%lld", &n) == 1){
if(a[n] == 1)
printf("There is only %lld way to produce %lld cents change.\n", a[n], n);
else
printf("There are %lld ways to produce %lld cents change.\n", a[n], n);
}
return 0;
}
```

### Combined / Loop Fusion:

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 357 – Let Me Count The Ways Solution
*/

#include<stdio.h>
#define N 30002

static long long a[N];
static const unsigned coins[5] = {1, 5, 10, 25, 50};

int main(){
register unsigned int i, j;
unsigned n;

/**
* This is a bit slower than split loop version
* In problem 674 i split the loop in two different ways
* We can apply this for both UVA problem 357 and 674
*/
a[0] = 1;
for(i = 0; i < 5; ++i){
for(j = coins[i]; j < N; ++j)
a[j] += a[j - coins[i]];
}

while(scanf("%lld", &n) == 1){
if(a[n] == 1)
printf("There is only %lld way to produce %u cents change.\n", a[n], n);
else
printf("There are %lld ways to produce %u cents change.\n", a[n], n);
}
return 0;
}
```

## UVA Problem 674 – Coin Change Solution

UVA Problem 674 – Coin Change Solution:

Solving Technique:

Given 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We are to calculate the number of ways the input amount can be distributed with this coins.

This problem is a bit harder. It can be solved with dynamic programming or using greedy technique. Use bottom up technique instead of top down to speed it up.

We can also replace this,

``` for(i = 5; i < N; ++i)
a[i] = a[i - 1];
```

with this since we know no matter what the input it is always possible to give 1 cents,

```for(j = 0; j < N; ++j)
a[j] = 1;
```

It is hard to visualize without drawing the recursion tree or the array. The first 20 indexes of the array looks like this,

```Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Coins: 1 1 1 1 1 2 2 2 2 2 4  4  4  4  4  6  6  6  6  6  9
```

### Explanation:

/* TO DO */

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.

Input:

```11
26
5
4```

Output:

```4
13
2
1```

### Code Bottom Up:

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 674 Coin Change
*/

#include <stdio.h>
#define N 8000

static int a[N] = {1, 1, 1, 1, 1};
static const int coins[4] = {5, 10, 25, 50};

int main()
{
register int i, j;

for(i = 5; i < N; ++i)
a[i] = a[i - 1];

for(i = 0; i < 4; ++i){
for(j = coins[i]; j < N; ++j)
a[j] += a[ j - coins[i] ];
}

int n;
while(scanf("%d", &n) == 1)
printf("%d\n", a[n]);

return 0;
}
```

### Loop Fission Variant:

```/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 674 Coin Change
*/

#include <stdio.h>

#define N 8000
#define M 5

static int a[N] = {1, 1, 1, 1, 1};

int main()
{
register int i, j;

for(j = M; j < N; ++j)
a[j] += a[j - 1];

for(j = 5; j < N; ++j)
a[j] += a[j - 5];

for(j = 10; j < N; ++j)
a[j] += a[j - 10];

for(j = 25; j < N; ++j)
a[j] += a[j - 25];

for(j = 50; j < N; ++j)
a[j] += a[j - 50];

int n;
while(scanf("%d", &n) == 1)
printf("%d\n", a[n]);

return 0;
}
```