840 - Deadlock Detection

[little joey]

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]

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

YES
X-b-X
Y-a-Y

YES
X-b-Y-a-X

[little joey]

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

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]

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

[Articuno]

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?
I think the input set is not good enough for this problem.

[Articuno]

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?