11060 - Beverages

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

Post Reply
User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

11060 - Beverages

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?

Code: Select all

5
a
b
c
d
e
5
a b
b c
c d
d b
c e

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.

User avatar
Mg9H
New poster
Posts: 18
Joined: Sun Oct 14, 2001 2:00 am
Location: Ohio University
Contact:

Re: 11060: Beverages

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?

Code: Select all

5
a
b
c
d
e
5
a b
b c
c d
d b
c e
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:

Code: Select all

3
a
b
c
1
c a

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.

User avatar
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:

Code: Select all

3
a
b
c
1
c a
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.. :D

Code: Select all

CUT AFTER AC
Last edited by helloneo on Sun Aug 06, 2006 8:12 am, edited 2 times in total.

User avatar
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.. :D
Try this one:

Code: Select all

5
A
B
C
D
E
5
C A
D A
B D
E B
E C

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:

Code: Select all

5
A
B
C
D
E
5
C A
D A
B D
E B
E C

Correct output:

Code: Select all

Case #1: Dilbert should drink beverages in this order: E B C D A.

Good point..~
Thanks a lot .. :D
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?

User avatar
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.

User avatar
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 :evil:
here you have to print on priority basis..

I think you will get accepted if you use a priority queue instead of Queue
Thanks
Check this out ThirdEye Creative.com
Image

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

Post Reply

Return to “Volume 110 (11000-11099)”