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