10152 - ShellSort

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10152 - ShellSort

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
New poster
Posts: 7
Joined: Wed Aug 06, 2003 4:51 am

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. :P

Good luck.

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

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

Not so obvious :|

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. :P
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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

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

Just got ACC.

Hint: NO sorting is required :P

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... :wink:
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

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

This problem is pissing me off.. :x

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

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

10152 - Shell Sort Not working :(

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

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

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

Sorry...

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

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

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

resolved!!!

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

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

10152 - Shellsort

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
New poster
Posts: 2
Joined: Thu Oct 23, 2003 11:33 pm

Clarification

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

shellsort not working

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

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

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest