UVA Problem 417 – Word Index Solution

UVA Problem 417 – Word Index Solution:


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

Solving Technique:

This one of the worst code I have ever written. It is both slow and wastes huge amount of memory, but still works. I am sharing this code as an example 5 dimensional re-sizable (vector) array. There are far far far better solution than this, so I won’t explain it.

If the input is thought of as string, then for each position the character right to current character is at least current character plus one. Since there are 5 length classes 1,2,3,4,5. So for each of them I applied this logic.

 

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:

26
1
0
83681

 


Output:

z
a
cat
vwxyz

Code:

/**
 * Author:    Asif Ahmed
 * site:      quickgrid.wordpress.com
 * Problem:   UVA 417 - word index
 * Technique: Very Slow and worst possible solution.
 *            5 (five) dimensioanl vector integer array. 1, 2
 *            3, 4 (four) dimensional integer array.
 */

#include <vector>
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;


#define N 26


int main() {


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


    vector<vector<vector<vector<vector<int> > > > > array5d;


      array5d.resize(N);
      for (int i = 0; i < N; ++i) {
        array5d[i].resize(N);

        for (int j = 0; j < N; ++j){
          array5d[i][j].resize(N);

            for (int k = 0; k < N; ++k){
              array5d[i][j][k].resize(N);

                for (int m = 0; m < N; ++m){
                  array5d[i][j][k][m].resize(N);
                }

            }
        }

      }

        int s1[N];
        int s2[N][N];
        int s3[N][N][N];
        int s4[N][N][N][N];
        int n = 0;


        for(int i = 0; i < N; ++i)
            s1[i] = ++n;



        for(int i = 0; i < N; ++i){
            for(int j = i + 1; j < N; ++j){
                s2[i][j] = ++n;

            }
        }



        for(int i = 0; i < N; ++i){
            for(int j = i + 1; j < N; ++j){
                for(int k = j + 1; k < N; ++k){

                        s3[i][j][k] = ++n;

                }
            }
        }




        for(int i = 0; i < N; ++i){
            for(int j = i + 1; j < N; ++j){
                for(int k = j + 1; k < N; ++k){
                    for(int m = k + 1; m < N; ++m){

                        s4[i][j][k][m] = ++n;

                    }
                }
            }
        }




        for(int i = 0; i < N; ++i){
            for(int j = i + 1; j < N; ++j){
                for(int k = j + 1; k < N; ++k){
                    for(int m = k + 1; m < N; ++m){
                        for(int t = m + 1; t < N; ++t){

                            array5d[i][j][k][m][t] = ++n;

                        }

                    }
                }
            }
        }




        char input[N];

        while( gets(input) ){

            int len = strlen(input);

            switch(len){
            case 1:
                printf("%d\n", s1[ input[0] - 'a' ] );
                break;
            case 2:
                printf("%d\n", s2[ input[0] - 'a' ][ input[1] - 'a' ] );
                break;
            case 3:
                printf("%d\n", s3[ input[0] - 'a' ][ input[1] - 'a' ][ input[2] - 'a' ] );
                break;
            case 4:
                printf("%d\n", s4[ input[0] - 'a' ][ input[1] - 'a' ][ input[2] - 'a' ][ input[3] - 'a' ] );
                break;
            case 5:
                printf("%d\n", array5d[ input[0] - 'a' ][ input[1] - 'a' ][ input[2] - 'a' ][ input[3] - 'a' ][ input[4] - 'a' ] );
                break;
            }

       }



  return 0;
}

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s