10152 - ShellSort

[seedosrun]

I don't think that their are any special cases... What does your alogrithm look like?

[yo_sole]

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]

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.

[OutCaster]

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]

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!

[zacharyleung]

I've gotten an AC for this question. 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]

[rakeb]

u can solve in o(n) time

[Chadwickiee]

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.

[davidrobert]

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

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]

Do you have more test inputs y its outs ?

[carliros]

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]

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]

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]

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 ?