10152 - ShellSort

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

seedosrun
New poster
Posts: 5
Joined: Tue Sep 30, 2003 6:46 am

I don't think so...

Post by seedosrun » Sat Oct 25, 2003 8:10 pm

I don't think that their are any special cases... What does your alogrithm look like?
Thanks,
Nicholas A. Hay
nhay@mvnu.edu

yo_sole
New poster
Posts: 2
Joined: Thu Oct 10, 2002 10:04 pm
Contact:

Shellsort

Post by yo_sole » Sun Oct 26, 2003 12:10 am

This is what I do:
void procesar()
{
int i,j, target;
target = n-1;
for (i = n-1; i >= 0; i--)
{
if( strcmp( unsorted[ i ], sorted[ target ]) == 0)
{
unsorted[0]= '\0';
target--;
}
}
for( i = n-1; i >= 0; i-- )
{
for( j = 0; j <n ; j++)
{
if( strcmp( unsorted[ j ], sorted[ i ]) == 0)
{
cout << unsorted[ j ]<<endl;
break;
}
}
}
}

I tried to change the strcmp() function with a function that don't take care of uppercase or lowercase letters. But the result is the same W.A.
My solution is running for 0.016 seconds. :(
Any thought?
Thanks
Sole

seedosrun
New poster
Posts: 5
Joined: Tue Sep 30, 2003 6:46 am

looks right to me...

Post by seedosrun » Sun Oct 26, 2003 12:33 am

It looks right to me... Can you send me your full code listing privately to see if i can see anything. Your logic is pretty much the same as mine but it just may be something small.
Thanks,
Nicholas A. Hay
nhay@mvnu.edu

OutCaster
New poster
Posts: 4
Joined: Thu Jan 22, 2004 2:24 am

10152 ShellSort .. WA

Post by OutCaster » Sun Apr 04, 2004 12:41 am

Hi

I'm getting the exact output as other people, but I'm still getting WrongAnswer in like 4.5 seconds ..

Here's some of my code, I'm not sure if I'm reading the information correctly, or maybe there are special cases that I need to check? ...

[java]
public static void main (String args[])
{
int cases = 0;
int total = 0;
String input;
input = Main.ReadLn (255);
cases = Integer.parseInt(input);
String[] Sorted;
String[] Unsorted;
for(int count = 0 ; count < cases; count++){

input = Main.ReadLn (255);
total = Integer.parseInt(input);

if(total >= 1)
{

Sorted = new String[total];
Unsorted = new String[total];

for(int uCount = 0 ; uCount < total ; ++uCount)
{
input = Main.ReadLn (255);
Unsorted[uCount] = input;
}

for(int sCount = 0 ; sCount < total ; ++sCount)
{
input = Main.ReadLn (255);
Sorted[sCount] = input;
}

/* Code for solving is here, I'm sure this part is correct so I didn't put it here */

System.out.println();
}
}
}
[/java]

Any ideas guys?

fangs404
New poster
Posts: 10
Joined: Thu Jan 22, 2004 3:32 am
Contact:

Post by fangs404 » Mon Apr 05, 2004 10:23 pm

here's the input/output that my accepted answer used:

input num of tests
input num of elements
input elements of unsorted elements
input elements of sorted elements
output answer
<space>
input num of elements
input elements of unsorted elements
input elements of sorted elements
output answer
<space>
input num of elements
input elements of unsorted elements
input elements of sorted elements
output answer
<space>
<space>

i hope that helps. good luck!
"God does not care about our mathematical difficulties. He integrates empirically."
-Albert Einstein

zacharyleung
New poster
Posts: 14
Joined: Tue Feb 03, 2004 3:43 am

10152 Shellsort--how do you make this faster?

Post by zacharyleung » Wed Apr 14, 2004 8:18 am

I've gotten an AC for this question. :D But my solution takes about 6 seconds to run, which is a lot longer than the fastest solutions (about 0.15 seconds) Any suggestions as to how to make this faster?

[cpp]
#include <cstdio>
#include <climits>
#include <cstring>

#define DEBUGI(var) printf( "%s = %d\n", #var, var ); fflush(stdout);
#define LINE cout << __LINE__ << endl;


const int MAX_LINE_LEN = 100;
const int MAX_NUM_TURTLES = 1000;

char orig_pos[ MAX_NUM_TURTLES ][ MAX_LINE_LEN ];
char targ_pos[ MAX_NUM_TURTLES ][ MAX_LINE_LEN ];
int ti[ MAX_NUM_TURTLES ]; //turtle index
char must_be_moved[ MAX_NUM_TURTLES ];
int n_turtles;
int n_cases;


void read_input();
void compute_result();
void shellsort( int n );
void move( int n );

int main() {
scanf( " %d ", &n_cases );
for( int case_num = 0; case_num < n_cases; case_num++ ) {
read_input();

if( case_num != 0 )
printf( "\n" );
compute_result();
}

return 0;
}

void read_input() {
scanf( " %d ", &n_turtles );
for( int i = 0; i < n_turtles; i++ )
fgets( orig_pos[ i ], MAX_LINE_LEN, stdin );
for( int i = 0; i < n_turtles; i++ )
fgets( targ_pos[ i ], MAX_LINE_LEN, stdin );

/*
//just to test that the input is read correctly
for( int i = 0; i < n_turtles; i++ )
printf( "%s", orig_pos[ i ] );
*/
}


void compute_result() {
for( int i = 0; i < n_turtles; i++ ) {
int j;
for( j = 0; strcmp( orig_pos, targ_pos[j] ) != 0; j++ )
;
ti[ i ] = j;
}

/*
//to test that ti is computed correctly
for( int i = 0; i < n_turtles; i++ )
printf( "%d\n", ti );
*/

while( true ) {
int max_ti, max_ni = INT_MIN;
for( int j = 1; j < n_turtles; j++ ) {
bool has_greater = false;
for( int k = 0; k < j; k++ ) {
if( ti[ k ] > ti[ j ] ) {
has_greater = true;
break;
}
}

if( has_greater && max_ni < ti[ j ] ) {
max_ti = j;
max_ni = ti[ j ];
}
}

if( max_ni == INT_MIN )
break;
move( max_ti );
printf( "%s", targ_pos[ max_ni ] );
}
}


void move( int n ) {
int temp = ti[ n ];
for( int i = n-1; i >= 0; i-- )
ti[ i+1 ] = ti[ i ];
ti[ 0 ] = temp;
}

[/cpp]
For God so loved the world, that he gave his only Son, that whoever believes in him should not perish but have eternal life.
(John 3:16)

User avatar
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by rakeb » Sat Apr 17, 2004 5:11 pm

u can solve in o(n) time :)
Rakeb

Chadwickiee
New poster
Posts: 1
Joined: Mon Jul 19, 2004 6:08 am
Location: TX
Contact:

to Map or Not to Map

Post by Chadwickiee » Mon Jul 19, 2004 6:32 am

I am wondering if it is neccessary to map the indices of one array to another in order to get the solution in O(n)?

My solution in Java ran in about 5.39 using a Hashtable O(n).
My solution in C++ ran in about .996 using nested loops to mapping.O(n^2)

I can not for the life of me get a hashCode() function to work with the judge. I have tried hashing a char* in C++, but it does not seem to work correctly when I turn it into the judge. Maybe I am not thinking deeply enough about how I to build a working HashTable. My initial thought involved a struct, but now I think that I should be able to hash a string into an int use that as an index to my table, and voila. I know collitions right, well I made my table bigger and it still does not work. Maybe the Function check it:

[cpp]
// return the hash code -- just take the module
// of the size of the table
//this requires the most thought
int hashCode(char *str)
{
unsigned int hash = 0;

/* Make sure a valid string passed in */
if (str==NULL) return -1;

/* Sum up all the characters in the string */
while (*str) hash = (hash << 1) + *str++;

/* Return the sum mod the table size */
return hash % MAX_NUM_TURTLES;
}
[/cpp]
Any help with problem 10152 either the algorithm with or without mapping or my HashTable mishaps would be greatly appreciated.
Suerte,
Chadwickiee

davidrobert
New poster
Posts: 1
Joined: Fri Sep 17, 2004 6:13 pm

O(n)

Post by davidrobert » Fri Sep 17, 2004 6:22 pm

#include <cstdio>
#include <cstring>

const int MAX_LEN = 100;
const int MAX_NUM = 1000;

char inicial[ MAX_NUM ][ MAX_LEN ];
char objetivo[ MAX_NUM ][ MAX_LEN ];
int num_tartarugas;

void read();
void computa();

int
main()
{
int num_casos;
scanf( " %d ", &num_casos );
for( int case_num = 0; case_num < num_casos; case_num++ )
{
read();

computa();
printf( "\n" );
}

return 0;
}

void
read()
{
scanf( " %d ", &num_tartarugas );
for( int i = 0; i < num_tartarugas; i++ )
fgets( inicial, MAX_LEN, stdin );
for( int i = 0; i < num_tartarugas; i++ )
fgets( objetivo, MAX_LEN, stdin );
}


void
computa()
{
int i, j, count = 0;
for( i = num_tartarugas - 1, j = num_tartarugas - 1; (i >= 0) and (j >= 0); --i )
{
if (strcmp( inicial, objetivo[j] ) != 0)
++count;
else
--j;
}

for (int i = count - 1; i >= 0; --i){
printf( "%s", objetivo );
/*printf( "%s\n", objetivo );*/
}
}[cpp][/cpp]

atthink
New poster
Posts: 1
Joined: Fri Apr 14, 2006 5:17 pm
Location: Taiwan

10152(Shellsort) - a runtime error...help

Post by atthink » Fri Apr 14, 2006 5:32 pm

I got a runtime error and messaged "Invalid memory reference" when I sumbitted my code. However, I could compile and run my program without any fault in Windows with Dev-C++ and VC++. I really hope somebody can help me check my codes.

To keep this page clean, I put my code on the website for any of you that could give me a hand to download. :)

http://www.atthink.info/10152.cpp

carliros
New poster
Posts: 6
Joined: Wed Aug 13, 2008 1:30 am

10152 - ShellSort

Post by carliros » Tue Sep 02, 2008 6:37 am

Do you have more test inputs y its outs ?

carliros
New poster
Posts: 6
Joined: Wed Aug 13, 2008 1:30 am

10152 - ShellSort

Post by carliros » Fri Sep 05, 2008 12:51 am

here is my code, where's wrong ?

Code: Select all

#include <stdio.h>
#include <string.h>
#define MAXNOM 50
#define MAXTOR 200

int getNextToMin(int tam);
void borrarValue(int val, int tam);
void generarArray(int tam);
int getIndex(char name[MAXNOM], int tam);
void procesar(int tam);
void readLine(char *cad);

char tortugas[MAXTOR][MAXNOM];
char tortugasT[MAXTOR][MAXNOM];
int lista[MAXTOR];

int main () {
	freopen("P10152.in", "rt", stdin);
	
	int nroTests, nroTor, i , j;
	
	scanf("%d", &nroTests);
	while (nroTests!= 0) {
		scanf("%d\n", &nroTor);
		for (i=nroTor-1; i >= 0; i--){
			readLine(&tortugasT[i][0]);
		}
		for (i=nroTor-1; i >= 0; i--){
			readLine(&tortugas[i][0]);
		}
		nroTests--;
		
		generarArray(nroTor);
		procesar(nroTor);
		printf("\n");
	}
	
	return 0;
}

void readLine(char *cadena){
     char c;
     int index = 0;
     
     while(( c = getchar() ) != '\n'){
         cadena[index++] = c;
     }
     
     cadena[index++] = '\0';
}

void generarArray(int tam){
	int i;
	for(i = 0; i < tam; i++){
		lista[i] = getIndex(tortugasT[i], tam);
	}
}

int getIndex(char name[MAXNOM], int tam){
	int i, res;
	for(i = 0; i < tam; i++){
		if(strcmp(name, tortugas[i]) == 0){
			res = i;
			break;
		}
	}
	return res;
}

void procesar(int tam){
	int val = getNextToMin(tam), index, i;
	index = tam;
	val++;
	while(val < tam){
		lista[index++] = val;
		borrarValue(val, tam);
		val++;
	}

	/*mostrar resultado*/
	for(i = tam; i < index; i++){
		if(lista[i] != (-1)){
			printf("%s\n", tortugas[lista[i]]);
		}
	}
}

void borrarValue(int val, int tam){
	int i;
	for(i = 0; i < tam; i++){
		if(lista[i] == val){
			lista[i] = (-1);
			break;
		}
	}
}

int getNextToMin(int tam){
	int res = 0, cnt = (-1), i=0, j, bandera;
	
	while(i < tam){
		bandera = 1;
		for(j = cnt+1; j < tam; j++){
			if(lista[j] == i){
				bandera = 0;
				res = i;
				cnt = j;
				i++;
				break;
			}
		}
		if(bandera) break;
	} 
	return res;
}

DonLimpio
New poster
Posts: 2
Joined: Wed Sep 10, 2008 1:40 am

Re: 10152 - ShellSort

Post by DonLimpio » Wed Sep 10, 2008 4:16 pm

Hello carlitos,

I don't go to reply you, sorry.

I have a problem with my code,
all tested inputs are right but this have a WA.
Again, have this problem any Critical Input?

Code: Select all

#include <cstdlib>
#include <iostream>

char aOrdenar[200][90];
char Ordenadas[200][90];
char entrada[100];
int tortugos;

int lee_linea( char *s )
{
   int ch, n=0;

   while( (ch=getchar()) != EOF && ch != '\n' ) {
      if ( ch != '\r' ) {
         *s++ = ch;
         n++;
      }
   }

   *s='\0';
   return n;
}

void tortugos_ninja(){
     int i=0;
     for(int j=0; j < tortugos; j++){
             if (strcmp(Ordenadas[i], aOrdenar[j])==0) i++;
     }
     if(i==tortugos) printf("\n");
     else{
          if (strcmp(Ordenadas[i], aOrdenar[tortugos-1])==0) i++;
     
          for (;i < tortugos; i++) printf("%s\n",Ordenadas[i]);
         
     }
}
             

int main(int argc, char *argv[])
{   
           int casos;
           lee_linea(entrada);
           casos=atoi(entrada);
           while( casos > 0){
                  tortugos=0;
                  lee_linea(entrada);
                  tortugos=atoi(entrada);
                 
                  for(int i=tortugos-1; i >= 0; i--){
                          lee_linea(aOrdenar[i]);
                  }

                  for(int i=tortugos-1; i >= 0; i--){
                          lee_linea(Ordenadas[i]);
                  }

                  tortugos_ninja();
                 
                  if(casos > 1) printf("\n");
                  casos--;
           }
}

panthenia
New poster
Posts: 5
Joined: Sun Jul 11, 2010 3:57 am

10152--PRE why??who can help me!!

Post by panthenia » Sat Aug 07, 2010 10:27 am

it's drive me crazy...

Code: Select all

#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<map>

using namespace std;

struct nd{
       nd():a(-1),b(0){}
       int a,b;
       };

int main()
    {
    int t;
    cin>>t;
    while(t--)
        {
        int dnum;
        string fuck;
        cin>>dnum;      
        getline(cin,fuck);
            
        map<string,int> mp;
        vector<nd> avec(210);
        vector<string>svec(210),vtm(210);
        
        for(int i=0;i<dnum;++i)
            getline(cin,vtm[i]);
        for(int i=0;i<dnum;++i)
           {
             getline(cin,svec[i]);
             mp[svec[i]]=i;     
           }
        for(int i=0;i<dnum;++i)
           {avec[i].a=mp[vtm[i]];
            //cout<<"av.a="<<avec[i].a<<endl;
           } 
         int max,mpos;
         for(int i=0;i<dnum;++i)
            if(avec[i].a == (dnum-1))
            {
            mpos=i-1;max=dnum-2;avec[i].b=1;break;} 
         for(int i=mpos;i>=0;--i)
            if(avec[i].a==max){avec[i].b=1;--max;}    
         max=-1;
         for(int i=0;i<dnum;++i)
           if(!avec[i].b&&avec[i].a>max)max=avec[i].a;
         for(int i=max;i>=0;--i)
           cout<<svec[i]<<endl;
         if(t)cout<<endl;   
        }           
     system("pause");     
    }

54tanghan
New poster
Posts: 1
Joined: Tue Mar 19, 2013 3:44 pm

Re: 10152 - ShellSort

Post by 54tanghan » Tue Mar 19, 2013 3:47 pm

Code: Select all

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


int main ()
{
    int testCase;
    cin >> testCase; // Input the number of test cases
    vector <string> output; // This vector stores the output


    while ( testCase-- ) {
        output.push_back (" ");

        int turtle;  // variable to hold the number of turtles (names/strings)
        cin >> turtle; // Input the number of turtles
        getchar(); // Read the next charactor to end the line (to get rid of reading the end of line character)


        string input;
        vector <string> initial; // This vector will be use to keep turtle names in the initial list
        vector <string> final; // This vector will be use to keep turtle names in the final list



        for ( int i = 0; i < turtle; i++ ) {
            getline(cin, input); // Read the i-th turtle name from the initial list
            initial.push_back (input); // Keep the turtle i-th name in the vector
        }

        for ( int i = 0; i < turtle; i++ ) {
            getline(cin, input); // Read the i-th turtle name from the final list
            final.push_back (input); // Keep the turtle i-th name in the vector
        }

        /**********************************
        * Main part: You have to implement your solution here
        * Your solution should be stored in the vector output.
        **********************************/

            int m = 0;
            int n = 0;
            int i = turtle - 1;

            while (m>=n&&i>0) {
                 int m = 0;
                 int n = 0;

                  while ( initial[m] != final[i]) {
                  m++;
                  }
                  while ( initial[n] != final[i-1]) {
                  n++;
                  }
                  if (m>=n)
                  i--;
                  else
                  break;
                  }
            if (i == 0)
            break;
            else {
                 for (int j = 0;j<=i-1;j++)
                 output.push_back (final[i-1-j]);
            }
    }

        /**********************************
         * End of main part
         **********************************/


        /**********************************
         *  Output
         **********************************/

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

	return 0;
}
Hey, my output is ok. i don`t know what`s wrong with my code. can you guys help me ?

Post Reply

Return to “Volume 101 (10100-10199)”