10972 - RevolC FaeLoN

All about problems in Volume 109. 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
Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

10972 - RevolC FaeLoN

Post by Wei-Ming Chen » Sun Nov 13, 2005 10:54 am

Why the output are 1 & 2 ?
I thought they were 0 & 1 ....

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

Post by Adrian Kuegel » Sun Nov 13, 2005 12:22 pm

For first input, you need to add an edge between 1 and 3
(the edge orientations can then be 1-> 2, 2->3, 3-> 1 or 1->3, 3->2, 2->1)

For second input, one solution would be to add an edge between 10 and 7 and between 10 and 6 (you cannot use less edges, since 10 has no connection at all before, so it needs an ingoing and an outgoing edge).

artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm

Post by artem » Fri Nov 18, 2005 11:22 pm

Who may check this input

Code: Select all

3 3
1 2
2 3
3 1
10 11
1 2
2 3
3 1
3 7
4 5
5 6
6 4
7 9
6 3
9 8
7 8
3 2
1 2
2 3
3 0
6 4
1 2
1 3
1 4
5 6
1 0
0 0
7 6
1 2
1 3
2 4
2 5
3 6
3 7
20 20
1 3
3 5
5 7
7 9
9 11
11 13
13 15
15 17
17 19
19 20
20 2
2 4
4 6
6 8
8 10
10 12
12 14
14 16
16 18
18 1
10 12
1 2
2 3
3 4
4 2
1 5
5 6
6 7
7 5
1 8
8 9
9 10
10 8
10 8
1 3 
3 5
5 7
7 9
2 4
4 6
6 8
8 10
5 6
1 2
1 3
2 4
3 5
4 1
5 1
20 1
7 11
1000 1
1000 999
14 16
1 2
2 3
2 4
3 4
4 5
4 6
5 6
6 7
7 8
7 9
8 9
10 11
10 12
11 14
12 13
13 14
my output is

Code: Select all

0
2
1
3
3
0
0
3
0
2
2
0
19
999
2
Is it right?

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Sun Nov 20, 2005 4:57 pm

My accpeted solution gives me these anserws:

Code: Select all

0
2
1
3
3
0
0
2
0
2
2
0
19
999
2

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Mon Nov 21, 2005 2:48 pm

I don't know how to solve ths problem. :(
Just found a stubid greedy method
could someone who got ac explain it? :oops:

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Tue Nov 22, 2005 3:01 pm

It's about biconnected component. Revising textbook may help.
CLR Ch.23, p.495, problem 23-2.

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Cut-Edge

Post by Moha » Tue Nov 22, 2005 4:24 pm

Yes, I use same algorithm. I tried to find cut-edge in graph.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

tests

Post by Monsoon » Thu Aug 31, 2006 12:10 am

Could anyone post some tricky tests cases? Thanks in advance :wink:

[Edit]
I have one (probably silly) question, suppose we have a graph G, we create a graph G', where nodes are connected componets from G, and egdes are bridges from G. G' is a forrest. Now i think that answer i seek is ceil(number_of_leaves_in_G' / 2). Where single node i count as 2 leaves. I can't find counter example to this, but i can't also prove it. Could anyone show me counter example (using this idea i got wa so i consider it to be wrong)?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Re: tests

Post by sclo » Fri Sep 01, 2006 3:42 am

Monsoon wrote:Could anyone post some tricky tests cases? Thanks in advance :wink:

[Edit]
I have one (probably silly) question, suppose we have a graph G, we create a graph G', where nodes are connected componets from G, and egdes are bridges from G. G' is a forrest. Now i think that answer i seek is ceil(number_of_leaves_in_G' / 2). Where single node i count as 2 leaves. I can't find counter example to this, but i can't also prove it. Could anyone show me counter example (using this idea i got wa so i consider it to be wrong)?
I can prove the general case now. I think there are 2 cases.
I'll only look at the interesting case, we have more than 1 node (biconnected components).
Let n be the number of leaves, k be the number of single nodes.
Proof:
1) we need at least ceil(n/2)+k = ceil((n+2k)/2) additional edges.
Suppose we added less than ceil(n/2)+k additional edges, then there will exist some nodes of deg 1 (leaves) or deg 0 (single nodes) even after we added edges. For the case of deg1, then clearly we can either enter or leave the node, but not both, so it is not strongly connected to other nodes. For the case of deg 0, it is not connected, so it can't be strongly connected to other nodes.
2) we need at most ceil(n/2)+k additional edges.
We use k-1 edges to connect the k single nodes together, we use ceil(n/2) edges to connect the leaves together into a single component,
Now, if there is at least 2 leaves, remove one of the edges connecting 2 leaves, and use it to connect a single node and one of the leave, and add another edge to connect the remaining leaf with the remaining node. We used a total of ceil(n/2)+k edges.
If there are only k single nodes, clearly k edges are sufficient to form a cycle.
Now we must prove that we can give an orientation of the undirected edges to solve the problem by adding the same number of edges as above.
It is left as an exercise. It is a not so straight forward induction proof. One approach to show that we can swap the edges that we have added until we have a single biconnected component, and then show that any biconnected graph can be given an orientation to become a strongly connected digraph.
Last edited by sclo on Fri Sep 01, 2006 9:32 am, edited 1 time in total.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Fri Sep 01, 2006 11:15 am

Thanks sclo, i will think how to proof the last part :D Thank you very much for the idea of proof.

But if my aproach is correct so maybe somebody would tell me where i have mistake...

Code: Select all

cut after acc, finally found a stupid bug :-)

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 10972 - RevolC FaeLoN

Post by red_apricot » Thu Mar 12, 2015 11:40 am

Certainly an amazing problem: so simply formulated yet conceptually rich. Now I've got a questions: are there duplicate edges? i.e. can (x,y) be listed twice? I know in that case we would simply merge x and y and consider them as one vertex, but that would only lengthen the code.
--Thanks!

EDIT: Checked with assert, and there seems to be no multiple edges.

Post Reply

Return to “Volume 109 (10900-10999)”