## 10152 - ShellSort

Moderator: Board moderators

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

### I don't think so...

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

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';
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...

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

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;
cases = Integer.parseInt(input);
String[] Sorted;
String[] Unsorted;
for(int count = 0 ; count < cases; count++){

total = Integer.parseInt(input);

if(total >= 1)
{

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

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

for(int sCount = 0 ; sCount < total ; ++sCount)
{
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:
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
<space>
input num of elements
input elements of unsorted elements
input elements of sorted elements
<space>
input num of elements
input elements of unsorted elements
input elements of sorted elements
<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?

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 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++ ) {

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

return 0;
}

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)

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France
u can solve in o(n) time Rakeb

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

### to Map or Not to Map

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,

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

### O(n)

#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 computa();

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

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

return 0;
}

void
{
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

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

Do you have more test inputs y its outs ?

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

### 10152 - ShellSort

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);

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--){
}
for (i=nroTor-1; i >= 0; i--){
}
nroTests--;

generarArray(nroTor);
procesar(nroTor);
printf("\n");
}

return 0;
}

char c;
int index = 0;

while(( c = getchar() ) != '\n'){
}

}

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

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

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;
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(i==tortugos) printf("\n");
else{

for (;i < tortugos; i++) printf("%s\n",Ordenadas[i]);

}
}

int main(int argc, char *argv[])
{
int casos;
while( casos > 0){
tortugos=0;

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

for(int i=tortugos-1; i >= 0; 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!!

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

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 ?