## 10152 - ShellSort

Moderator: Board moderators

PJYelton
New poster
Posts: 20
Joined: Fri May 30, 2003 6:56 pm

### 10152 - ShellSort

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
New poster
Posts: 7
Joined: Wed Aug 06, 2003 4:51 am
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
New poster
Posts: 20
Joined: Fri May 30, 2003 6:56 pm
Thanks, yeah I figured that out a couple of days ago and finally got a AC on it.

dopey
New poster
Posts: 2
Joined: Sat Sep 13, 2003 11:22 pm
Location: BERGEN

### Not so obvious :|

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)

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

codeguru
New poster
Posts: 1
Joined: Sun Sep 28, 2003 11:37 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
New poster
Posts: 2
Joined: Sat Sep 13, 2003 11:22 pm
Location: BERGEN

### I finally managed to solve it myself

>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
New poster
Posts: 5
Joined: Tue Sep 30, 2003 6:46 am

### 10152 - Shell Sort Not working :(

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]
Thanks,
Nicholas A. Hay
nhay@mvnu.edu

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
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
New poster
Posts: 5
Joined: Tue Sep 30, 2003 6:46 am

### Sorry...

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++;
}
}
}
----------------
Thanks,
Nicholas A. Hay
nhay@mvnu.edu

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
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
New poster
Posts: 5
Joined: Tue Sep 30, 2003 6:46 am

### resolved!!!

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.
Thanks,
Nicholas A. Hay
nhay@mvnu.edu

cvarrichio
New poster
Posts: 2
Joined: Thu Oct 23, 2003 11:33 pm

### 10152 - Shellsort

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.

Craig

cvarrichio
New poster
Posts: 2
Joined: Thu Oct 23, 2003 11:33 pm

### Clarification

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
New poster
Posts: 2
Joined: Thu Oct 10, 2002 10:04 pm
Contact:

### shellsort not working

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