UVA Problem 11716 – Digital Fortress Solution

UVA Problem 11716 – Digital Fortress Solution:


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

Solving Technique:

This is an easier string problem. The task is to arrange the characters within the string in a certain order.

If the input string length is not square of a number then print INVALID. Ex: “DAVINCICODE” has length of 11. Squaring no number results in 11.

“DTFRIAOEGLRSI TS” has length of 16 including the space character. Square root of 16 is 4 and 4 * 4 is 16. So this is valid input.

Now if the input is valid then next task is to rearrange them. Instead of following given solution technique in the question it can solved much faster in another way. Following instruction in the question gives intuition that first the string must be positioned on 2 dimensional matrix in row major order. Then traverse them column by column.

A better way is find out each group length from square rooting the original string length. Next starting from first group take a character then skip by group length to get next column major character. After its done do this from the next character of first group.


Visualization:
uva 11716 rearrange string in column major order
uva 11716 rearrange string in column major order

 

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++.


More Inputs of This Problem on uDebug.


Input:

3
WECGEWHYAAIORTNU
DAVINCICODE
DTFRIAOEGLRSI TS

 


Output:

WEAREWATCHINGYOU
INVALID
DIGITAL FORTRESS

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11716 - Digital Fortress
 * Technique: Square String Traverse from row major
 *            to column major by skipping.
 */

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


#define N 10002
static char s[N];
static char output[N];


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    int n;
    scanf("%d", &n);
    getchar();


    while( n-- ){
        gets(s);


        // Get the length of string and length of each string group.
        int len = strlen(s);
        int rc = sqrt(len);


        // Reset in case there are characters from previous iteration.
        memset(output, 0, sizeof output);



        // If the string length can be divided into equal parts
        // then traverse by skipping certain length.
        if( rc * rc == len ){

            int k = 0;

            for( int j = 0; j < rc; ++j ){
                for( int i = j; i < len; i = i + rc ){
                    output[k++] = s[i];
                }
            }

            puts(output);

        }
        else{
            puts("INVALID");
        }

    }


    return 0;
}

UVA Problem 12646 – Zero or One Solution

UVA Problem 12646 – Zero or One Solution:


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

Solving Technique:

The input is all possible combination of 3 bits. If A, B, C are thought as bits then possible binary combination are,

000 \rightarrow * \\  001 \rightarrow C \\  010 \rightarrow B \\  011 \rightarrow A \\  ---- \\  100 \rightarrow A \\  101 \rightarrow B \\  110 \rightarrow C \\  111\rightarrow * \\

This problem can be solved in multiple ways such as using string, checking equality, performing xor equality etc. My code below is exactly same as equality checking but it perform xor operation between them.

XOR Table,

\begin{tabular}{l*{6}{c}r}  X & Y & X XOR Y \\ \hline  0 & 0 & 0 \\  0 & 1 & 1 \\  1 & 0 & 1 \\  1 & 1 & 0 \\  \end{tabular}
 

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++.


More Inputs of This Problem on uDebug.


Input:

1 1 0
0 0 0
1 0 0

 


Output:

C
*
A

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 12646 - zero or one
 * Technique: XOR Bits to check equality.
 */

#include<stdio.h>


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    int A, B, C;
    while( scanf("%d%d%d", &A, &B, &C) == 3 ){

        if( !( A ^ B ) && !( A ^ C ) )
            putchar('*');
        else{
            if( A ^ B ){
                if( B ^ C )
                    putchar('B');
                else
                    putchar('A');
            }
            else
                putchar('C');
        }
        putchar('\n');
    }


    return 0;
}

UVA Problem 10189 – Minesweeper Solution

UVA Problem 10189 – Minesweeper Solution:


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

Solving Technique:

Given a mine field that is a matrix / 2D array, produce an output that contains count of adjacent mines for each squares.

In a 2D array for each squares there are at most adjacent 8 squares. If the current position is i and j then,

\begin{bmatrix}  (i-1,j-1) & (i-1,j) & (i-1,j+1) \\  (i+0,j-1) &  (i,j)  & (i+0,j+1) \\  (i+1,j-1) & (i-1,j) & (i+1,j+1) \\   \end{bmatrix}

Just traverse the matrix row-column wise and check its adjacent squares for getting mine count for current position. The adjacent squares check can be implemented with 8 if conditions for each one.

Another technique is to store the co-ordinates of adjacent squares and using a for loop to check them. The illustration below shows how the 2nd code is implemented using arrays and for loops,
uva 10189 matrix adjacent squares check with saved co-ordinates and for loop
uva 10189 matrix adjacent squares check with saved co-ordinates and for loop

Here the arrow from the center shows where checking starts. The 1D arrays drow and dcol hold the row and column values the way shown above. It can be changed by modifying drow and dcol arrays.

 

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++.


More Inputs of This Problem on uDebug.


Input:

4 4
*...
....
.*..
....
3 5
**...
.....
.*...
0 0

 


Output:

Field #1:
*100
2210
1*10
1110

Field #2:
**100
33200
1*100

Code Using Multiple if Conditions:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10189 - Minesweeper
 * Technique: 2D Array / Matrix Boundary checking using
 *            if conditions.
 */

#include<stdio.h>
#include<string.h>


#define MAXSIZE 101


static char MineField[MAXSIZE][MAXSIZE];



int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    int n, m;

    int FieldNumber = 0;

    while( scanf("%d%d", &n, &m), n ){

        getchar();

        for(int i = 0; i < n; ++i)
            scanf("%s", &MineField[i]);


        if( FieldNumber )
            printf("\n");


        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){

                if( MineField[i][j] == '*' )
                    continue;

                int temp = 0;

                if( i + 1 < n && MineField[i + 1][j] == '*' )
                    ++temp;
                if( i + 1 < n && j + 1 < m && MineField[i + 1][j + 1] == '*' )
                    ++temp;
                if( j + 1 < m && MineField[i][j + 1] == '*' )
                    ++temp;
                if( i - 1 >= 0 && j + 1 < m && MineField[i - 1][j + 1] == '*' )
                    ++temp;
                if( i - 1 >= 0 && MineField[i - 1][j] == '*' )
                    ++temp;
                if( i - 1 >= 0 && j - 1 >= 0 && MineField[i - 1][j - 1] == '*' )
                    ++temp;
                if( j - 1 >= 0 && MineField[i][j - 1] == '*' )
                    ++temp;
                if( i + 1 < n && j - 1 >= 0 && MineField[i + 1][j - 1] == '*' )
                    ++temp;


            MineField[i][j] = temp + '0';

            }
        }


        printf("Field #%d:\n", ++FieldNumber);


       for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j)
                putchar(MineField[i][j]);
            printf("\n");
       }

    }

    return 0;
}

Code Bound checking using Array & for Loop:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10189 - Minesweeper
 * Technique: 2D Array / Matrix Boundary checking using
 *            co-ordinate array and for loop.
 */

#include<stdio.h>
#include<string.h>


#define MAXSIZE 101


static char MineField[MAXSIZE][MAXSIZE];


// Co-ordinates / directions of adjacent 8 squares.
// W, SW, S, SE, E, NE, N, NW
static const int drow[] = {0, 1, 1, 1, 0, -1, -1, -1};
static const int dcol[] = {-1, -1, 0, 1, 1, 1, 0, -1};



int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    int n, m;

    int FieldNumber = 0;

    while( scanf("%d%d", &n, &m), n ){

        getchar();

        for(int i = 0; i < n; ++i)
            scanf("%s", &MineField[i]);


        if( FieldNumber )
            printf("\n");


        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){

                int temp = 0;

                // If mine found do nothing.
                if( MineField[i][j] == '*' )
                    continue;


                // For each adjacent squares of the current square calculate mine count.
                // and set the count in current square.
                for(int k = 0; k < 8; ++k){

                    // Check if out of bound of the 2D array or matrix.
                    if( i + drow[k] < 0 || j + dcol[k] < 0 || i + drow[k] >= n || j + dcol[k] >= m )
                        continue;

                    // Check the appropriate co-ordinate for mine, if mine found increase count.
                    if( MineField[i + drow[k] ][j + dcol[k]] == '*' )
                        ++temp;

                }

                // All adjacent squares checked set the mine count for current squares.
                MineField[i][j] = temp + '0';

            }
        }


        printf("Field #%d:\n", ++FieldNumber);


       for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j)
                putchar(MineField[i][j]);
            printf("\n");
       }

    }

    return 0;
}

UVA Problem 11565 – Simple Equations Solution

UVA Problem 11565 – Simple Equations Solution:


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

UPDATE:

As a commenter below pointed out the solution is wrong due to the fact I made some wrong assumptions. Kindly check other sources for correct solution. This was accepted due to weak test cases. Also check udebug for different test cases.

Problem Statement Description:

Given input of A, B, C where 0 \leqslant A, B, C \leqslant 10000 and three equations,

\mathbf{ x + y + z = A }
\mathbf{ x.y.z = B }
\mathbf{ x^2 + y^2 + z^2 = C }

The task is to find values of x, y, z where x, y, z are three different integers which is ( x != y != z ). Meaning x can not be equal to y, t can not be equal to z and z can not be equal to x.

The problem asks to output the least value of x then y then z meaning the output will be in x < y < z order.


Things to notice:

One very important thing to notice is that for all three equation the values of x, y, z can be interchanged and it will still satisfy the problem.

For example,
\mathbf{ if, x = 5, y = 0, z = 9 }

then it can also be written as,
\mathbf{ x = 0, y = 5, z = 9 }
\mathbf{ x = 9, y = 5, z = 0 }

etc. all possible combinations. But the problem asks for least value of x then y then z.

So if after calculation the result is x = 9, y = 0, z = 5 which is supposed to be x = 0, y = 5, z = 9. In that case the values can be sorted which will result in x = 0, y = 5, z = 9 and this still satisfies the equations.


Solution Technique Explanation:

The simple approach to solve this problem is try all possible combinations of x, y, z and see if it produces a correct result.

The values of x, y, z being negative also satisfies this problem. Forgetting the value of negatives for the moment and focusing on the positive values. To get the naive loop count limit see x or y or z can be at least 0 and at most 100.

Same goes for the negative portion so looping for -100 to 100 for each 3 nested loops seem easy ( I haven’t given the 3 nested loop solution here. It can be found on other sites ). So from -100 to 0 to 100 there are 201 number in between. So naive solution requires 201*201*201 which is more than 8 million (8120601). This program should do 117 * 45 = 5265 iterations per test case.


This problem can be solve much faster using some algebraic substitution. Notice,

\mathbf{ x + y + z = A ........ (i) \\ }
\mathbf{ x.y.z = B ........ (ii) \\ }
\mathbf{ x^2 + y^2 + z^2 = C ........ (iii) \\ }

from equation (ii),

\mathbf{ x.y.z = B }

This can be rewritten as,

\mathbf{ z = \frac{B}{x.y} ........ (iv) }

from equation (i),

\mathbf{ x + y + z = A }

substituting value of z from (iv) to (i) gives,

\mathbf{ x + y + \frac{B}{x.y} = A }

This can be rewritten as,

\mathbf{ \frac{B}{x.y} = A - x - y ........ (v) }

similarly from (iii) and (iv),

\mathbf{ x^2 + y^2 + z^2 = C }

plugging in the value of z and solving for x and y,

\mathbf{ x^2 + y^2 + ( \frac{B}{x.y} )^2 = C ........ (vi) }

Now from (v) and (vi),
\mathbf{ x^2 + y^2 + (A - x - y)^2 = C }

Notice this equation above does not contain z. Now z can be calculated in terms of B, x, y.

This will completely remove one of the nested loops. Further improvements can be made by cutting down number of loop iterations.


Important point to notice that A, B, C can be at most 10000. Also x, y, z can differ by 1 and satisfy the equation. From above equations,

\mathbf{ x + y + z = A ........ (i) }
\mathbf{ x.y.z = B ........ (ii) }
\mathbf{ x^2 + y^2 + z^2 = C ........ (iii) }

So if x, y, z differ by 1 then,

\mathbf{ y = x + 1 }
\mathbf{ z = x + 2 }

from equation (i),

\mathbf{ x + (x + 1) + (x + 2) = A }

but A can be at most 10000.

\mathbf{ x + (x + 1) + (x + 2) = 10000 }
\mathbf{ 3x + 3 = 10000 }

So, x = 3332.3333….

But to keep it simple, notice the lower order term 3 does not make much difference. By setting x = y = z the equation can be,

\mathbf{ x + x + x = 10000 }
\mathbf{ 3x = 10000 }
\mathbf{ x = 3333.3333.... }


from equation (iii) since x is squared so it to get its iteration just calculate the square root. or, setting x = y = z and B = 10000 in equation (iii) gives,

\mathbf{ x^2 + x^2 + x^2 = 10000 }
\mathbf{ 3x^2 = 10000 }
\mathbf{ x = 57.735.... }

after rounding of,
x = 58

So the loop range for x is [-58…58].


Again from equation (ii) the iteration limit for y can be counted using x = y = z,

\mathbf{ y.y.y = 10000 }
\mathbf{ y^3 = 10000 }
\mathbf{ y = 21.544.... }

Rounded of to,
y = 22

So iteration limit for y will be from [-22…22].

Calculating using y + 1 result in rounded range [-21…21]. Although I have not tested it.


Doing further algebraic simplification will remove another loop as z can be calculated in terms of A,B,C using,

\mathbf{ (A-z)^2 - 2.\frac{B}{z} = C - z^2 }

where,

\mathbf{ xy = \frac{B}{z} }

and,

\mathbf{ x + y = A - z }

using the main equation above, the value of z can be found and by solving the other equations the values of x and y can be calculated.


Also the loops can be input dependent. If max of A, B, C is bigger than 58 than choose 58 other wise choose the max as the loop counter.

There may be more improvements possible but that’s all I can come up with now. One final improvement can be made by breaking from all loops at once once the values are found. Although goto isn’t recommended c++ doesn’t support label to break out of multiple loops unlike java.

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++.


More Inputs of This Problem on uDebug.


Input:

2
1 2 3
6 6 14

Output:

No solution.
1 2 3

Optimized Code without goto:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11565 - Simple Equations
 * Technique: Mathematical elimination and substitution
 */

#include<cstdio>
#include<algorithm>
#include<iostream>

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    scanf("%d", &n);

    int A, B, C;

    while( n-- ){
        scanf("%d%d%d", &A, &B, &C);

        bool solutionFound = false;
        int x, y, z;

        for( x = -58; x <= 58; ++x ){
            for( y = -22; y <= 22; ++y ){

                if( x != y && ( (x * x + y * y) + (A - x - y) * (A - x - y) == C )  ){

                    int temp = x * y;

                    if( temp == 0 ) continue;

                    z = B / temp;

                    if( z != x && z != y && x + y + z == A   ){
                        if(!solutionFound){
                            int tmpArray[3] = {x, y, z};
                            std::sort(tmpArray, tmpArray + 3);
                            std::cout << tmpArray[0] << " " << tmpArray[1] << " " << tmpArray[2] << "\n";

                            solutionFound = true;
                            break;
                        }
                    }

                }
            }
        }

        if(!solutionFound) std::cout << "No solution." << "\n";

    }

    return 0;
}

Optimized Code without goto:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11565 - Simple Equations
 * Technique: Mathematical elimination and substitution
 */

#include<cstdio>
#include<algorithm>
#include<iostream>

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    scanf("%d", &n);

    int A, B, C;

    while( n-- ){
        scanf("%d%d%d", &A, &B, &C);

        bool solutionFound = false;
        int x, y, z;

        for( x = -58; x <= 58; ++x ){
            for( y = -22; y <= 22; ++y ){

                if( x != y && ( (x * x + y * y) + (A - x - y) * (A - x - y) == C )  ){

                    int temp = x * y;

                    if( temp == 0 ) continue;

                    z = B / temp;

                    if( z != x && z != y && x + y + z == A   ){
                        if(!solutionFound){
                            int tmpArray[3] = {x, y, z};
                            std::sort(tmpArray, tmpArray + 3);
                            std::cout << tmpArray[0] << " " << tmpArray[1] << " " << tmpArray[2] << "\n";

                            solutionFound = true;
                            goto done;
                        }
                    }

                }
            }
        }

        if(!solutionFound) std::cout << "No solution." << "\n";
        done:;

    }

    return 0;
}

 

UVA Problem 1225 – Digit Counting Solution

UVA Problem 1225 – Digit Counting Solution:


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

Solving Technique:

This problem is very easy. For input N = 13, sequence is 12345678910111213. which are actually numbers from 1 to 13 without spaces.

1 2 3 4 5 6 7 8 9 10 11 12 13

For this problem just calculate how many times a digit appears in the sequence. The digits being 0 to 9.

Use counting sort to easily calculate occurrence of a digit. If a digit is greater than single digit than break it to a single digit and increment count.

Here i have given two solutions. One converts digits to character than counts them. The next one count each digit in the integer without converting to string.

 

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++.


More Inputs of This Problem on uDebug.


Input:

2 
3 
13

 


Output:

0 1 1 1 0 0 0 0 0 0 
1 6 2 2 1 1 1 1 1 1

Code Using Character Count:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 1225 - Digit Counting
 * Technique: Counting sort characters, Integer to character conversion.
 */


#include<stdio.h>
#include<string.h>


#define N 200000

static char output[N];
static int outputNum[10];


int main() {

    int n;

    scanf("%d", &n);

    while( n-- ){

        int num;
        scanf("%d", &num);

        memset(outputNum, 0, sizeof outputNum);


        /**
         * Add the numbers to character array for easier counting.
         * If number is more then one digit it assign each digit to
         * a new location in char array. Although they are actually
         * reversed when positioning. But the order does not matter
         * in this problem. Just count each digit.
         *
         * It is possible to count with integers rather than using
         * char array. See the next code.
         */
        int k = 0;
        for(int i = 1; i <= num; ++i){

            int num = i;
            while(num){
                output[k++] = (num % 10) + '0';
                num /= 10;
            }
        }
        output[k] = '\0';


        /**
         * Use counting sort sort technique to position each
         * character to its equivalent integer location.
         */
        for(int i = 0; output[i]; ++i)
            ++outputNum[ output[i] - '0' ];


        for(int i = 0; i < 10; ++i){
            if(i) printf(" ");
            printf("%d", outputNum[i]);
        }
        printf("\n");
    }

	return 0;
}


Code Using Integer Count:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 1225 - Digit Counting
 * Technique: Counting sort characters, Integer to character conversion.
 */

#include<stdio.h>
#include<string.h>


static int outputNum[10];


int main() {

    int n;

    scanf("%d", &n);

    while( n-- ){

        int num;
        scanf("%d", &num);

        memset(outputNum, 0, sizeof outputNum);


        /**
         * It is possible to count the digits without convert char array.
         * Count each digit using counting sort technique.
         */
        int k = 0;
        for(int i = 1; i <= num; ++i){

            int num = i;
            while(num){
                ++outputNum[num % 10];
                num /= 10;
            }
        }


        for(int i = 0; i < 10; ++i){
            if(i) printf(" ");
            printf("%d", outputNum[i]);
        }
        printf("\n");
    }

	return 0;
}

UVA Problem 12015 – Google is Feeling Lucky Solution

UVA Problem 12015 – Google is Feeling Lucky Solution:


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

Solving Technique:

This is a sorting problem. In this problem we need to find biggest relevance number ( the second input / parameter). Then print the strings associated with that number. Multiple numbers can have equal relevance in which case print all the matching strings.

Ideas:

This can be solved efficiently by sorting inputs and based on that only print the strings / web addresses with biggest relevance number. Then if a lower relevance number is found stop processing. Since it was sorted ( ascending – start from last index, descending – start from index 0 )  if any lower value is found, further processing won’t yield any large relevance value.

Another method is using priority queue and store elements in key value pair. Then pop the biggest values and print their string.

Here my implementation is simple get the max value. Then brute force search all inputs for that value. If any value match the biggest relevance value print the string.

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:

2
www.youtube.com 1
www.google.com 2
www.google.com.hk 3
www.alibaba.com 10
www.taobao.com 5
www.bad.com 10
www.good.com 7
www.fudan.edu.cn 8
www.university.edu.cn 9
acm.university.edu.cn 10
www.youtube.com 1
www.google.com 2
www.google.com.hk 3
www.alibaba.com 11
www.taobao.com 5
www.bad.com 10
www.good.com 7
www.fudan.edu.cn 8
acm.university.edu.cn 9
acm.university.edu.cn 10

 


Output:

Case #1:
www.alibaba.com
www.bad.com
acm.university.edu.cn
Case #2:
www.alibaba.com

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 12015 Google is feeling lucky
 */

#include<stdio.h>

static char s[10][100];
static unsigned r[10];

static unsigned c, n, max, i;

int main(){

    scanf("%u", &n);

    while(n--){
        scanf("%s %u", &s[0], &r[0]);
        max = r[0];

        for(i = 1; i < 10; ++i){
            scanf("%s %u", &s[i], &r[i]);
            if(r[i] > max)
                max = r[i];
        }

        printf("Case #%u:\n", ++c);
        for(i = 0; i < 10; ++i){
            if(r[i] == max)
                printf("%s\n", s[i]);
        }
    }
    return 0;
}

UVA Problem 12149 – Feynman Solution

UVA Problem 12149 – Feynman Solution:


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

Solving Technique:

The problem asks given a number n how many squares are there in n by n grid. The relation can be found out by drawing n*n sqares and counting the squares. Since it will be very hard to draw and count more than 4 by 4 grid. We can try 1 by 1, 2 by 2, 3 by 3, 4 by 4 grid and count the number of squares. From there we can try to guess an equation.

For,
1*1 grid =   1 Square = 1
2*2 grid =   5 Square = 1 + 2^2
3*3 grid = 14 Square = 1 + 2^2 + 3^2
4*4 grid = 30 Square = 1 + 2^2 + 3^2 + 4^2

Here the series is,
1^2 + 2^2 + 3^2 + 4^2 + ….. n^2
Which is the sum of first n squares.

Instead of calculating with this formula a simpler formula exists.
1^2 + 2^2 + … + n^2 = n(n + 1)(2n + 1) / 6

The proof for this formula can be found here.

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:

2
1
8
0

Output:

5
1
204

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 12149 Feynman
 * Type:    Mathematics ( 1^2 + 2^2 + .... + n^2 )
 */

#include<stdio.h>

int main(){
    static unsigned n;

    while(scanf("%u",&n) && n)
        printf("%u\n", n * (n + 1) * (2 * n + 1 ) / 6 );

    return 0;
}

UVA Problem 11727 – Cost Cutting Solution

UVA Problem 11727 – Cost Cutting Solution:


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

Solving Technique:

Very easy problem. We are given 3 numbers in each test case. Among those three numbers we need to print the median value.

Two codes given below one solved with simple if else branching, another one is solved using STL sort algorithm. Can be solved also using stl nth_element  but it is too much for this problem. Use of nth_element shown in UVA Problem 10041 Vito’s Family.

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 written in c and some in c++.


Input:

3
1000 2000 3000
3000 2500 1500
1500 1200 1800

 


Output:

Case 1: 2000
Case 2: 2500
Case 3: 1500

Code C:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 11727 - Cost Cutting
 */

#include<stdio.h>

int main(){
    static unsigned i, n, a, b, c;
    scanf("%u", &n);

    for(i = 1; i <= n; ++i){
        scanf("%u%u%u",&a,&b,&c);

        if(a > b && a > c)
            printf("Case %u: %u\n", i, b > c ? b : c);
        else if(b > c)
            printf("Case %u: %u\n", i, c > a ? c : a);
        else
            printf("Case %u: %u\n", i, a > b ? a : b);
    }
    return 0;
}

Code STL Sort:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 11727 - Cost Cutting
 */

#include<cstdio>
#include<algorithm>

static unsigned a[4];

int main(){
    static unsigned i, j, n;
    scanf("%u", &n);

    for(i = 1; i <= n; ++i){
        for(j = 0; j < 3; ++j)
            scanf("%u", &a[j]);

        std::sort(a, a + 3);
        printf("Case %u: %u\n", i, a[1]);
    }

    return 0;
}

UVA Problem 10327 – Flip Sort Solution

UVA Problem 10327 – Flip Sort Solution:


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

Solving Technique:

Another sorting problem that requires us to “exchange two adjacent terms”. Use any stable sort to count the number of swaps. That is the output.

Here among three code the first one is a hybrid distribution between insertion sort and merge sort to count inversions / swaps. The next two codes are merge sort and bubble sort.

This merge sort also be made to work with selection sort. Please see Introduction to Algorithms book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein for more detail.

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:

3
1 2 3
3
2 3 1

Output:

Minimum exchange operations : 0
Minimum exchange operations : 2

Hybrid Merge Sort and Insertion Sort Distribution:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10327 Flip Sort
 */

#include<stdio.h>
#include<limits.h>

#define INSERTION_SORT_THERSHOLD 20

static int A[1024], c;

void Merge(int front, int mid, int rear){
    int n1 = mid - front + 1;
    int n2 = rear - mid;

    int *L = new int[n1 + 1];
    int *R = new int[n2 + 1];

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front + i];

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];

    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = j = 0;

    /**
     * Might work without swaps by just incrementing index counters
     */
    register unsigned k = front;
    for(; k <= rear; ++k){
        if(L[i] <= R[j]){
            A[k] = L[i++];
            c += j;
        }
        else
            A[k] = R[j++];
    }
}

void insertionSort(int front, int rear) {
    register int i, j;
    int key;

    for (i = front + 1; i <= rear; ++i) {
        key = A[i];
        j = i - 1;
        while (j >= front && A[j] > key) {
            A[j + 1] = A[j];
            ++c;
            --j;
        }
        A[j + 1] = key;
    }
}

/**
 * Hybrid distribution between insertion sort and merge sort
 * Performs slower than regular merge sort for this small input range
 * Such distribution also works with selection sort
 * Please refer to book introduction to algorithm for more
 */
void HybridMergesort(int front, int rear){
    if(rear - front < INSERTION_SORT_THERSHOLD)
        insertionSort(front, rear);
    if(front < rear){
       int mid = (rear + front) >> 1;
       HybridMergesort(front, mid);
       HybridMergesort(mid + 1, rear);
       Merge(front, mid, rear);
    }
}

int main(){
    register unsigned int i, j, n;
    unsigned key;
	while(scanf("%u", &n) == 1){
        for(i = c = 0; i < n; ++i)
            scanf("%u", &A[i]);

        HybridMergesort(0, n - 1);

        printf("Minimum exchange operations : %u\n", c);
	}
	return 0;
}

Merge Sort Inversion Count:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10327 Flip Sort
 */

#include<stdio.h>
#include<limits.h>

static int A[1024], c;

void Merge(int front, int mid, int rear){
    int n1 = mid-front+1;
    int n2 = rear - mid;

    int *L = new int[n1 + 1];
    int *R = new int[n2 + 1];

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front + i];

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];

    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = j = 0;

    /**
     * Might work without swaps by just incrementing index counters
     */
    register unsigned k = front;
    for(; k <= rear; ++k){
        if(L[i] <= R[j]){
            A[k] = L[i++];
            c += j;
        }
        else
            A[k] = R[j++];
    }
}

void Mergesort(int front, int rear){
    if(front < rear){
       int mid = (rear + front) >> 1;
       Mergesort(front, mid);
       Mergesort(mid + 1, rear);
       Merge(front, mid, rear);
    }
}

int main(){
    register unsigned int i, j, n;
    unsigned key;
	while(scanf("%u", &n) == 1){
        for(i = c = 0; i < n; ++i)
            scanf("%u", &A[i]);
        Mergesort(0, n - 1);

        printf("Minimum exchange operations : %u\n", c);
	}
	return 0;
}

Bubble Sort Inversion Count:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10327 Flip Sort
 */

#include<cstdio>
#include<iostream>

static unsigned a[1024];

int main(){
    register unsigned int i, j, k, n;
	while(scanf("%u", &n) == 1){
        for(i = 0; i < n; ++i)
            scanf("%u", &a[i]);

        /**
         * Bubble Sort
         */
        for(k = j = 0; j < n; ++j){
            for(i = 0; i < n - j - 1; ++i){
                if(a[i] > a[i + 1]){
                    std::swap(a[i], a[i + 1]);
                    ++k;
                }
            }
        }

        printf("Minimum exchange operations : %u\n", k);
	}
	return 0;
}

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;
}