UVA Problem 10696 – f91 Solution

UVA Problem 10696 – f91 Solution:


Click here to go to this problem in uva Online Judge.

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 !!
Before starting to look below take look at this codes ( Fibonacci DP, Memoization ) with explanation.

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 )
 * @link    https://quickgrid.wordpress.com
 * 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 )
 * @link    https://quickgrid.wordpress.com
 * 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 )
 * @link    https://quickgrid.wordpress.com
 * 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 )
 * @link    https://quickgrid.wordpress.com
 * 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;
}
Advertisements

UVA Problem 10405 – Longest Common Subsequence Solution

UVA Problem 10405 – Longest Common Subsequence Solution:


Click here to go to this problem in uva Online Judge.

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 )
 * @link    https://quickgrid.wordpress.com
 * 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 )
 * @link    https://quickgrid.wordpress.com
 * 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 674 – Coin Change Solution

UVA Problem 674 – Coin Change Solution:


Click here to go to this problem in uva Online Judge.

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 )
 * @link    https://quickgrid.wordpress.com
 * 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 )
 * @link    https://quickgrid.wordpress.com
 * 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;
}

Fibonacci Memoization Top Down ( Recursive ) and Bottom Up ( Iterative )

Fibonacci Memoization Top Down ( Recursive ) and Bottom Up ( Iterative ) Dynamic Programming:


Top Down Fibonacci Memoization Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<stdio.h>

#define N 64
long long F[N];

/**
 * Top Down Recursive Fibonacci Memoization
 */
long long topDownMemFib(long long n){
    /**
     * If its not 1 then it means there is already a calculated value
     * So no more need to compute, just return that value
     */
    if(F[n] != -1)
        return F[n];

    F[n] = topDownMemFib(n - 1) + topDownMemFib(n - 2);
    return F[n];
}

int main(){
    register unsigned i;

    unsigned n;
    printf("Enter a number:\n");
    scanf("%u", &n);

    /**
     * Terminating condition values
     */
    F[0] = 0;
    F[1] = 1;

    /**
     * First set the whole array to -1, means there are no calculated value
     */
    for(i = 2; i <= n; ++i)
        F[i] = -1;

    printf("%lld\n", topDownMemFib(n));

    return 0;
}

 

Bottom Up Iterative Fibonacci Implementation:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<stdio.h>

/**
 * Increase this value for numbers more than 64
 */
#define N 64
long long F[N];

/**
 * Top Down Fibonacci Memoization
 */
long long bottomUpMemFib(long long n){
    /**
     * Terminating Condition
     */
    F[0] = 0;
    F[1] = 1;

    register unsigned i;
    for(i = 2; i <= n; ++i)
        F[i] = F[i - 1] + F[i - 2];

    return F[n];
}

int main(){
    register unsigned i;

    unsigned n;
    printf("Enter a number:\n");
    scanf("%u", &n);

    printf("%lld\n", bottomUpMemFib(n));

    return 0;
}

UVA Problem 100 – The 3n + 1 problem Solution

UVA Problem 100 – The 3n + 1 problem Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This problem is not for beginners. Due to a simple logical error I failed and failed again.

Before proceeding to understand my solution please check Memoization, Lookup Table, Recursion, Dynamic Programming, Bitwise Operations. Also you may check Algorithmist Solution and Collatz Conjecture. Learned this solution technique is from here.

For this problem we are given two numbers. We need cycle from and including the smaller number to and including the bigger number.

Basically we are to cycle through the given range and find the maximum cycle length among all numbers in the given range.

Here i have used a lookup table to store already calculated cycle lengths. This dramatically decreases running time. Without lookup table my first solution took 0.552 s but when i applied memoization ( this solution ) took only 0.035 s.

0.552 > 0.035 /* See the speed difference */

Another thing is when the number is ODD we need to calculate 3*n+1. But when we calculate 3*n+1 for any ODD number the ODD number becomes EVEN. Now we can divide by 2 in same step since it becomes EVEN. So here i performed 2 steps in the ODD checking code.


 

n = 3, 3*n+1 = 10 /* So calculating 3n+1 for odd number is always even */
n = 7, 3*n+1 = 22 /* Since it becomes even we can perform n/2 in same step */

 

Also another thing to note is that i used,

n >> 1 /* Which does the same thing as n/2 but Faster */

 

So here I calculate the cycle length and store them in table. If the table already contains the definition it returns the cycle length to main(). There I check if the returned cycle length is bigger then existing max cycle length.

Last thing set the first index of table to 1 since I haven’t used any condition to check if the number becomes 1. Also it is much faster than checking every time since the number is bound to converge in 1. So 1 is stored in look table when it is found its immediately returned.

table[1] = 1;

Rest i explained code comments. Hopefully it is easier to understand :).

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:

1 10
100 200
201 210
900 1000

Output:

1 10 20
100 200 125
201 210 89
900 1000 174

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 100 ( 3n + 1 )
 */
#include<stdio.h>

#define SIZE 1000002

/* Lookup table for storing previously calculated values */
static unsigned table[SIZE];

/* Returns cycle length for given number */
unsigned cycleLength(register unsigned n){
    /* If the value already exists in the lookup table then return its cycle length */
    if (n < SIZE && table[n])
        return table[n];

    /* Check if number is odd */
    if (n&1){
        if (n < SIZE){
            /* Since 3n+1 becomes an even number, we perform the next step which is divided by two since its even, also +2 since we perform two operations */
            table[n] = 2 + cycleLength((3 * n + 1) >> 1);
            return table[n];
        }else
            /* The value is bigger than table so we calculate and return */
            return 2 + cycleLength((3 * n + 1) >> 1);
    }else{
        if (n < SIZE){
            /* The number is even so we perform number divided two, or bit shift left once */
            table[n] = 1 + cycleLength(n >> 1);
            return table[n];
        }else
            return 1 + cycleLength(n >> 1);
    }
}

int main(){
    unsigned a, b, count;
    register unsigned n;
    /* This is necessary since i don't check for 1 in cycleLength, Also 1st index is always 1 */
    table[1] = 1;

    while (scanf("%u%u", &a, &b) == 2){
        unsigned maxCycle = 0;
        /* The input may contain bigger number first then smaller number */
        if (a < b){
            for (n = a; n <= b; ++n){
                /* Cycle every value between a to b */
                count = cycleLength(n);
                /* We need to find max cycle, so if a cycle count is greater than maxCycle then replace maxCycle */
                if (maxCycle < count)
                    maxCycle = count;
            }
        }else{
            for (n = b; n <= a; ++n){
                count = cycleLength(n);
                if (maxCycle < count)
                    maxCycle = count;
            }
        }
        printf("%u %u %u\n", a, b, maxCycle);
    }
    return 0;
}

UVA Problem 11636 – Hello World! Solution

UVA Problem 11636 – Hello World! Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

Here i have given Three solution one is Hybrid ( pre-calculated values with little calculations, Rank 1821 ) , another is with pre-caculated values stored in table ( see Memoization and Look up table ) ,last one is pure calculation. For this problem i have found out all answer combinations. So you can use your logic to get your code faster.

The problem requires us to find minimum number of copy commands to reach input lines.

For example, if there is 1 line and we copy whats on-screen 4 times we get 16 lines. How?

1 line copy paste 2 lines (since there was 1 line and we copied 1 more line)
2 line copy paste 4 lines (since there was 2 line and we copied 2 more line)
4 line copy paste 8 lines (since there was 4 line and we copied 4 more line)
8 line copy paste 16 lines (since there was 8 line and we copied 8 more line)

As we can what we copy is twice ( 2 times ) the amount of original.

Now we can use this knowledge to find the copy commands required. We can just loop until we find that our line number exceeds the given line. Now as many times as we looped is the copy command required.

Because we can copy 11 lines, 10 lines or 9 lines in 4 commands. We weren’t given any restriction on this. Just looping until our copy lines for the loop exceed the given line is enough.

Also Critical thing is input can be 0, 1 both for these the output is 0. For 1 the answer is 0 because. There is already a line so it takes 0 command to get 1 line.

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


Critical Inputs:

21
99
0
1
1001
101
11
-1

Output:

Case 1: 5
Case 2: 7
Case 3: 0
Case 4: 0
Case 5: 10
Case 6: 7
Case 7: 4

Code Easier:

/**
 * @author Quickgrid ( Asif Ahmed )
 * @link https://quickgrid.wordpress.com
 */

#include<stdio.h>

int main(){
    int n;
    register unsigned c = 1;
    while(scanf("%d", &n) && n>-1){
        register unsigned i = 1, p = 0;
        while(i < n){
            /*
             * In the equation 2^p > n, for which value is greater than input, Here p is the answer
             */
            i <<= 1;
            ++p;
        }
        printf("Case %u: %u\n", c, p);
        ++c;
    }
    return 0;
}

Faster Solution ( Rank: 1821, Run time: 9 ms  ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 */
#include<stdio.h>
int main(){
    int n;
    register unsigned int c = 1;
	while(scanf("%d", &n) && n>-1){
        if(n>1){
            if(n > 8192)
                printf("Case %u: 14\n", c);
            else if(n >= 4097)
                printf("Case %u: 13\n", c);
            else if(n >= 2049)
                printf("Case %u: 12\n", c);
            else if(n >= 1025)
                printf("Case %u: 11\n", c);
            else{
                register unsigned int i = 1, lines = 1;
                for(; i<=n; ++i){
                    lines <<= 1;
                    if(lines >= n){
                        break;
                    }
                }
                printf("Case %u: %u\n", c, i);
            }
        }else printf("Case %u: 0\n", c);
        ++c;
	}
	return 0;
}

Another Solution ( with Look Up Table ):

/*
 * @author Quickgrid ( Asif Ahmed )
 * @link   https://quickgrid.wordpress.com
 */

#include<stdio.h>
static unsigned arr[10010];

void precalculate(){
    register unsigned n = 10001;
    arr[0] = 0;
    arr[1] = 0;
    arr[2] = 1;
    arr[3] = 2;
    arr[4] = 2;
    arr[5] = 3;
    arr[6] = 3;
    arr[7] = 3;
    arr[8] = 3;

    /**
     * If you look carefully there is a nice pattern here
     * This code can be shorted with a nested loop
     * 2^N <= Loop <= 2^(N-1) + 1
     */
    for(; n >= 8193; --n)
        arr[n] = 14;
    for(; n >= 4097; --n)
        arr[n] = 13;
    for(; n >= 2049; --n)
        arr[n] = 12;
    for(; n >= 1025; --n)
        arr[n] = 11;
    for(; n >=  513; --n)
        arr[n] = 10;
    for(; n >=  257; --n)
        arr[n] = 9;
    for(; n >=  129; --n)
        arr[n] = 8;
    for(; n >=   65; --n)
        arr[n] = 7;
    for(; n >=   33; --n)
        arr[n] = 6;
    for(; n >=   17; --n)
        arr[n] = 5;
    for(; n >=    9; --n)
        arr[n] = 4;
}

int main(){
    precalculate();
    int n;
    register unsigned c = 1;

    while (scanf("%d", &n) && n > -1){
        printf("Case %u: %u\n", c, arr[n]);
        ++c;
    }

    return 0;
}