10982 - Troublemakers

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

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

10982 - Troublemakers

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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

What do you do if the graph is not bicolorable?

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

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

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

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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.

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

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

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
New poster
Posts: 10
Joined: Thu Jul 18, 2002 2:40 pm
Location: Russia
Contact:

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
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

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
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

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

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

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

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

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

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.

Post Reply

Return to “Volume 109 (10900-10999)”