10152 - ShellSort
Moderator: Board moderators
I don't think so...
I don't think that their are any special cases... What does your alogrithm look like?
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]= '\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
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
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.
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;
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?
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?
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!
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
-Albert Einstein
-
- 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 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]
[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)
(John 3:16)
-
- New poster
- Posts: 1
- Joined: Mon Jul 19, 2004 6:08 am
- Location: TX
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.
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
Chadwickiee
-
- 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 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]
#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]
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
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
10152 - ShellSort
Do you have more test inputs y its outs ?
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);
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;
}
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?
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--;
}
}
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");
}
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;
}