OJ Board

Posted: **Tue Sep 21, 2004 3:55 pm**

Having trouble getting this one Accepted. Can someone verify this I/O? It's a little too much to hand-check them 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.

Posted: **Tue Sep 21, 2004 5:09 pm**

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.

Posted: **Tue Sep 21, 2004 5:37 pm**

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

Posted: **Tue May 03, 2005 3:36 am**

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.

Posted: **Thu May 19, 2005 1:23 pm**

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.

Posted: **Fri May 20, 2005 3:52 am**

Thank you, Adrian. That was the problem.

Posted: **Wed Feb 27, 2013 8:45 am**

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

Posted: **Wed Feb 27, 2013 11:55 pm**

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

Posted: **Thu Feb 28, 2013 12:28 am**

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.

OJ Board

818 - Cutting Chains

818 - Cutting Chains

Re: 818 - Cutting chains

Re: 818 - Cutting chains

Re: 818 - Cutting chains