## UVA Problem 264 – Count on Cantor Solution

UVA Problem 264 – Count on Cantor Solution:

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:

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 10008 – What’s Cryptanalysis? Solution

UVA Problem 10008 – What’s Cryptanalysis? Solution:

Solving Technique:

Task for this problem is to find occurrence of each alphabetical character. Uppercase and lowercase are treated as same characters. No other characters except for upper and lower case characters must be counted.

After counting their occurrence print them in most to least order. If multiple characters have same character count then print the characters alphabetically. Ex: If E occurred 2 times, A occurred 2 times then, print A first then E.

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
This is a test.
Count me 1 2 3 4 5.
Wow!!!! Is this question easy?


Output:

S 7
T 6
I 5
E 4
O 3
A 2
H 2
N 2
U 2
W 2
C 1
M 1
Q 1
Y 1


### Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10008 - What's Cryptanalysis
* Technique: Counting character occurrence in string,
*            Lexicographical / alphabetically sort characters,
*/

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

#define N 256

// Holds each character and its occurrence in string.
struct collection{
char character;
int occurence;
} node[26];

static char s[N];

// Sorts based on occurrence, if occurrence count is same
// then sort using lexicographical / alphabetically first character.
int cmp(collection a, collection b){

if(a.occurence < b.occurence)
return 0;
else if(a.occurence > b.occurence)
return 1;
else
return (a.character <= b.character) ? 1 : 0;

}

int main(){

// O(1)
// Represent character by its ASCII value index.
for(int i = 'A'; i <= 'Z'; ++i)
node[i].character = i;

int n;

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

while( n-- ){

gets( s );

// Convert string to uppercase O(n)
for(int i = 0; s[i]; ++i){
if( s[i] >= 'a' && s[i] <= 'z')
s[i] = s[i] - 32;
}

// O(n)
// Counting using character index
for(int i = 0; s[i]; ++i){
if( s[i] >= 'A' && s[i] <= 'Z' )
++node[ s[i] ].occurence;
}

}

// Sorts occurrence most to least and in lexicographic order.
std::sort(node + 'A', node + 'Z', cmp);

// O(1)
// Prints sorted occurrence most to least.
// Also prints characters in lexicographic
// order if two occurrence are same.
for(int i = 'A'; i <= 'Z'; ++i){
if(node[i].occurence)
printf("%c %d\n", node[i].character, node[i].occurence);
}

return 0;
}


## UVA Problem 11713 – Abstract Names Solution

UVA Problem 11713 – Abstract Names Solution:

Solving Technique:

For input of n there will be 2*n lines. Task is to match a pair of lines. The vowels a, e, i, o, u in the strings doesn’t matter. Except these the rest of both strings should match.

That means each character in a index from both strings should match. Their order needs to be same. Except vowels if the match then output is yes. Otherwise the output is no.

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:

5
pele
polo
pele
pola
ronaldo
ronaldino
pele
pelet
pele
bele


Output:

Yes
Yes
No
No
No


### Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 11713 - Abstract Names
* Technique: Removing specific characters from string
*            by copying into another string.
*/

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

#define N 36

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

static char tmpS[N];
static char tmpT[N];

int main(){

int n;

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

while( n-- ){

gets(s);
gets(t);

// If their length is not the same then output is no.
if( strlen(s) != strlen(t) ){
printf("No\n");
continue;
}

// Reset memory.
int j = 0, k = 0;
memset(tmpS, 0, sizeof tmpS);
memset(tmpT, 0, sizeof tmpT);

// Remove vowels from the first string.
for(int i = 0; s[i]; ++i){
if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
continue;
else
tmpS[j++] = s[i];
}

// Remove vowels from the second the string.
for(int i = 0; t[i]; ++i){
if(t[i] == 'a' || t[i] == 'e' || t[i] == 'i' || t[i] == 'o' || t[i] == 'u')
continue;
else
tmpT[k++] = t[i];
}

// After removing the vowels the strings should match.
if( strcmp(tmpS, tmpT) == 0 )
printf("Yes\n");
else
printf("No\n");

}

return 0;
}


## UVA Problem 424 – Integer Inquiry Solution

UVA Problem 424 – Integer Inquiry Solution:

Solving Technique:

This problem requires adding integers. The integers are very long, meaning they won’t fit even in long long. So the addition needs to be done using arrays.

It can be solved using integers arrays but my solution uses character array. Code is explained in the comments.

Similar to this problem UVA 10035 Primary Arithmetic and UVA 713 – Adding Reversed Numbers.

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:

123456789012345678901234567890
123456789012345678901234567890
123456789012345678901234567890
0


Output:

370370367037037036703703703670


### Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 424 - Integer Inquiry
* Technique: Adding Multi String Integer characters column wise
*/

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

#define N 160

static char s[N][N];
static char output[N];

int main(){

int i = 0;

int maxlen = 0;

// Finish taking all the inputs.
while( gets(s[i]) ){

// Exit for input of 0.
if( s[i][0] == '0' && ! s[i][1] )
break;

int len = strlen( s[i] );

// Get the max length to create padding.
if( len > maxlen )
maxlen = len;

++i;
}

// Save rows
int rows = i;

// Create padding for each of the strings.
for(int j = 0; j < i; ++j){

int temp = strlen( s[j] );

if( temp != maxlen ){

// Shift by this many spaces to create 0's in front.
int padding = maxlen - temp;

for(int k = temp - 1; k >= 0; --k)

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

int carry = 0, z = 0;

for(int j = maxlen - 1; j >= 0; --j){

int sum = 0;

for(int i = 0; i < rows; ++i)
sum += s[i][j] - '0';

// Add if any previous  carry
sum = sum + carry;

output[z++] = sum % 10 + '0';

// get the carry for adding to next column
carry = sum / 10;

}

// Print if any carry first
if(carry)
printf("%d", carry);

// Then print what ever character is left
for(int i = z - 1; i >= 0; --i){
if(output[i] >= '0' && output[i] <= '9')
printf("%c", output[i]);
}
printf("\n");

return 0;
}


## UVA Problem 10035 – Primary Arithmetic Solution

UVA Problem 10035 – Primary Arithmetic Solution:

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
*            Making two strings of same length,
*/

#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);

// Shift each characters in string right by padding length.
if( lens > lent ){

int padding = lens - lent;

for(int i = lent - 1; i >= 0; --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)

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 713 – Adding Reversed Numbers Solution

UVA Problem 713 – Adding Reversed Numbers Solution:

Solving Technique:

The biggest problem in this problem is that there is no built in data type to hold 200 digit numbers. Although this problem is good in sense that it says that the number can be 200 characters long.

To handle this large number array is needed. while others may have solved using integer array and their methods may be faster. But mine addition is using character array.

##### For example using first method,

when input is 24 and 1, their reversal is,

42
01
==
43


Since i am using right most column as 0 th index. So the result will be 34.

Again for input 4358 and 754,

8534
0457
====
8991


Result will be 1998. This is because i am starting calculation from rightmost column and moving carry to left.

##### Another method is adding as is then print result from left,
4358
7540
====
1998


I’ve implemented the first method only. The code is explained in 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++.

More Inputs of This Problem on uDebug.

Input:

3
24 1
4358 754
305 794


Output:

34
1998
1


### Code:

/***********************************************************************
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 1225 - Digit Counting
* Technique: Reverse string or character array,
*            Shift characters in string by given number of spaces,
*            add two character array or strings,
***********************************************************************/

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

#define N 512

static char* firstNumber;
static char* secondNumber;

static char input[N];

/*********************************************************************
* Pass a string and a Integer length greater than the String length.
* The function will add leading 0's to the string. The length of the
* new string will be equal to the passes integer.
*********************************************************************/
char* fixLength(char* number, int maxlen){

/**
* Calculate padding or the amount positions to shift digits to the right.
* If length of string is 5 and maxlen is 8 then each digit starting from
* the end will be shifted 3 places to the right.
*
* Ex: Original String = "25634", Modified String = "00025634"
*/
int numLength = strlen(number);
int padding = maxlen - numLength;

/**
* Starting from the end of given string shift each character to the right
*
* Character are shifted from rear otherwise beginning from 0 index will
* replace existing character in the string and output string will be garbage.
*/
for(int i = numLength - 1; i >= 0; --i)

/**
*/
for(int i = 0; i < padding; ++i)
number[i] = '0';

/**
* Mark end of String
*/
number[maxlen] = '\0';

return number;
}

/*********************************************************************
* Given a string and its length this function reverses the string.
* It first discards any leading 0's in the input string then reverses
* the input string.
*********************************************************************/
char* reverseString( char* number, int len ){

/**
* Initialize a new char array to keep the string after discarding
*/
char* tempNumber = new char[N];
int k = 0, i;

/**
*/
for(i = 0; i < len; ++i)
if(number[i] - '0') break;
for(; i < len; ++i)
tempNumber[k++] = number[i];
tempNumber[k] = '\0';

/**
* Reverse the new string without leading zeros.
*/
int tmp = k / 2;
for(int i = 0, j = k - 1; i < tmp; ++i, --j){
int swap = tempNumber[i];
tempNumber[i] = tempNumber[j];
tempNumber[j] = swap;
}

return tempNumber;
}

/**********************************************************************************
* Starting from the last column add two integers. Then add any carry to the left
* column. This way calculate the addition. In the end if any carry left add it
* to the output char array. For safety assume last carry can be bigger than one
* digit.
**********************************************************************************/
void add( char* firstNumber, char* secondNumber, int lengthFirst, int lengthSecond){

/**
* Initialize a new array to keep sum of two number strings.
*/
char* tempNumber = new char[N];
int k = 0;
int sum = 0;
int carry = 0;

/**
* Starting from last column move left to 0th index. Add the numbers and if there
* is carry add it to left column.
*/
for(int j = lengthFirst - 1; j >= 0; --j){

sum = firstNumber[j] - '0' + secondNumber[j] - '0';

// Add if any previous carry
sum = sum + carry;

// place the part of output number
tempNumber[k++] = (sum % 10) + '0';

// calculate the the carry
carry = sum / 10;
}

/**
* Assuming last carry can be more than one digit. Add carry digits to output array.
*/
while(carry){
tempNumber[k++] = (carry % 10) + '0';
carry /= 10;
}
tempNumber[k] = '\0';

/**
*/
int p = 0;
for(; p < k; ++p)
if(tempNumber[p] - '0') break;

for(; p < k; ++p)
printf("%c", tempNumber[p]);
printf("\n");

}

int main() {

/**
* Important allocate memory for the numbers.
*/
firstNumber = new char[N];
secondNumber = new char[N];

int n;

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

while(n--){

int j = 0, k = 0;

/**
* Take input of two numbers as strings.
*/
scanf("%s%s", firstNumber, secondNumber);

/**
* Get each of their length.
*/
int firstNumberLength = strlen(firstNumber);
int secondNumberLength = strlen(secondNumber);

/**
* Initial guess the first number string is bigger.
*/
int maxlen = firstNumberLength;

/**
* Reverse both of the number string.
*/
firstNumber = reverseString(firstNumber, firstNumberLength);
secondNumber = reverseString(secondNumber, secondNumberLength);

/**
* Pass in the smaller number string and bigger number string size.
*
* If initial guess of first number is bigger is wrong then update
* the max length with second number length.
*/
if( firstNumberLength < secondNumberLength ){
firstNumber = fixLength(firstNumber, secondNumberLength);
maxlen = secondNumberLength;
}
else
secondNumber = fixLength(secondNumber, firstNumberLength);

/**
* Now pass in the two numbers and max length to add them and print answer.
* Notice here i pass the same argument twice this need to be fixed and also
* there are many more improvements needed in other functions.
*/

}

return 0;
}


## UVA Problem 1225 – Digit Counting Solution

UVA Problem 1225 – Digit Counting Solution:

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 10699 – Count the factors Solution

UVA Problem 10699 – Count the factors Solution:

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:

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