11060 - Beverages

[Martin Macko]

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]

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.

[Mg9H]

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]

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]

I get:

Code: Select all

Case #1: Dilbert should drink beverages in this order: b c a.

[Mg9H]

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]

Ah, thanks, that explains a lot

[helloneo]

hello..~
I did a simple topological sort .. but getting WA..
can anybody give me some test cases..?
thanks..

Code: Select all

CUT AFTER AC

[Martin Macko]

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]

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

[Wei-Ming Chen]

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]

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

[mf]

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]

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]

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