10982 - Troublemakers

rushel · Post by **rushel** » Mon Jan 23, 2006 9:46 am

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.

what is wrong with my algo? or give me the correct algo. Please help me.

Per · Post by **Per** » Mon Jan 23, 2006 10:55 am

What do you do if the graph is not bicolorable?

rushel · Post by **rushel** » Mon Jan 23, 2006 11:00 am

Yes i missed that case. But i am new at matching problems this is my first time. Can u help me?

Per · Post by **Per** » Mon Jan 23, 2006 11:10 am

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 · Post by **rushel** » Mon Jan 23, 2006 11:12 am

Thanks a lot Per. I think ur are a great helper.

kp · Post by kp » Mon Jan 23, 2006 1:31 pm

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
number of random divisions. If feasible division was not found
then it is impossible to split graph in such a way.

Or you mean something else???

Adrian Kuegel · Post by **Adrian Kuegel** » Mon Jan 23, 2006 2:14 pm

Actually, it is always possible, so I guess the "Impossible" was just there to fool people.

Abednego · Post by **Abednego** » Mon Jan 23, 2006 3:43 pm

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.

Per · Post by **Per** » Mon Jan 23, 2006 7:48 pm

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
number of random divisions. If feasible division was not found
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 · Post by **Renat** » Mon Jan 23, 2006 8:26 pm

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 · Post by **Quantris** » Tue Jan 24, 2006 2:55 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 · Post by **L I M O N** » Tue Jan 24, 2006 3:31 pm

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

thx in advanced

Abednego · Post by **Abednego** » Tue Jan 24, 2006 3:34 pm

For example,

Code: Select all

Case #1: 2
1 2

kissksh · Post by **kissksh** » Fri Feb 10, 2006 11:46 am

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 · Post by **sclo** » Sat Feb 11, 2006 12:46 am

output can be
1 3 4 / or / 2 / or / 2 3 ???
Then May I print one of them?

Yes, you can print any of them. This is special judge problem.