840 - Deadlock Detection

All about problems in Volume 8. 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
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

840 - Deadlock Detection

Post by little joey » Sun Apr 04, 2004 11:02 am

Haven't tried it yet, but in reading the problem description it occurs to me that the output is under-specified. Since this is a red flag problem, there's only one correct answer, but how are the following ambiguities resolved?

1. In which order is a cycle reported?
The cycle X-a-Y-b-X can be reported in 4 ways. Should we choose the alphabetically smalest? Is a-Y-b-X-a smaller than X-a-Y-b-X ?

2. In what order should cycles of the same length be reported? Alphabetically?

3. If a process/resource occurs in more than one cycle, what should we report? The longest? The shortest? All?

More speciffic; what is the output for the following input?

Code: Select all

3

2 2 4
Y-a a-X X-b b-Y

2 2 4
Y-a a-Y X-b b-X

2 2 5
Y-a a-X X-b b-X b-Y 

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Apr 04, 2004 12:59 pm

My output is:
YES
X-b-Y-a-X

YES
X-b-X
Y-a-Y

YES
X-b-Y-a-X

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Apr 04, 2004 1:37 pm

Thanks for your reply, Adrian.

Did some experimenting myself in the meantime, but kept getting WA. Your output made me see my mistake: I forgot to print "YES" in case there were cycles :oops: :oops: :oops:

Got accepted now. The answers to my questions are:

1. Alphabetically, with 'A' < 'a'.
2. No such case in the input file.
3. No such case in the input file. My AC program also prints the small cycle X-b-X in addition to Adrians output.

Weak problem description IMO, but with a few additions and better input file it could be made much more challenging.

subzero
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am

Re: 840 - Deadlock Detection

Post by subzero » Thu Oct 01, 2009 7:16 pm

hi guys

I'm trying this problem and I get wa...
does anyone could post some AC input - output?

thanks.

btw.what is the otuput for

Code: Select all

1

2 2 3
I-h
h-q
I-q
I think it's not a deadlock...
There is no knowledge that is no power.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 840 - Deadlock Detection

Post by Articuno » Fri Dec 25, 2009 8:04 am

I don't understand how this thing could be a deadlock
X-b-X
My AC code does not considered this as a deadlock but in the previous posts it is considered as a deadlock........ Here b is assigned to X and X needs b. How could it be a deadlock? :o
I think the input set is not good enough for this problem.
May be tomorrow is a better day............ :)

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 840 - Deadlock Detection

Post by Articuno » Fri Dec 25, 2009 8:13 am

I did a silly mistake in my code and for that reason my code failed in such a simple test case:

Code: Select all

1
2 2 4
Y-a a-X X-b b-Y
My code returns "NO".
But I got AC. Don't know why? :-?
May be tomorrow is a better day............ :)

Post Reply

Return to “Volume 8 (800-899)”