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

##### Sequence Traversal within Matrix:

##### Unraveling the Sequence:

##### Traversal Pattern and Sub structure/pattern:

##### Substructure and Movement within Matrix:

##### 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:

OR, In my code,

Note: Increment the index and diagonal also.

##### Filling the Matrix (1st code only):

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

##### About Space:

The first solution requires a total of 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 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; }