10152 - ShellSort

PJYelton · Post by **PJYelton** » Fri Aug 01, 2003 8:45 pm

I am truly stumped on this one

Any hints as to a simple way that this one can be done? Obviously trying every possibility isn't the answer...

farsight · Post by **farsight** » Sat Aug 09, 2003 7:47 pm

hmm... I hope this isn't giving it away...

Look at how many turtles are properly in their increasing (not necessary consecutive) order. Then the solution should be obvious.

Good luck.

PJYelton · Post by **PJYelton** » Sat Aug 09, 2003 7:59 pm

Thanks, yeah I figured that out a couple of days ago and finally got a AC on it.

dopey · Post by **dopey** » Sat Sep 13, 2003 11:28 pm

farsight wrote:hmm... I hope this isn't giving it away...
Look at how many turtles are properly in their increasing (not necessary consecutive) order. Then the solution should be obvious.

I also thought it was obvious, but I am unable to formulate an algorithm for the set

7
Yertle
Oscar
Baron
Lord
King
White
Kong
Oscar
Baron
Lord
Yertle
King
Kong
White

Which should result in

Kong
King
Yertle
Lord
Baron
Oscar

Any hints? I have tried looking at increasing order and consecutive order, but I am unable to stop the algorithm from sorting 'white' (it should't)

Appreciate an answer

Observer · Post by **Observer** » Tue Sep 16, 2003 6:20 am

Just got ACC.

Hint: NO sorting is required

dopey: what do you mean by "unable to stop the algorithm from sorting 'white'"? Could you explain it a bit, plz? We really want to help...

codeguru · Post by **codeguru** » Sun Sep 28, 2003 11:45 pm

This problem is pissing me off..

here are my questions:

1) Why is there "No Sorting"? Of course there should be: if a turtle is not in increasing order, throw it to the top.. do that until you have transformed it to the required stack.

2) What if there is only one turtle in the stack? what are you supposed to print?

3) What if the given stack is already sorted just like the required stack?

If somebody thinks that I am way off in my algorithm, please let me know..

THanks

dopey · Post by **dopey** » Mon Sep 29, 2003 1:33 am

>1) Why is there "No Sorting"? Of course there should be: if a turtle >is not in increasing order, throw it to the top.. do that until you >have transformed it to the required stack.
You actually do not have to do any manipulation of any sort

>2) What if there is only one turtle in the stack? what are you >supposed to print?
If only one, both stacks are alike, and noone moves...

>3) What if the given stack is already sorted just like the required >stack?
Then noone moves and nothing is printed out

>If somebody thinks that I am way off in my algorithm, please let me >know..
You haven't figured it out just yet :|

HINT: Count the number of shells that are misplaced
HINT2: Know that no sort of ANY kind need to be done. No manipulation
what so ever. Just counting!

seedosrun · Post by **seedosrun** » Tue Sep 30, 2003 6:51 am

Hello, I am having some problems with this problem. It seems to be working but i keep on getting wrong answer... I have an input file which i will include below and an output file and if anyone could give me a hint to this problem or any other possible cases which i haven't thought of, i would love you... lol

in.txt
--------------------------------------------------
4
3
Yertle
Duke of Earl
Sir Lancelot
Duke of Earl
Yertle
Sir Lancelot
9
Yertle
Duke of Earl
Sir Lancelot
Elizabeth Windsor
Michael Eisner
Richard M. Nixon
Mr. Rogers
Ford Perfect
Mack
Yertle
Richard M. Nixon
Sir Lancelot
Duke of Earl
Elizabeth Windsor
Michael Eisner
Mr. Rogers
Ford Perfect
Mack
7
Yertle
Oscar
Baron
Lord
King
White
Kong
Oscar
Baron
Lord
Yertle
King
Kong
White
3
Yertle
Duke of Earl
Sir Lancelot
Yertle
Duke of Earl
Sir Lancelot
--------------------------------------------------

out.txt
--------------------------------------------------
Duke of Earl

Sir Lancelot
Richard M. Nixon
Yertle

Kong
King
Yertle
Lord
Baron
Oscar

--------------------------------------------------
[/cpp]

junjieliang · Post by **junjieliang** » Tue Sep 30, 2003 3:03 pm

Your output is correct, but if you don't tell us your algorithm... it's rather hard to help you. IMO this problem doesn't have tricky inputs.

seedosrun · Post by **seedosrun** » Tue Sep 30, 2003 4:32 pm

Sorry, I pretty much saw this pattern... I have 2 arrays Sorted and unsorted. Pretty much i will make a variable called c, which the first time the value is set for each case is equal to n-1 (the amount of elements in array). I have a loop that goes from the bottom to the top of unsorted. I compare it with the value of sorted[c], to see if it is equal and if it is equal, than i know i don't need to move that element so i just simply erase that entry on the unsorted list and i subtract 1 from the c value to move to the next value. After i get though this loop, I then know what elements need to be moved so i go though and output the ones that need to be moved by how they appear in the sorted list (last to first).

Here is my chunk of code that i have doing this part of my program.

Code
----------------
// find the order
celement = n-1;
for (y=n-1; y>=0; y--) {
if (strcmp(nonsort[y], sorted[celement]) == 0) {
nonsort[y][0] = '\0';
celement--;
}
}
c=0;
for (y=n-1; y>=0; y--) {
for (z=0; z<n; z++) {
if (strcmp(nonsort[z], sorted[y]) == 0) {
cout << nonsort[z] << endl;
c++;
}
}
}
----------------

junjieliang · Post by **junjieliang** » Wed Oct 01, 2003 3:42 pm

Hi...
Send me your code via PM. I added a few lines of input to your chunk and it got AC. Also you may want to edit your previous post to erase the code.

seedosrun · Post by **seedosrun** » Sat Oct 04, 2003 6:38 am

Hey, for anyone else that may be having problems, the resolution to my problem was that their compiler were having problems with using cin.getline. After switching all my getlines to gets(), it worked great.

cvarrichio · Post by **cvarrichio** » Thu Oct 23, 2003 11:41 pm

I too am having troubles getting this problem accepted. My program seems to work for any input I can concieve of. It prints a blank line only between test cases, though I have also tried making it print a blank line at the end of any test case even if it is not followed by another case. I am using java (required in order to get credit for my class), and have used only System.in.read() to obtain data, as I am under the impression any more advanced methods cause the judge to freak out. Any theories on little things that might be bothering the judge, or some really bizarre test case that I might not have considered? My algorithm is admittedly inefficient, but that really shouldn't cause a problem. I can provide more information or code if that would help. Thanks in advance for any help.

Slowly going mad,
Craig

cvarrichio · Post by **cvarrichio** » Thu Oct 23, 2003 11:54 pm

Just to clarify a little about the output format I am currently trying:
If the list is already sorted, it will print a single blank line.
It also prints a blank line after the end of the last test case (although I have tried it without this)
There is, of course, a blank line separating each test case.
There is no blank line before the first test case.

[/java]

yo_sole · Post by **yo_sole** » Sat Oct 25, 2003 3:32 am

Hi, I'm having troubles with this one, I

UVa OJ Board

10152 - ShellSort

10152 - ShellSort

Not so obvious :|

I finally managed to solve it myself

10152 - Shell Sort Not working :(

Sorry...

resolved!!!

10152 - Shellsort

Clarification

shellsort not working