956 - The Minimum Slot Machine

All about problems in Volume 9. 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
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

956 - The Minimum Slot Machine

Post by Jan » Fri Nov 24, 2006 12:53 am

I m currently getting WA, but cant find any reason. Can anyone please verify the I/O set?

Input:

Code: Select all

3
A C B w
B A B -
C C B -
4
A C B w
B A B -
C C D w
D A B w
4
A C B w
B A B -
C C D w
D C B -
4
A C B w
B A B -
C C D w
D A B -
Output:

Code: Select all

A B C
A B C D
A B C D
A B
Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Nov 24, 2006 1:00 am

My AC code outputs

Code: Select all

A B C
A B C D
A B
A B
I hope this helps.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Nov 24, 2006 1:08 am

The problem states
Two states are equivalent if no matter the sequence of coins you insert, the result is the same starting from one state or from the other.
Input:

Code: Select all

4 
A C B w 
B A B - 
C C D w 
D C B -
A and C are not equal. If you insert 1 coin you will get state C, but if you insert 2 coins you will get A -> B, and C -> D.
B and D are not equal. If you insert 2 coins you will get B, but if you insert 1 coin you will get B -> A, and D -> C.
And so, why are they equal?
Ami ekhono shopno dekhi...
HomePage

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Nov 24, 2006 1:29 am

You are little misunderstanding the statement.
Two states are equivalent if no matter the sequence of coins you insert, the result is the same starting from one state or from the other.
"the result is the same" doesn't mean the same alphabet.

---
Sory for my poor English. I can't explain well.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Nov 25, 2006 12:10 am

Thanks, got it accepted.
Ami ekhono shopno dekhi...
HomePage

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sat Feb 17, 2007 10:33 am

Isn't this problem just an application of union find?

Post Reply

Return to “Volume 9 (900-999)”