UVa : 10152 (ShellSort )


Title : ShellSort

Link : http://uva.onlinejudge.org/external/101/10152.html

Tricky Lines :

  1. a turtle can crawl out of its position in the stack and climb up over the other turtles to sit on the top.
  2. Print a blank line after each test case.

Analysis :

  1. Given initial stack and final stack. One operation possible : move any turtle from anywhere in initial stack and place it at top.
  2. Take two pointers, one points to the end of initial stack : ini
    and other points to the end of final stack : fin
  3. if ( initial [ini] == final [fin] )
    fin– and ini–
    // both are same, so we don’t need any movement
  4. if ( initial [ini] != final [fin] )
    // we need to move initial [ini]
    // but it may not be the right time to place initial [ini] at top
    // that is, its sure that, we have to move initial [ini], but we don’t know when to place it at top
    // so for now, move the initial [ini] from initial stack
    // as we have moved initial [ini], all the turtle before it should fall down one step
    // now go back to step 3
  5. at the end, we will reach at the top of initial stack, means ini = -1
    at this state u can’t compare, if ( initial [ini] == final [fin] )
  6. now its time to place previously moved turtles in correct order
  7. loop through fin to 0 and print final [fin]

Runtime : 0.388s

Critical input : 
5
9
Yertle
Duke of Earl
Sir Lancelot
Elizabeth Windsor
Michael Eisner
Richard M. Nixon
Mr. Rogers
Ford Perfect
Mack
Mack
Ford Perfect
Mr. Rogers
Richard M. Nixon
Michael Eisner
Elizabeth Windsor
Sir Lancelot
Duke of Earl
Yertle
5
a
b
c
d
e
e
d
b
a
c
6
b
c
e
a
f
d
a
b
c
d
e
f
2
hello
bye
bye
hello
1
hello
hello

Critical output :
Duke of Earl
Sir Lancelot
Elizabeth Windsor
Michael Eisner
Richard M. Nixon
Mr. Rogers
Ford Perfect
Mack

b
d
e

d
c
b
a

bye
< --- blank Line --- > // usual blank for case 4
< --- blank Line --- > // no output for case 5, but a blank line

Solution :

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;


int main ()
{
    int testCase;
    scanf ("%d", &testCase);

    while ( testCase-- ) {
        int turtle;
        scanf ("%d", &turtle);
        getchar ();

        char input [100];
        vector <string> initial;
        vector <string> final;

        for ( int i = 0; i < turtle; i++ ) {
            gets (input);
            initial.push_back (input);
        }

        for ( int i = 0; i < turtle; i++ ) {
            gets (input);
            final.push_back (input);
        }

        vector <string>::iterator ini = initial.end () - 1;
        vector <string>::iterator fin = final.end () - 1;
        map <string, bool> reserve;
        vector <string> output;

        while ( fin != final.begin () - 1 ) {
            if ( *fin == *ini ) fin--, ini--;
            else {
                if ( reserve [*fin] == true ) {
                    while ( ini != initial.begin () ) {
                        reserve [*ini] = true;
                        initial.erase (ini);
                        ini--;
                    }
                    reserve [initial [0]] = true;

                    while ( fin != final.begin () ) {
                        output.push_back (*fin);
                        fin--;
                    }

                    output.push_back (final [0]);
                    break;
                }

                else {
                    while ( *ini != *fin ) {
                        reserve [*ini] = true;
                        initial.erase (ini);
                        ini--;
                    }
                }

                fin--;
            }

        }

        for ( size_t i = 0; i < output.size (); i++ )
            cout << output [i] << endl;
        cout << endl;
    }

	return 0;
}

// @END_OF_SOURCE_CODE

One thought on “UVa : 10152 (ShellSort )

  1. #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #define maxi 1000001
    #define R 3
    #define C 3
    #define loop(VARIABLE, n) for(int VARIABLE = 0; VARIABLE < n; ++VARIABLE)
    #define loopi(VARIABLE, n) for(int VARIABLE = 0; VARIABLE > t;
    while(t–){
    cin >> n;
    map m;
    map::iterator it;
    map name;
    char c[10];
    getline(cin,s);
    vector init,fin;
    for(i=0;i<n;i++) init.push_back(i+1);
    for(i=0;i<n;i++){
    getline(cin,s);
    m[s]=i+1;
    name[i+1]=s;
    }
    for(i=0;i<n;i++){
    getline(cin,s);
    fin.push_back(m[s]);
    }
    int in=n-1,fi=n-1;
    while(in!=-1){
    if(init[in]==fin[fi]){
    in–;
    fi–;
    }
    else
    in–;
    }
    if(fi<0)
    {cout <=0){
    cout << name[fin[fi]];
    fi–;}
    if(fi<0)
    cout <=0){
    cout << endl << name[fin[fi]];
    fi–;
    }
    if(t)
    cout << endl;

    }
    return 0;
    }

    Can you look out why this solution is not getting accepted ?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s