818 - Cutting Chains

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
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

818 - Cutting Chains

Post by little joey »

Having trouble getting this one Accepted. Can someone verify this I/O? It's a little too much to hand-check them all...

Code: Select all

14 1 3 1 4 1 5 1 6 1 9 1 10 1 12 1 14 2 3 2 9 2 11 2 12 3 5 3 6 3 7 3 8 3 12 3 13 3 14 4 6 4 8 4 9 4 10 4 11 4 13 5 7 5 9 5 11 5 14 6 10 6 11 6 12 6 14 7 9 7 11 7 12 7 13 8 9 8 11 8 13 9 11 9 13 11 12 11 13 12 13 -1 -1
12 1 3 1 8 1 9 2 3 2 4 2 5 2 7 2 11 3 5 3 6 3 7 3 9 3 11 3 12 4 5 4 6 4 7 4 8 4 9 4 10 4 11 4 12 5 7 5 8 5 10 5 12 6 7 6 10 6 12 7 8 7 9 8 9 8 11 9 10 9 12 10 12 11 12 -1 -1
6 1 2 1 6 2 4 4 5 5 6 -1 -1
7 1 2 1 3 1 4 1 7 2 3 2 5 2 6 3 4 3 6 3 7 4 5 4 6 4 7 6 7 -1 -1
7 1 3 1 6 1 7 2 3 3 7 4 5 4 6 5 7 -1 -1
9 1 3 1 5 1 8 1 9 2 5 2 9 3 4 3 5 3 8 4 6 4 7 5 8 6 7 6 8 6 9 8 9 -1 -1
1 -1 -1
12 1 5 1 11 2 7 2 8 2 11 2 12 3 4 3 5 3 7 3 10 3 11 3 12 4 5 4 7 4 8 4 9 4 12 6 9 6 10 6 12 7 9 8 9 8 10 9 11 10 11 10 12 -1 -1
2 1 2 -1 -1
15 1 2 1 3 1 5 1 6 1 8 1 9 1 11 2 5 2 7 2 14 2 15 3 5 3 9 3 14 3 15 4 5 4 8 4 11 4 12 4 13 5 6 5 9 5 11 5 12 5 13 5 14 6 7 6 8 6 11 7 9 7 13 8 13 8 15 9 10 9 11 9 15 10 13 11 13 11 14 12 13 12 14 12 15 13 14 13 15 -1 -1
7 1 2 1 5 1 7 2 3 2 7 3 7 6 7 -1 -1
5 1 2 1 3 2 3 2 5 3 4 4 5 -1 -1
12 1 2 1 4 1 6 1 7 1 9 1 10 1 12 2 3 2 4 2 5 2 6 2 9 2 10 2 11 2 12 3 6 3 7 3 9 4 5 4 6 4 9 4 12 5 6 5 7 5 8 5 9 5 11 6 7 6 8 7 8 7 11 11 12 -1 -1
7 1 3 1 5 1 7 2 3 2 4 2 5 3 5 4 6 5 6 5 7 -1 -1
6 1 2 1 4 1 5 3 5 4 6 5 6 -1 -1
5 1 2 1 4 1 5 2 3 2 5 3 4 3 5 4 5 -1 -1
8 1 3 1 5 1 6 1 8 2 5 2 8 3 4 3 5 3 6 4 5 4 6 4 7 4 8 5 6 6 7 6 8 7 8 -1 -1
8 1 5 1 6 1 7 1 8 2 3 2 5 2 6 2 7 2 8 3 4 3 5 4 6 4 7 5 8 6 7 -1 -1
9 1 4 1 8 1 9 2 3 2 7 2 8 2 9 3 4 3 6 3 7 3 8 4 8 4 9 5 6 5 8 5 9 6 8 6 9 7 8 8 9 -1 -1
14 1 2 1 4 1 8 1 10 1 13 2 3 2 4 2 7 2 8 2 9 2 11 2 13 3 6 3 8 3 9 3 10 3 11 3 12 3 13 4 5 4 6 4 9 4 11 4 12 5 8 5 9 5 10 5 11 5 12 5 13 6 7 6 8 6 11 6 12 6 14 7 8 7 9 7 11 7 13 7 14 8 10 8 11 8 14 9 12 10 12 10 13 11 14 13 14 -1 -1
3 2 3 -1 -1
15 1 2 1 4 1 7 1 11 2 3 2 6 2 7 2 9 2 14 2 15 3 4 3 5 3 6 3 7 3 9 3 11 3 12 3 13 3 14 3 15 4 5 4 8 4 14 5 7 5 9 5 10 5 11 6 7 6 8 6 11 6 12 6 13 7 8 7 10 7 11 7 12 7 13 7 14 8 10 8 11 8 13 9 11 9 12 9 13 9 15 10 11 10 12 10 14 11 12 11 13 11 14 12 13 13 15 14 15 -1 -1
8 1 3 1 5 1 6 1 8 2 3 2 5 2 6 3 4 3 5 3 6 4 5 4 7 5 7 5 8 6 8 -1 -1
0
My output:

Code: Select all

Set 1: Minimum links to open is 7
Set 2: Minimum links to open is 6
Set 3: Minimum links to open is 1
Set 4: Minimum links to open is 3
Set 5: Minimum links to open is 2
Set 6: Minimum links to open is 3
Set 7: Minimum links to open is 0
Set 8: Minimum links to open is 5
Set 9: Minimum links to open is 0
Set 10: Minimum links to open is 7
Set 11: Minimum links to open is 2
Set 12: Minimum links to open is 1
Set 13: Minimum links to open is 5
Set 14: Minimum links to open is 1
Set 15: Minimum links to open is 1
Set 16: Minimum links to open is 2
Set 17: Minimum links to open is 3
Set 18: Minimum links to open is 3
Set 19: Minimum links to open is 3
Set 20: Minimum links to open is 8
Set 21: Minimum links to open is 1
Set 22: Minimum links to open is 8
Set 23: Minimum links to open is 3
Are there any special cases to consider?

Thanx in advance.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

Two errors:

Code: Select all

1c1
< Set 1: Minimum links to open is 6
---
> Set 1: Minimum links to open is 7
5c5
< Set 5: Minimum links to open is 1
---
> Set 5: Minimum links to open is 2
Take set 5 for instance, where it suffices to open chain 1.

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

Post by little joey »

Thanx man!
I always make the same mistakes when typing in certain algorithms :oops:
Finding subsets in a set is one of them... stupid, stupid me :(

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego »

Does the chain have to be open, or is a loop allowed as the final answer?

Is there anything wrong with this algorithm?
1. for each subset S of the links, remove these links.
1a. Run UNION/FIND on the remaining links. If there is a loop - break.
1b. If any link is connected to more than 2 links - break.
1c. Compute the number of connected components that we found.
1d. If we have enough links in S to connect these components, remember the size of S.
2. The answer is the size of the smallest set S that had enough links to connect the remaining components.

Here is my code. It passes joey's random input, but gets WA.

Code: Select all

Works now. Change the 3 to a 2 in sample case 5. The answer should be 0.
Last edited by Abednego on Fri May 20, 2005 3:53 am, edited 1 time in total.
If only I had as much free time as I did in college...

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

Post by Adrian Kuegel »

I think you can't handle some inputs where "edges" are given more than once. This is valid input, as sample test case 5 shows.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego »

Thank you, Adrian. That was the problem.
If only I had as much free time as I did in college...

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Re: 818 - Cutting chains

Post by howardcheng »

My code passes the posted I/O but got WA. With asserts I confirmed that some pairs are included in the input multiple times. My algorithm is essentially the same as the one posted above.

What exactly are we supposed to do if we see an edge twice? Sample case 5 seems clear, but what if the same pair (in the same order) is given twice? Is that counted as one or two edges? I have tried both interpretations and both got WA...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 818 - Cutting chains

Post by brianfry713 »

Edges are bidirectional so the order the pairs are listed in doesn't matter. Use something like an adjacency matrix and only count repeated edges once.

For input:

Code: Select all

2 1 2 1 2 -1 -1
2 1 2 2 1 1 2 2 1 -1 -1
3 1 2 -1 -1
0
AC output:

Code: Select all

Set 1: Minimum links to open is 0
Set 2: Minimum links to open is 0
Set 3: Minimum links to open is 1
Check input and AC output for thousands of problems on uDebug!

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Re: 818 - Cutting chains

Post by howardcheng »

Thanks, I have solved it now. I thought that 1 2 and 2 1 both appearing means that somehow they are formed into a loop.

Post Reply

Return to “Volume 8 (800-899)”