OJ Board

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

Posted: **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.

Posted: **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.

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

Posted: **Sun Aug 06, 2006 1:05 am**

I get:

Code: Select all

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

Posted: **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.

Posted: **Sun Aug 06, 2006 1:12 am**

Ah, thanks, that explains a lot

Posted: **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..

Code: Select all

CUT AFTER AC

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

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.

Posted: **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 ..

Posted: **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?

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

Posted: **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.

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

Posted: **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...

OJ Board

11060 - Beverages

11060 - Beverages

Re: 11060: Beverages