(to anyone who got AC): Is "NO SOLUTION" impossible for your AC?

Re: (to anyone who got AC): Is "NO SOLUTION" impossible for your AC?

Yes.

SO may you tell me a test which its answer "NO SOLUTION"?

> Yes.

Re: SO may you tell me a test which its answer "NO SOLUTION"?

You asked if "No solution" is impossible. My answer was yes. So I'm

saying that such a test doesn't exist.

+^^+

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: +^^+

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?

Thanks! me and also my friends got AC :P

>

Re: Thanks! me and also my friends got AC :P

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

Re: +^^+

Posted by

lamer 27 Mar 2005 19:38

Can you give me a code, plz?

Re: +^^+

Posted by

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?)

It seems so...

*Edited by author 27.03.2006 01:16*

Re: +^^+

Posted by

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 [-]

Nice idea, and very nice proof [-] +1 !

XD

Re: +^^+

Posted by

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

Posted by

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 :)