11060 - Beverages

Moderator: Board moderators

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

11060 - Beverages

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

Re: 11060: Beverages

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
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:
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:
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
Ah, thanks, that explains a lot

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
hello..~
I did a simple topological sort .. but getting WA..
can anybody give me some test cases..?
thanks..

Code: Select all

``````CUT AFTER AC
``````
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)
helloneo wrote:hello..~
I did a simple topological sort .. but getting WA..
can anybody give me some test cases..?
thanks..
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
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 ..
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
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:
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:
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:
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
Check this out ThirdEye Creative.com

sluga
New poster
Posts: 20
Joined: Sun Jan 22, 2006 10:48 pm
Location: Croatia
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...