Discussion @ 1128. Partition into Groups @ Timus Online Judge

Show all messages Hide all messages

(to anyone who got AC): Is "NO SOLUTION" impossible for your AC? Locomotive 7 Mar 2003 12:22

Re: (to anyone who got AC): Is "NO SOLUTION" impossible for your AC? Tiberiu Danet 7 Mar 2003 13:02

Yes.

SO may you tell me a test which its answer "NO SOLUTION"? Locomotive 7 Mar 2003 20:15

> Yes.

Re: SO may you tell me a test which its answer "NO SOLUTION"? Tiberiu Danet 8 Mar 2003 01:52

You asked if "No solution" is impossible. My answer was yes. So I'm
saying that such a test doesn't exist.

+^^+ Locomotive 8 Mar 2003 16:58

Thanks! it was matter of bad English for such an Iranian Boy...
Can you help me a little bit more?
which algorithm i should use?
DFS and BFS dont help...
Brute Force doesn`t seem beauty ;)!
Please Help Me
Best
Aidin_n7@hotmail.com

Re: +^^+ Tiberiu Danet 9 Mar 2003 20:16

First put every child into the first team.
Then while there exists a child who has more than one opponent in his
team, just move him to the other team.

but i think it wont be so simple r u sure it is correct? Locomotive 9 Mar 2003 23:48

Thanks! me and also my friends got AC :P Locomotive 10 Mar 2003 18:13

Re: Thanks! me and also my friends got AC :P charles.king 1 Apr 2004 08:19

I don't know how. Could you explain it for me? Thank you very much!

Re: +^^+ lamer 27 Mar 2005 19:38

Can you give me a code, plz?

Re: +^^+ Sandro 12 Jul 2005 17:46

The idea really works. But did you prove that this algo is correct? (Why will it finish the work in a finite number of steps?)

Re: +^^+ shrek 6 Nov 2006 11:42

It works because in each step number of edges between the two parts increases and obviously it can't be more than E.

Nice idea, and very nice proof [-] Chmel_Tolstiy 27 Jul 2007 14:11

Nice idea, and very nice proof [-] +1 ! Eric Alejandro Destefains 14 Aug 2009 02:15

Re: +^^+ svr 26 Nov 2011 08:40

This proof incomplete and doesn't shed light to the point.
We should add next: if person Q on the left side have >=2 enemy on the left
then he don't have more than 1 enemies in persons on the right
because in other case he would have >=4 enemies.

Edited by author 26.11.2011 08:42

termination proof Aneto 13 Jan 2013 01:48

It is clear that if proposed algorithm terminates then we have found a solution. But does it allways terminate? I will try to add my 5 cents by giving a short yet complete proof of termination.

Let us first introduce the decreasing measure M. We define M to be equal to the number of edges of the graph on the same(!) side. Algorithm terminates if measure decreases with each iteration of algorithm. Let us consider 3 possible situations:

1) We change side of a child with 3 enemies on his side. Then M decreases by 3.
2a) We change side of a child with 2 enemies on his side and 0 enemies on other side. Then measure decreases by 2.
2b) We change side of a child with 2 enemies on his side and 1 enemy on other side. Then M decreases by 2 and increases by 1.
3) If child has only one enemy on his side, then we do nothing.

According to described cases M will decrease after each iteration. Hence, algorithm terminates.

Hope this helps :)

It seems so... Spatarel Dan Constantin 26 Mar 2006 19:12

Edited by author 27.03.2006 01:16

It seems so... Spatarel Dan Constantin 26 Mar 2006 19:23

Discussion of Problem 1128. Partition into Groups