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.

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 264 – Count on Cantor Solution

UVA Problem 264 – Count on Cantor Solution:

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

Solving Technique:

Warning this is a terrible dynamic programming and memoization solution. If you want a fast and efficient solution then, this isn’t what you are looking for.

Problem Statement:

Given an input integer that represent a rational number sequence term shown by cantor, output the rational number for that term.

Solution Types:

I have given two solution, one of which uses a 2D array to store the rational number sequence as shown by cantor and using a traversal pattern memoize the series in another array. Although the first one can be improved to only traverse 1/4 th of the array but that’s still a lot.

The next solution discards the 2D array and using the traversal pattern with some optimization memoizes the series.

The time difference as of UVA submission running time is,

0.245 ms (1st technique)
0.072 ms (2nd technique)

Removing the recursion by replacing with iterative version ( A bit harder to do ) will make it even faster. I think this one can be further improved but have no idea how.

Figuring out the algorithm:

Note everything here is assuming indexing starts from 1 instead of 0. But in my code I start with index 0 instead of 1.

Points To Notice:

1. Moves right when row number is 0 and column number is even.
2. Moves down-left when row number is 0 and column number is odd.
3. Moves down when column number is 0 and column number is odd.
4. Moves up-right when column number is 0 and column number is even.
5. Diagonal traversal gets bigger by 1 unit for each down or right movements.

Traversing the Matrix:

$Traverse(r,c,index,diagonal) = \begin{cases} \rightarrow \text{(1 times)} & \forall : row = 0; col \in Even \\ \swarrow \text{(c - 1 times)} & \forall : row = 0; col \in Odd \\ \downarrow \ \ \text{(1 times)} & \forall : col = 0; row \in Odd \\ \nearrow \text{(r - 1 times)} & \forall : col = 0; row \in Even \\ \end{cases}$

OR, In my code,

$Traverse(r,c,index,diagonal) = \begin{cases} \rightarrow \text{(1 times)} & \forall : row = 0; col \in Even \\ \swarrow \text{(c + diagonal times)} & \forall : row = 0; col \in Odd \\ \downarrow \ \ \text{(1 times)} & \forall : col = 0; row \in Odd \\ \nearrow \text{(r + diagonal times)} & \forall : col = 0; row \in Even \\ \end{cases}$

Note: Increment the index and diagonal also.

Filling the Matrix (1st code only):

$CantorTable_{i,j} = \begin{cases} numerator = row, & \forall : Column, rows \\ denominator = column, & \forall : Column, rows \\ \end{cases}$

Base case:

Note when row or the column is equal to 0 then there is a turn. If row or column becomes less than 0 then it should stop.

Also the amount values to memoize is N which is the maximum cantor sequence value for this problem. So if N values are memoized then the process should stop.

if (r < 0 || c < 0 || index > M)
return;


Storing the fractions in 2D Struct Array:

Instead of storing the values in string it is better to store the fraction in a struct. There are 3 things in the fraction the numerator, a division sign , the denominator. There is no need to store the division sign since all elements within matrix are fraction.

struct CantorSequence{
int numerator;
int denominator;
};


The first solution requires a total of $O( M + \frac{N(N+1)}{2} )$ space including storing the cantor sequence in another array and pre calculating the 2D cantor table and traversing.

The second solution requires a total of $O( M )$ space including storing the cantor sequence in another array.

Here, M is 10000000 and N is 4500. N can be adjusted but 4500 is a safe value.

Please point out if the post contains mistakes.

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
14
7
10000000


Output:

TERM 3 IS 2/1
TERM 14 IS 2/4
TERM 7 IS 1/4
TERM 10000000 IS 2844/1629


Code Recursive DP 2D struct Traversal and Memoize:

/***********************************************************************
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 264 - Count on Cantor
*
* Technique: Zig Zag / Spiral Diagonal traversal,
*            2D struct array,
*            2D half diagonal fill,
*            Recursive Dynamic Programming
***********************************************************************/

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

// N * N should be almost twice greater than or equal to M.
// Or, N should be such that N*(N+1)/2 is greater than M.
#define N 4500

#define M 10000000

/**
* Table to construct the sequence
*/
struct CantorTable{
int numerator;
int denominator;
} CT[N][N];

// Holds cantor values from 1 to M by index
CantorTable OrderedCantor[M];

/**
* Fill in the cantor table.
*/
void CantorFill(){

for(int row = 0; row < N; ++row){

int cutoff = N - row;

for(int col = 0; col < cutoff; ++col){
CT[row][col].numerator   = row + 1;
CT[row][col].denominator = col + 1;
}

}

}

void RecursiveCantor(int r, int c, int index, int diagonal){

// base case
if( r < 0 || c < 0 || index > M ){
return;
}

OrderedCantor[index].numerator = CT[r][c].numerator;
OrderedCantor[index].denominator = CT[r][c].denominator;

// Amount of times to travel in diagonal
++diagonal;

if(r == 0){

// when odd move down left
if(c % 2){
for(int i = 0; i < c + diagonal; ++i){
++index;
r = r + 1;
c = c - 1;
RecursiveCantor( r, c, index, diagonal );
}
}

// when even Move right
else{
++index;
c = c + 1;
RecursiveCantor( r, c, index, diagonal );
}
}

if(c == 0){

// when odd move down
if(r % 2){
++index;
r = r + 1;
RecursiveCantor( r, c, index, diagonal );
}

// when even Move up right
else{
for(int i = 0; i < r + diagonal; ++i){
++index;
r = r - 1;
c = c + 1;
RecursiveCantor( r, c, index, diagonal );
}
}

}

}

int main() {

// Initialize Cantor table
CantorFill();

// Pass in row, column, index, diagonal traversal size
RecursiveCantor(0, 0, 1, 0);

int n;

while( scanf("%d", &n) == 1 ){
printf("TERM %d IS %d/%d\n", n, OrderedCantor[n].numerator, OrderedCantor[n].denominator );
}

return 0;
}



Code Recursive DP Sequence Memoize:

/***********************************************************************
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 264 - Count on Cantor
*
* Technique: Zig Zag / Spiral Diagonal traversal,
*            Recursive Dynamic Programming
***********************************************************************/

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

#define M 10000000

/**
* Table to construct the sequence
*/
struct CantorTable{
int numerator;
int denominator;
};

// Holds cantor values from 1 to M by index
CantorTable OrderedCantor[M];

void RecursiveCantor(int r, int c, int index, int diagonal){

// base case
if( r < 0 || c < 0 || index > M ){
return;
}

// change from table traversed DP
OrderedCantor[index].numerator = r + 1;
OrderedCantor[index].denominator = c + 1;

// Amount of times to travel in diagonal
++diagonal;

if(r == 0){

// when odd move down left
if(c % 2){
for(int i = 0; i < c + diagonal; ++i){
++index;
r = r + 1;
c = c - 1;
RecursiveCantor( r, c, index, diagonal );
}
}

// when even Move right
else{
++index;
c = c + 1;
RecursiveCantor( r, c, index, diagonal );
}
}

else if(c == 0){

// when odd move down
if(r % 2){
++index;
r = r + 1;
RecursiveCantor( r, c, index, diagonal );
}

// when even Move up right
else{
for(int i = 0; i < r + diagonal; ++i){
++index;
r = r - 1;
c = c + 1;
RecursiveCantor( r, c, index, diagonal );
}
}

}

}

int main() {

// Pass in row, column, index, diagonal traversal size
RecursiveCantor(0, 0, 1, 0);

int n;

while( scanf("%d", &n) == 1 ){
printf("TERM %d IS %d/%d\n", n, OrderedCantor[n].numerator, OrderedCantor[n].denominator );
}

return 0;
}


UVA Problem 10921 – Find the Telephone Solution

UVA Problem 10921 – Find the Telephone Solution:

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

Solving Technique:

Given a string of alphabets (A-Z), 1, 0, and Hyphens( – ) task for this problem is to find numbers represented by a character from the given table.

1, 0, Hyphen should not be changed since they aren’t in table. Just change a character with its integer representation from table. Easiest way to do this is create a mapping array with pattern from the table. Then map the pattern to each character and print result.

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-HOME-SWEET-HOME
MY-MISERABLE-JOB


Output:

1-4663-79338-4663
69-647372253-562


Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10921 - Find The Telephone
* Technique: Mapping character from an array to another.
*/

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

#define N 128

static char mappingArray[N] = "22233344455566677778889999";

static char table[N];
static char input[N];

int main(){

/**
* The code below fill 'A' to 'O' with appropriate values.
* Not necessary when using mapping array.
*/
/*
for(int i = 0; i <= 15; ++i ){
table[64 + i] = k;
if(i % 3 == 0) ++k;
}
*/

int k = 0;

/**
* Map each character index to integer value from mapping array.
*/
for(int i = 'A'; i <= 'Z'; ++i)
table[i] = mappingArray[k++];

/**
* These characters don't change.
*/
table['-'] = '-';
table['0'] = '0';
table['1'] = '1';

/**
* Take input, then iterate through each character
* and print the character indexed value from table.
*/
while( gets(input) ){
for(int i = 0; input[i]; ++i)
printf("%c", table[ input[i] ]);
printf("\n");
}

return 0;
}


UVA Problem 10035 – Primary Arithmetic Solution

UVA Problem 10035 – Primary Arithmetic Solution:

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

Solving Technique:

For this problem two integers less than 10 digits are given. The task is to find how many carry operations occur when adding.

This problem may be solved using strings since input integer is less than 10 digits. It can be solved with out using array. My implementation is using character array to add and count carry operations.

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:

123 456
555 555
123 594
0 0


Output:

No carry operation.
3 carry operations.
1 carry operation.


Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10035 - Primary Arithmetic
* Technique: Adding leading 0's integer string,
*            Making two strings of same length,
*            Adding String Integers.
*/

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

#define N 128

static char s[N];
static char t[N];

static char output[N];

int main(){

while( scanf("%s", s) && scanf("%s", t) ){

// Although a major flaw input beginning with 0 and
// two strings matching. But for this problem it doesn't matter.
if( strcmp(s,t) == 0 && s[0] == '0' )
break;

int lens = strlen(s);
int lent = strlen(t);

// Add leading 0's to smaller string (May not be necessary).
// Shift each characters in string right by padding length.
if( lens > lent ){

int padding = lens - lent;

for(int i = lent - 1; i >= 0; --i)
t[i + padding] = t[i];

for(int i = 0; i < padding; ++i)
t[i] = '0';
}

else if( lens < lent ){

int padding = lent - lens;

for(int i = lens - 1; i >= 0; --i)
s[i + padding] = s[i];

for(int i = 0; i < padding; ++i)
s[i] = '0';
}

int maxlen;
if(lens > lent)
maxlen = lens;
else maxlen = lent;

int carry = 0;
int c = 0;
int sum = 0;

// Add two Strings, if a carry operation occurs
// then add that to the count.
for(int i = maxlen - 1; i >= 0; --i){

sum += s[i] - '0' + t[i] - '0';

sum = sum + carry;

carry = sum / 10;

if(carry)
++c;

sum = 0;

}

if(!c)
printf("No carry operation.\n");
else if( c > 1 )
printf("%d carry operations.\n", c);
else
printf("%d carry operation.\n", c);

}

return 0;
}


UVA Problem 10699 – Count the factors Solution

UVA Problem 10699 – Count the factors Solution:

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

Solving Technique:

The problem requirement is to find the prime factors of a given number. If the input number is divisible by a prime number then that prime number is a prime factor of input.

Similarly do this with all prime numbers less than the input if it is divisible then increase prime factor count. It seems like there is a way to cut down running time in this very code, but I am not able find it.

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:

289384
930887
692778
636916
747794
238336
885387
760493
516650
641422
0


Output:

289384 : 3
930887 : 2
692778 : 5
636916 : 4
747794 : 3
238336 : 3
885387 : 2
760493 : 2
516650 : 3
641422 : 3


Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10699 - count the factors
* Technique: Efficient Prime Generation, Sieve of Eratosthenes.
*/

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

/**
* Since value can be up to 1000000
*/

#define N 1000000

int primesTable[N];
int onlyPrimesTable[N];

int k = 0;

void SieveOfEratosthenes(){

int i = 2;

/**
* Set Every index in the table to be prime.
*/
for(; i <= N; ++i)
primesTable[i] = 1;

/**
* Base case 0 and 1 are not primes.
*/
primesTable[0] = primesTable[1] = 0;

int len = sqrt(N);

/**
* Set all multiples of a number to 0 since primes can't divisible by other than itself.
*/
for(i = 2; i <= len; ++i){
if(primesTable[i]){
for( int k = i << 1; k <= N; k += i )
primesTable[k] = 0;
}
}

/**
* This is not really a part of Sieve of Eratosthenes.
* It checks if a number is prime then it moves primes
* to another array which only contain primes and this
* reduces the number of lookups.
*/
for(i = 0; i <= N; ++i){
if(primesTable[i])
onlyPrimesTable[k++] = i;
}
}

int main() {

/**
* Pre generate primes and isolate them to another array.
*/
SieveOfEratosthenes();

int n;

/**
* Input the number and check if its 0.
*/
while(scanf("%d", &n) && n){

int c = 0;

/**
* If the number is divisible by a prime then,
* increase prime factor count.
*/

for(int i = 0; i < k; ++i){
if( n % onlyPrimesTable[i] == 0)
++c;
}

printf("%d : %d\n", n, c);

}

return 0;
}


UVA Problem 10851 – 2D Hieroglyphs decoder Solution

UVA Problem 10851 – 2D Hieroglyphs decoder Solution:

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

Solving Technique:

This problem may look a little hard at first but the problem could be easily reverse engineered from the problem statement. Before starting this if you are familiar with UVA PROBLEM 10878 – DECODE THE TAPE then apply that knowledge. This problem is also very similar.

It is also possible to pre calculate a pattern table based on printable ASCII character then apply a string matching algorithm ( which is harder than this ). This is a reminder for myself and anyone else who wants to implement this method.

Here $\forall$ is called universal quantifier, so $\forall$ can be termed as for all and $\in$ means member of or, element of or, in.

Dissecting problem statement to create pattern generator:

H is a 2D array. It is filled following rules below. I have used H as a function to generate the 2D pattern,

$H_{i,j} = \begin{cases} ' \backslash ' & \forall i = 0, j \in (0, 1, ..., M + 1) \\ ' \backslash ' & \forall i = 9, j \in (0, 1, ..., M + 1) \\ ' \backslash ' & \forall j = 0, j \in (0, 1, ..., 9) \\ ' \backslash ' & \forall j = M + 1, i \in (0, 1, ..., 9) \\ b(i - 1, c_{j-1}) & \forall i \in (1, 2, ..., 8) , j \in (1, ..., M) \\ \end{cases}$

Its Helper function,

$b(i, c) = \begin{cases} ' / ' & if, \ \frac{c}{2^i} \ mod \ 2 \ == \ 0 \\ ' \backslash ' & if, \ \frac{c}{2^i} \ mod \ 2 \ == \ 1 \\ \end{cases}$

As described in the problem statement M is the length of the string and their are M + 2 columns ( from 0 to M + 1 columns ). Also there will always be 10 rows of input.

When i is 0 or, i is 9 and j is from 0 to M + 1 print backslash.
Also when j is 0 or, j is M + 1 ( last column ) and i is from 0 to 9 then print backslash.

From above it is clearly visible there are two functions. H function depends on the b function to print slashes when i is 1 to 8 and j is 1 to M ( Length of String ). This means omitting the first, last row and first, last column.

When i is 1 to 8 and j is 1 to M the output depend on $b(i,c)$ function. Which prints a slash based on input. It checks if character ASCII decimal value divided by $2^i$ is even or, odd and based on that prints a slash.

Using these relations the pattern generator can be created.

Tracing the output:

It is not possible for me to show the whole string since it will be very large. I will show with String being, $c[M] = bc"$.

When, $i = 1 \ and \ j = 1$ the call to $b(i,c)$ begins with parameter $b(i-1, c[j - 1])$ which is,

$b(1-1, c[1-1]) = b(0,c[0]) = b(0, 'b')$

It loops M (strings) times for each row. Which in this case is 2 times,

$b(1-1, c[2-1]) = b(0, 'c')$

In the b(i,c) function it checks if, character divided by 2^i is even or odd and prints slashes based on that.

for $b(0,'b')$ it is calculated, $(98 / 2^0) % 2$ which is 0 so prints forward slash ‘/’.
for $b(0,'c')$ it is calculated, $(99 / 2^0)% 2$ which is 1 so prints backslash ‘\’.

The $b(i,c)$ is called M times for each row and 8 times for each column and a slash is printed based on that. The rest two times slashes are printed from the condition of $H_{i,j}$ function.

From this relation, setting 0 for forward slashed and 1 for backward slashed the column wise string looks like its in binary format. Where the top row is Least significant bit (LSB) and bottom row is Most significant bit (MSB). In case of ‘b’ character only first column shown from the above example string,

 row sign binary value 0 / 0 0 1 \ 1 2 2 / 0 0 3 / 0 0 4 / 0 0 5 \ 1 32 6 \ 1 64 7 / 0 0

Their sum is = 2 + 32 + 64 = 98 or, converting the binary to decimal gives a value of 98 which is the ASCII decimal value of ‘b’. Similarly, more characters are calculated if there are more columns.

Shortcut Technique:

Basically first, last row and column are useless. A character is decoded based on each column. A forward slash means 0 and a backslash mean 1. Just apply bit wise shift for each row in a column and add the value when backslash is found. From that value print is equivalent ASCII character.

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
///////////
/\/\/\/\/\/
//\\//\\///
////\\\\///
////////\\/
///////////
/\\\\\\\\\/
/\\\\\\\\\/
///////////
///////////

///////////////////////////////////////
//\///\/\\/\//\\/\//\/\\/\/\/\\/\/\//\/
///////\////\/\/\//////\//\////\/\/////
/\//\\\\///\\//\\/\\//\//\\//\///\/\\//
/\//\\//\///\////\\\//////\//\////\\\//
//////\\//////\/\//////\/\/////\/\/////
///\//////\//\///////\//\///\//////////
/\\/\\\\\\/\\/\\\\\\\/\\/\\\/\\\\\\\\\/
///////////////////////////////////////
///////////////////////////////////////


Output:

abcdefghi
LA LLUVIA EN SEVILLA ES UNA MARAVILLA


Critical Input Generator:

Warning!!!
This is not the solution just input generator for the problem. The Solution code is below this code.

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10851 - 2D Hieroglyphs Decoder Pattern / Input Generator
*/

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

//static char c[] = "bc";
//static char c[] = "abcdefghi";
static char c[] = "LA LLUVIA EN SEVILLA ES UNA MARAVILLA";

void b(int i, char ch){
// May be do a bitwise shift since power of 2
if( (ch / (long long) pow(2, i) ) % 2 == 0 )
printf("/");
else
printf("\\");
}

void H(int row, int M){
// String length is M and column is M + 2 so from 0 to M - 1
M = M + 2;

for(int i = 0; i < row; ++i ){

// This can be moved outside loop with little adjustment
if(i == 0 || i == row - 1){
for(int j = 0; j < M; ++j)
printf("/");
}

else{
for(int j = 0; j < M; ++j){
// Since M = M + 2 so j is j == (M - 1) = (M + 2 - 1) = (M + 1)
if(j == 0 || j == M - 1)
printf("/");
else
b(i - 1, c[j - 1]);
}
}

printf("\n");
}

}

int main(){

H(10, strlen(c) );

return 0;
}


Solution Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10851 - 2D Hieroglyphs Decoder
* Technique: Binary to Decimal, 2D row wise calculation.
*/

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

static char c[10][80];

int main(){

int n, i;

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

while( n-- ){

/**
* Reset each of the strings ignoring first and last row.
*/
for(i = 1; i < 9; ++i)
memset(c[i], 0, sizeof c[i]);

/**
* Reuse i for taking string inputs.
*/
i = 0;

/**
* Take input of 10 rows.
* Another logic is to discard first and last line when taking input.
* But this method is easier to code.
*/
while(gets(c[i]) && strlen(c[i]))
++i;

/**
* Take count of the column.
* Since input is a rectangle so any column length will work.
*/
int cols = strlen(c[0]);

/**
* Ignore last column.
* Also last row.
*/
cols = cols - 1;
i = i - 1;

/**
* k represents columns and j represents rows.
* k starts from 1 ignoring first column.
*/
for(int k = 1; k < cols; ++k){

// Reset for each column.
int sum = 0;
int shift = 1;

/**
* Ignoring the first and last character.
* i starts from 1 ignoring first row.
*/
for(int j = 1; j < i; ++j){

// Double slash means (for this case) in binary 1 and add that value.
// Otherwise its zero and no need to calculate in that case.
if( c[j][k] == '\\' )
sum = sum + shift;

// Bitwise shift left once for each column.
shift = shift << 1;
}

// Print character wise or use string then print outside this loop.
printf("%c", sum);
}

printf("\n");

}

return 0;
}


UVA Problem 865 – Substitution Cypher Solution

UVA Problem 865 – Substitution Cypher Solution:

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

Solving Technique:

Similar problems to this problem, UVA Problem 10082 – WERTYU Solution and also UVA Problem 11278 – One Handed Typist Solution.

In this problem we are given two strings one of which is plain text and the next one is its substitution. In the plain text string there are characters that are to be mapped to its substitution characters from the substitution string.

Next comes several lines of text in which plain characters that match the required substitution characters should be replaced to its substitution character equivalent. The characters that don’t match the substitution requirement should stay the same.

The hardest part of this problem is newlines. There is a new line after number of cases, so make sure to discard that. Also an empty line marks the end of text inputs for a test case. Last thing is there is a new line between test cases, so for the last output there shouldn’t be an extra new line.

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

abcdefghijklmnopqrstuvwxyz
zyxwvutsrqponmlkjihgfedcba
Shar's Birthday:
The birthday is October 6th, but the party will be Saturday,
October 5.  It's my 24th birthday and the first one in some
years for which I've been employed.  Plus, I have new clothes.
So I have cause to celebrate.  More importantly, though,
we've cleaned the house!  The address is 506-D Albert Street.
Extra enticement for CS geeks:  there are several systems in
the house, and the party is conveniently scheduled for 3 hours
after the second CSC programming contest ends (not to mention,
within easy walking distance)!


Output:

zyxwvutsrqponmlkjihgfedcba
abcdefghijklmnopqrstuvwxyz
Sszi'h Brigswzb:
Tsv yrigswzb rh Oxglyvi 6gs, yfg gsv kzigb droo yv Szgfiwzb,
Oxglyvi 5.  Ig'h nb 24gs yrigswzb zmw gsv urihg lmv rm hlnv
bvzih uli dsrxs I'ev yvvm vnkolbvw.  Pofh, I szev mvd xolgsvh.
Sl I szev xzfhv gl xvovyizgv.  Mliv rnkligzmgob, gslfts,
dv'ev xovzmvw gsv slfhv!  Tsv zwwivhh rh 506-D Aoyvig Sgivvg.
Ecgiz vmgrxvnvmg uli CS tvvph:  gsviv ziv hvevizo hbhgvnh rm
gsv slfhv, zmw gsv kzigb rh xlmevmrvmgob hxsvwfovw uli 3 slfih
zugvi gsv hvxlmw CSC kiltiznnrmt xlmgvhg vmwh (mlg gl nvmgrlm,
drgsrm vzhb dzoprmt wrhgzmxv)!


Code:

/**
* Author:    Quickgrid ( Asif Ahmed )
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 865 - Substitution Cypher
* Technique: Character Mapping, Array Mapping
*/

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

#define N 256

static char text[N];
static char plaintext[N];
static char substitution[N];

static char newLayout[N];

static char output[N];

int main(){

int n;

/**
* Input an integer.
* discard new line character for enter.
* discard empty line.
*/
scanf("%d", &n);
getchar();
getchar();

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

/**
* Print spaces between test cases.
*/
if(j)
printf("\n");

/**
* Input plain text and cipher text.
*/
gets(plaintext);
gets(substitution);

/**
* Map each character to its ASCII decimal value.
* In other words map the same character to itself.
*
* This is done because not all characters are changed by
* substitution cipher so rest of the characters map to itself.
*/
for(int i = 0; i < 256; ++i)
newLayout[i] = i;

/**
* Since plain text and cipher text will equal size any of them
* can be used to check termination condition.
*
* Inside the loop map plain text characters to its substitution.
*/
for(int i = 0; plaintext[i]; ++i)
newLayout[ plaintext[i] ] = substitution[i];

/**
* Print substitution string first and plain text as per requirement.
*/
puts(substitution);
puts(plaintext);

/**
* Now take input and scramble until a blank line is found.
*
* Here i have used string to output each line but character
* by character output will also work.
*/
while(gets(text) && strlen(text)){

memset(output, 0, sizeof output);

for( int i = 0; i < strlen( text ); ++i )
output[i] = newLayout[ text[i] ];

puts(output);

}

}

return 0;
}


UVA Problem 11278 – One-Handed Typist Solution

UVA Problem 11278 – One-Handed Typist Solution:

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

Solving Technique:

Before starting this you can check out a similar problem UVA Problem 10082 – WERTYU Solution. That problem is very similar to this and also somewhat similar to a Caesar Cipher with right shift of 1.

The problem deals with two keyboard layouts. The author typed dovrak key layout keys in standard keyboard layout by mistake. So he was actually pressing standard keys and now his output ( input in this problem ) looks scrambled. The task is to convert all typed standard key inputs to equivalent dvorak keys.

There are a few ways to solve this problem. One ways is to painstakingly map each standard key to a dvorak key.

Another way is to map ASCII table characters from Decimal 32 to 126 as standard keys. This can be done with a loop and another array with equivalent dvorak keys. This method is easier that is eliminates one array but then creating the dvorak array becomes time consuming.

The third way which which i used here is create two arrays containing standard and dvorak keys. Then map each standard key to a dvorak key.

The code below is explained with comments.

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:

Hg66t Mty6k!
Jhg 4ibl; pytmn 8tc 5i79urrr
t,gy jhg 6fxo kt.r

Output:

Hello World!
The quick brown fox jumps...
over the lazy dog.

Code Output as Characters:

/*
* Author:     Quickgrid ( Asif Ahmed )
* Site:       https://quickgrid.wordpress.com
* Problem:    UVA 11278 - One Handed Typist
* Techniques: Array mapping, Character mapping
*/

#include<stdio.h>

#define N  128
#define IO 1001

/**
* Heart of the problem. Be careful with mapping, one typo in mapping and the verdict is wrong.
* Here standard contains all the characters in standard keyboard including capital and small.
* dvorak contains all the characters in dvorak keyboard including capital and small.
*/
static const char standard[N] = "1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./~!@#$%^&*()_+QWERTYUIOP{}|ASDFGHJKL:\"ZXCVBNM<>? "; static const char dvorak[N] = "123qjlmfp/[]456.orsuyb;=\\789aehtdck-0zx,inwvg'~!@#QJLMFP?{}$%^>ORSUYB:+|&*(AEHTDCK_)ZX<INWVG\" ";

/**
* This is the mapping array. It holds mappings of dvorak to standard keyboard.
*/
static char mappingKB[N];

static char input[IO];

int main(){

/**
* Although mapping "mappingKB[ standard[i] ] = dvorak[i]" seems wrong and
* mapping from "mappingKB[ dvorak[i] ] = standard[i]" seems correct.
*
* But its wrong remember the coach was typing dvorak in standard keyboard keys
* instead of dvorak key mappings. Since the input was in standard keyboard and we should convert it to dvorak otherwise it looks
* scrambled.
*
* So the keys of standard keyboard maps to dvorak keys.
*/
for(int i = 0; dvorak[i]; ++i)
mappingKB[ standard[i] ] = dvorak[i];

while(gets(input)){

/**
* Convert standard keys to dvorak using pre-mapped array
*/
for(int i = 0; input[i]; ++i)
printf("%c", mappingKB[ input[i] ] );

printf("\n");

}

return 0;
}


Code Output as String:

/*
* Author:     Quickgrid ( Asif Ahmed )
* Site:       https://quickgrid.wordpress.com
* Problem:    UVA 11278 - One Handed Typist
* Techniques: Array mapping, Character mapping
*/

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

#define N  128
#define IO 1001

static const char standard[N] = "1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./~!@#$%^&*()_+QWERTYUIOP{}|ASDFGHJKL:\"ZXCVBNM<>? "; static const char dvorak[N] = "123qjlmfp/[]456.orsuyb;=\\789aehtdck-0zx,inwvg'~!@#QJLMFP?{}$%^>ORSUYB:+|&*(AEHTDCK_)ZX<INWVG\" ";

static char mappingKB[N];

static char input[IO];
static char output[IO];

int main(){

for(int i = 0; dvorak[i]; ++i)
mappingKB[ standard[i] ] = dvorak[i];

while(gets(input)){

// Reset memory otherwise character form previous input will be shown along with new
memset(output, 0, sizeof output);

for(int i = 0; input[i]; ++i)
output[i] = mappingKB[ input[i] ];

puts(output);

}

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.alibaba.com 10
www.taobao.com 5
www.good.com 7
www.fudan.edu.cn 8
www.university.edu.cn 9
acm.university.edu.cn 10
www.alibaba.com 11
www.taobao.com 5
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
acm.university.edu.cn
Case #2:
www.alibaba.com

Code:

/**
* @author  Quickgrid ( Asif Ahmed )
* 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;
}