## 10982 - Troublemakers

Moderator: Board moderators

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

### 10982 - Troublemakers

I got WA. my algorithm is:
. first i tried to bicolor given graph.
. then put the same colored vertex in one class and others in another class.
. check that the two class satisfies the given constraints and print the result.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
What do you do if the graph is not bicolorable?

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am
Yes i missed that case. But i am new at matching problems this is my first time. Can u help me?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
This is not a matching problem.

Hint: take a random division into two groups. What is the probability that a fixed pair is split by this division? What is the expected value on the total number of pairs split?

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am
Thanks a lot Per. I think ur are a great helper.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
2 Per:
I am a little bit confused by your last post.

You want to say that we need to calculate probability
of splitting n/2 pairs and after that just do appropriate
then it is impossible to split graph in such a way.

Or you mean something else???

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Actually, it is always possible, so I guess the "Impossible" was just there to fool people.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Yay Per! You found the solution that I was hoping someone would find. There is also a very simple greedy solution, but the randomized one is a lot more beautiful.
If only I had as much free time as I did in college...

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
kp wrote:2 Per:
I am a little bit confused by your last post.

You want to say that we need to calculate probability
of splitting n/2 pairs and after that just do appropriate
then it is impossible to split graph in such a way.
No. I wanted to say exactly what I said.
Abednego wrote:Yay Per! You found the solution that I was hoping someone would find. There is also a very simple greedy solution, but the randomized one is a lot more beautiful.
Thanks, but I can't really claim to have found it... you'll hardly find any max-cut paper not mentioning it.
The greedy solution is essentially the derandomization of the randomized one, or are you talking about something else?

Renat
New poster
Posts: 10
Joined: Thu Jul 18, 2002 2:40 pm
Location: Russia
Contact:
Maybe the greedy solution is the following: take vertices one by one, and put each of them in the class where it creates less number of pairs with already added vertices.

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Yes, plus it is easy to see why:

Every "troublesome" pair will be considered exactly once (namely, when you have placed one of the members and are deciding where to put the other). At every decision, you "enable" at most half of the pairs that you are considering. Therefore, at the end, you will have "enabled" at most half the total number of pairs. QED.

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Contact:
what's the output for this input ?
1
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

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

Code: Select all

Case #1: 2
1 2
If only I had as much free time as I did in college...

kissksh
New poster
Posts: 3
Joined: Sat Sep 24, 2005 10:11 am
Contact:

### 10982 - Troublemakers

There are a few output in this problem, aren't there ?

In Sample input .

4 3
1 2
2 3
3 4

->

output can be

1 3 4 / or / 2 / or / 2 3 ???

Then May I print one of them?

============================
sorry for my foor english

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm