UVA Problem 10082 – WERTYU Solution

UVA Problem 10082 – WERTYU Solution:


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

Solving Technique:

Read the first paragraph and input section carefully. This is a simple mapping problem.

The problem is that the keyboard is broken and every key that was pressed its immediate right character was printed. So we have to reverse that procedure by mapping every input character to the character to its left based on the given keyboard.

Generating the keyboard layout is easy. We can use an array and lay them sequentially so when we find a character we print the character that is to its left.

If we only use array to layout keyboard then for every input we will need to search the whole array. We can fix this by mapping the layout array to another array beforehand only once. Then just access that index and print.

Here the first code below is mapping from predefined lookup table. The second one does brute force to find its match. Here I have used stringstream but c++ string or c char array can also be used.

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:

O S, GOMR YPFSU/

Output:

I AM FINE TODAY.

Code (Mapping from predefined Lookup table):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10082 WERTYU ( using c++ string stream )
 */

#include<cstdio>
#include<sstream>
#include<iostream>

#define N 256

/**
 * Predefined keyboard layout
 */
static const char kb[64] = "`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";
static char s[N], A[N];

void createTable(){
    /**
     * space character does not change
     */
    A[' '] = ' ';

    /**
     * Create keyboard layout from broken keyboard
     */
    register int i = 0;
    for(; kb[i]; ++i)
        A[kb[i+1]] = kb[i];
}

int main(){
    std::ios_base::sync_with_stdio(NULL);
    std::cin.tie(0);
    register int i, j;

    /**
     * Create the keyboard layout beforehand
     */
    createTable();

	while(gets(s)){
        /**
         * Create a string stream from table to print all together
         * We can also use string and add each character then print
         */
        std::stringstream ss;

        /**
         * Lookup characters from predefined table
         */
        for(i = 0; s[i]; ++i)
            ss << A[s[i]];

        std::cout << ss.str() << "\n";
	}
	return 0;
}

Code (Using Lookup Table):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10082 WERTYU ( using c++ string stream )
 */

#include<cstdio>
#include<sstream>
#include<iostream>

static const char kb[64] = "`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";
static char s[256];

int main(){
    std::ios_base::sync_with_stdio(NULL);
    std::cin.tie(0);
    register int i, j;

	while(gets(s)){
        std::stringstream ss;

        for(i = 0; s[i]; ++i){
            if(s[i] == ' ')
                ss << ' ';
            else{
                /**
                 * Each character maps to a character in its left as defined
                 */
                for(j = 0; kb[j]; ++j){
                    if(s[i] == kb[j])
                        ss << kb[j - 1];
                }
            }
        }
        std::cout << ss.str() << "\n";
	}
	return 0;
}
Advertisements

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 10924 – Prime Words Solution

UVA Problem 10924 – Prime Words Solution:


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

Solving Technique:

This problem is easy we just need to read it carefully.

The problem assigns values for 1 to 26 for (a-z) and 27 – 52 for (A-Z). The input is a stringWe are asked to find the sum of every character with given value and check if the sum is a prime number or not.  

Summing is actually easy. For lower case when we sum, we just subtract the character from ASCII value of a or the ‘a’ character. This way we get 1 to 25 for ( a to z ). Since the number that was assigned was 1 more, so we add 1 to every value in loop. We do the same thing for upper case letters ( subtract ‘A’ from each character ). So we get 0 to 25 again. This time we add 27 to every value in loop so we get 27 to 52 for ( A to Z ).

One important thing to note is although 1 is not a prime. In this problem it is specified that it is prime. We output according to given specification.  So if the sum of all given word is 1 then the output is prime. Ex, a ( since a is 1 ).

The given word length is 1 to 20. So an array of 21 is enough. We should check for EOF to terminate the program.

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:

UFRN
contest
AcM
a

Output:

It is a prime word.
It is not a prime word.
It is not a prime word.
It is a prime word.

Code (using lookup table, Sieve of Eratosthenes):

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

#include<stdio.h>
#include<math.h>

/**
 * Since there is max of 20 characters in a single line
 * Calculating with biggest value 'Z' gives a max of 1040
 */
#define N 1041

static int table[128];
static unsigned primes[N];

void PreSum(){
    register unsigned i, j = 1;

    /**
     * Set 1 to 26 for 'a' to 'z'
     */
    for (i = 'a'; i <= 'z'; ++i, ++j)
        table[i] = j;

    /**
     * Set 27 to 52 for 'a' to 'z'
     */
    for (i = 'A'; i <= 'Z'; ++i, ++j)
        table[i] = j;
}

void SieveOfEratosthenes(){
    register unsigned i, j;

    /**
     * For this problem though 0 and 1 are primes
     */
    for (i = 0; i < N; ++i)
        primes[i] = 1;

    unsigned len = sqrt(N);

    for (i = 2; i <= len; ++i){
        if (primes[i]){
            for (j = i * i; j <= N; j += i)
                primes[j] = 0;
        }
    }
}

int main(){
    /**
     * Pre calculate character value table
     * Pre calculate prime values using Sieve of Eratosthenes
     */
    PreSum();
    SieveOfEratosthenes();

    char s[32];
    register unsigned i;

	while (gets(s)){
        unsigned sum = 0;

        /**
         * Get character value from pre calculated character value table and sum them
         */
        for (i = 0; s[i]; ++i)
            sum += table[s[i]];

        /**
         * Get primality from pre calculated prime table
         */
        if (primes[sum])
            printf("It is a prime word.\n");
        else
            printf("It is not a prime word.\n");
	}
	return 0;
}

Code (without using table):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 */

#include<stdio.h>
#include<math.h>

static char s[32];

int main(){
    while (gets(s)){
        unsigned int i, sum = 0;

        for (i = 0; s[i]; ++i){
            if (s[i] >= 'a' && s[i] <= 'z')
                sum += s[i]-'a'+1;
            else
                sum += s[i]-'A'+27;
        }

        if (sum <= 2)
            printf("It is a prime word.\n");
        else if (sum % 2 == 0)
            printf("It is not a prime word.\n");
        else{
            unsigned int prime = 1, len = sqrt(sum);
            for(i = 3; i <= len; i += 2){
                if(sum % i == 0){
                    printf("It is not a prime word.\n");
                    prime = 0;
                    break;
                }
            }
            if (prime)
                printf("It is a prime word.\n");
        }
    }
    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;
}