## 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 10696 – f91 Solution

UVA Problem 10696 – f91 Solution:

Solving Technique:

This is a simple DP problem (OR, so it looks but there’s a better way). It can be solved both iteratively and recursively with or without memoization. Still it will get accepted. But still the runtime is slow due huge input. So using a faster io may help it get accepted with a better rank.

For the matter of practice i will show all four methods i know of to solve this problem. Codes are given in this order,

1. dynamic programming solution.
2. Recursive solution without Memoization.
3. Recursive solution with Memoization.
4. Shortcut Trickery.
5. Maybe extend the shortcut Trickery with memoization or other technique by yourself ? try it !!

#### Solution explanation:

Here the formula is given, we just need rearrange it and get the recurrence relation,

If N ≤ 100, then f91(N) = f91(f91(N+11));
If N ≥ 101, then f91(N) = N-10.

So from the given statement generating recurrence relation will be,

f(n) = { f(f(n+11)), if n <= 100
{ n - 10,     if n >= 101


Here base case is for any n greater than or equal to 101 is return n – 10. No more recursive call on that.
This can be simplified but i won’t go into that. The codes below will give a better idea.

Now, just create a function named f and use if else or ternary to implement the given relation and it’ll work.

#### Memoization:

Since we’ve found out the recurrence relation it won’t be hard to memoize the code. We can use a memo array to store the already calculated results. We need not change much from the previous recursive solution to memoize it.

Add an if condition in the beginning if the value is already calculated and stored in memo array just return. Other wise when returning just store the return values in memo.

That’s it.

#### Dynamic Programming ( bottom up method ):

Our recurrence relation will never change. Since there is no other function needed we just calculate and store values in memo array. I started from 1,000,000 because the problem statement said an integer may be at most 1,000,000. Just loop through that many times and store results in memo array.

##### Last Solution Trick:

It come to me when i was testing my own inputs. Anything less or equal 100 result in 91. Any greater value results in that value minus 10. Take a look at the code below to get the idea.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

Input:

500
91
1
5
190
100
101
0

Output:

490
91
91
91
180
91
91

### Code Bottom Up (Iterative) Dynamic Programming:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10696 - f91
* Type:    Bottom Up (Iterative) Dynamic Programming
*/

#include<cstdio>
#include<sstream>

using namespace std;

#define N 1000000

static int F[N];

int main(){
int n, i;

for(i = N; i >= 0; --i){
if(i >= 101)
F[i] = i - 10;
else
F[i] = F[F[i + 11]];
}

while(scanf("%d", &n) && n)
printf("f91(%d) = %d\n", n, F[n]);

return 0;
}


### Code Top Down (Recursive) Without Memoization:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10696 - f91
* Type:    Top Down (Recursive) without Memoization
*/

#include<stdio.h>

int f(int n){
return (n >= 101) ? n - 10 : f(f(n + 11));
}

int main(){
int n;

while(scanf("%d",&n) && n)
printf("f91(%d) = %d\n", n, f(n));

return 0;
}


### Code Top Down (Recursive) with Memoization:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10696 - f91
* Type:    Top Down (Recursive) with Memoization
*/

#include<stdio.h>

static unsigned F[1000000];

unsigned f(unsigned n){
if(F[n])
return F[n];

if(n >= 101)
return F[n] = n - 10;
else
return F[n] = f(f(n+11));
}

int main(){
unsigned n;

while(scanf("%u",&n) && n)
printf("f91(%u) = %u\n", n, f(n));

return 0;
}


### Shortcut Technique:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10696 - f91
* Type:    shortcut technique
*/

#include<stdio.h>

int main(){
unsigned n;

while(scanf("%u", &n) && n){
if(n <= 100)
printf("f91(%d) = 91\n", n);
else
printf("f91(%d) = %d\n", n, n - 10);
}

return 0;
}


## Lower Bound of Fibonacci Big Omega Time Complexity

Lower Bound of Fibonacci Big Omega Time Complexity:

### Code for Recursive Fibonacci Algorithm:

int fib(int n){
if (n < 2)
return n;
else
return fib(n - 1) + fib(n - 2);
}


### Time Complexity Lower Bound ( Big Omega ):

Detailed explanation for calculating the upper and lower bound can be found here.

T(n) =  T(n-1) + T(n-2) + c
=  T(n-2) + T(n-3) + c + T(n-2) + c
=  2T(n-2) + T(n-3) + 2c
>= 2T(n-2) + 2c
=  2T(n-3) + T(n-4) + c) + 2c
=  2T(n-3) + 2T(n-4) + 2c + 2c
=  2T(n-3) + 2T(n-4) + 4c
=  2T(n-4) + 2T(n-5) + 2c + 2T(n-4) + 4c
=  4T(n-4) + 2T(n-5) + 6c
>= 4T(n-4) + 6c
=  4T(n-5) + 4T(n-6) + 10c
=  4T(n-6) + 4T(n-7) + 4c + 4T(n-6) + 10c
=  8T(n-6) + 4T(n-7) + 14c
>= 8T(n-6) + 14c
=  .......................
=  .......................
=  2^k T(n - 2k) + (2^(k+1)-2)c

for, k steps, n - 2k = 0 or, 1 the recursion stops
=> n = 2k
=> k = n / 2

so, from the recurrence relation
= 2^(n/2) * T(0) + (2^((n/2) +1) -2) * c
= 2^(n/2) * c + (2^((n/2) +1) -2) * c
= Ω(2^(n/2))


So, the lower bound of for this recursive Fibonacci algorithm implementation is Big Omega of 2n / 2.

Lower Bound:  Ω ( 2n / 2  )