| ENG RUS | Timus Online Judge |
Обсуждение задачи 1128. Деление на группыLocomotive (to anyone who got AC): Is "NO SOLUTION" impossible for your AC? [17] // Задача 1128. Деление на группы 7 мар 2003 12:22 Tiberiu Danet Re: (to anyone who got AC): Is "NO SOLUTION" impossible for your AC? [16] // Задача 1128. Деление на группы 7 мар 2003 13:02 Yes. Locomotive SO may you tell me a test which its answer "NO SOLUTION"? [13] // Задача 1128. Деление на группы 7 мар 2003 20:15 > Yes. Tiberiu Danet Re: SO may you tell me a test which its answer "NO SOLUTION"? [12] // Задача 1128. Деление на группы 8 мар 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 +^^+ [11] // Задача 1128. Деление на группы 8 мар 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 Tiberiu Danet Re: +^^+ [10] // Задача 1128. Деление на группы 9 мар 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. Locomotive but i think it wont be so simple r u sure it is correct? [2] // Задача 1128. Деление на группы 9 мар 2003 23:48 Locomotive Thanks! me and also my friends got AC :P [1] // Задача 1128. Деление на группы 10 мар 2003 18:13 > charles.king Re: Thanks! me and also my friends got AC :P // Задача 1128. Деление на группы 1 апр 2004 08:19 I don't know how. Could you explain it for me? Thank you very much! lamer Re: +^^+ [6] // Задача 1128. Деление на группы 27 мар 2005 19:38 Can you give me a code, plz? Sandro (USU) Re: +^^+ [5] // Задача 1128. Деление на группы 12 июл 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?) shrek Re: +^^+ [4] // Задача 1128. Деление на группы 6 ноя 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. Chmel_Tolstiy Nice idea, and very nice proof [-] [1] // Задача 1128. Деление на группы 27 июл 2007 14:11 Eric Alejandro Destefains Nice idea, and very nice proof [-] +1 ! // Задача 1128. Деление на группы 14 авг 2009 02:15 XD svr Re: +^^+ [1] // Задача 1128. Деление на группы 26 ноя 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 Aneto termination proof // Задача 1128. Деление на группы 13 янв 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 :) 👨🏻💻 Spatarel Dan Constantin It seems so... [1] // Задача 1128. Деление на группы 26 мар 2006 19:12 Edited by author 27.03.2006 01:16 👨🏻💻 Spatarel Dan Constantin It seems so... // Задача 1128. Деление на группы 26 мар 2006 19:23 |