All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
-
Martin Macko
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Post
by Martin Macko » Sun Aug 06, 2006 12:52 am
Well... the beverages relation is transitive, but is it asymmetric? If it is not, what is the correct answer for the following?
-
mf
- Guru
- Posts: 1244
- Joined: Mon Feb 28, 2005 4:51 am
- Location: Zürich, Switzerland
-
Contact:
Post
by mf » Sun Aug 06, 2006 12:58 am
Well, the problem states that a relation A B means that the amount of alcohol in drink A (which must be a non-negative real number, I guess) is less than the amount of alcohol in B.
Comparison of reals is asymmetric.
Last edited by
mf on Sun Aug 06, 2006 12:59 am, edited 1 time in total.
-
Mg9H
- New poster
- Posts: 18
- Joined: Sun Oct 14, 2001 2:00 am
- Location: Ohio University
-
Contact:
Post
by Mg9H » Sun Aug 06, 2006 12:59 am
Martin Macko wrote:Well... the beverages relation is transitive, but is it asymmetric? If it is not, what is the correct answer for the following?
I believe the input will not form any "circles" because of the background information about alcohol content of the beverages.
-
Darko
- Guru
- Posts: 580
- Joined: Fri Nov 11, 2005 9:34 am
- Location: Calgary, Canada
Post
by Darko » Sun Aug 06, 2006 1:03 am
I assumed there were no cycles - because they didn't say what to do in the case of one.
I am still not sure what I did wrong with my solution, it was supposed to be a simple topological sort, right?
What is output for this:
-
mf
- Guru
- Posts: 1244
- Joined: Mon Feb 28, 2005 4:51 am
- Location: Zürich, Switzerland
-
Contact:
Post
by mf » Sun Aug 06, 2006 1:05 am
I get:
Code: Select all
Case #1: Dilbert should drink beverages in this order: b c a.
-
Mg9H
- New poster
- Posts: 18
- Joined: Sun Oct 14, 2001 2:00 am
- Location: Ohio University
-
Contact:
Post
by Mg9H » Sun Aug 06, 2006 1:10 am
Darko wrote:I assumed there were no cycles - because they didn't say what to do in the case of one.
I am still not sure what I did wrong with my solution, it was supposed to be a simple topological sort, right?
What is output for this:
Yes, it's just a simple topological sort, but be careful when you count the degree of each node. I believe there will be the case when some of the edges are listed more than once in the input.
And I got "b c a" for your input.
-
Darko
- Guru
- Posts: 580
- Joined: Fri Nov 11, 2005 9:34 am
- Location: Calgary, Canada
Post
by Darko » Sun Aug 06, 2006 1:12 am
Ah, thanks, that explains a lot

-
helloneo
- Guru
- Posts: 516
- Joined: Mon Jul 04, 2005 6:30 am
- Location: Seoul, Korea
Post
by helloneo » Sun Aug 06, 2006 6:23 am
hello..~
I did a simple topological sort .. but getting WA..
can anybody give me some test cases..?
thanks..
Last edited by
helloneo on Sun Aug 06, 2006 8:12 am, edited 2 times in total.
-
Martin Macko
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Post
by Martin Macko » Sun Aug 06, 2006 7:33 am
helloneo wrote:hello..~
I did a simple topological sort .. but getting WA..
can anybody give me some test cases..?
thanks..
Try this one:
Correct output:
Code: Select all
Case #1: Dilbert should drink beverages in this order: E B C D A.
-
helloneo
- Guru
- Posts: 516
- Joined: Mon Jul 04, 2005 6:30 am
- Location: Seoul, Korea
Post
by helloneo » Sun Aug 06, 2006 8:12 am
Martin Macko wrote:
Try this one:
Correct output:
Code: Select all
Case #1: Dilbert should drink beverages in this order: E B C D A.
Good point..~
Thanks a lot ..

Last edited by
helloneo on Sat Dec 16, 2006 8:45 am, edited 1 time in total.
-
Wei-Ming Chen
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
Post
by Wei-Ming Chen » Sun Aug 06, 2006 4:53 pm
The sample inputs are
Code: Select all
3
vodka
wine
beer
2
wine vodka
beer wine
5
wine
beer
rum
apple-juice
cachaca
6
beer cachaca
apple-juice beer
apple-juice rum
beer rum
beer wine
wine cachaca
10
cachaca
rum
apple-juice
tequila
whiskey
wine
vodka
beer
martini
gin
11
beer whiskey
apple-juice gin
rum cachaca
vodka tequila
apple-juice martini
rum gin
wine whiskey
apple-juice beer
beer rum
wine vodka
beer tequila
and sample outputs are
Code: Select all
Case #1: Dilbert should drink beverages in this order: beer wine vodka.
Case #2: Dilbert should drink beverages in this order: apple-juice beer wine rum cachaca.
Case #3: Dilbert should drink beverages in this order: apple-juice wine vodka beer rum cachaca tequila whiskey martini gin
but my outputs are
Code: Select all
Case #1: Dilbert should drink beverages in this order: beer wine vodka.
Case #2: Dilbert should drink beverages in this order: apple-juice beer wine cachaca rum.
Case #3: Dilbert should drink beverages in this order: apple-juice beer rum cachaca gin martini wine whiskey vodka tequila.
I think my outputs are legal,but it got WA.
Can someone tell me my outputs are legal or not?
-
arsalan_mousavian
- Experienced poster
- Posts: 111
- Joined: Mon Jan 09, 2006 6:19 pm
- Location: Tehran, Iran
-
Contact:
Post
by arsalan_mousavian » Sun Aug 06, 2006 7:29 pm
maybe you sort the drinks by name , because the drinks on each level in sample is given by the order of input , but you output them in sorted order for example if B and A are in the same level and B is given before A in the input you should print B , A not A , B
In being unlucky I have the record.
-
mf
- Guru
- Posts: 1244
- Joined: Mon Feb 28, 2005 4:51 am
- Location: Zürich, Switzerland
-
Contact:
Post
by mf » Sun Aug 06, 2006 8:02 pm
Wei-Ming Chen wrote:Can someone tell me my outputs are legal or not?
No, they are not:
In the case there is no relation between two beverages Dilbert should start drinking the one that appears first in the input.
For example, in the 2nd sample case, there's no relation between
rum and
cachaca, but since
rum appears earlier in the input, it should be drank before
cachaca.
-
mute
- New poster
- Posts: 8
- Joined: Thu Apr 13, 2006 2:16 am
- Location: Dhaka
-
Contact:
Post
by mute » Sun Aug 06, 2006 11:26 pm
Wei-Ming Chen wrote:
I think my outputs are legal,but it got WA.
Can someone tell me my outputs are legal or not?
Hi, your output is wrong.. but Topologically they are correct
here you have to print on priority basis..
I think you will get accepted if you use a priority queue instead of Queue
Thanks
-
sluga
- New poster
- Posts: 20
- Joined: Sun Jan 22, 2006 10:48 pm
- Location: Croatia
Post
by sluga » Mon Aug 07, 2006 12:55 am
I had the same output when i did topological sort.
This is the key sentence:
In the case there is no relation between two beverages Dilbert should start drinking the one that appears first in the input.
It means that because juice is the first drink in the input that isn't preceeded by some other drink that has less alchohol, it comes first. Then, wine becomes the first drink in the input with the following property...
A sta da radim