818 - Cutting Chains

[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]

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]

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

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

[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]

Thank you, Adrian. That was the problem.

[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]

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

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