Discussion @ 1156. Two Rounds @ Timus Online Judge

I use Dynamic Prog. May Be It's wrong. Help with test or hint, please. WA#3

Posted by Alexey 1 May 2006 15:29

My programm passes all my tests, but WA#3.
Please, help.
Thanks a lot.

Re: I use Dynamic Prog. May Be It's wrong. Help with test or hint, please. WA#3

Posted by Zubyk Taras(Khmelnitsky) 1 May 2006 18:21

How you here have applied Dinamic Prog.? I the ambassador aside graph.

Re: I use Dynamic Prog. May Be It's wrong. Help with test or hint, please. WA#3

Posted by Alexey 2 May 2006 13:16

Hi, Taras.
I use simple method:
I read two variables ot and ku.
If ot and ku are in the same group, I Output('IMPOSSIBLE');
If they are in the different groups then I Continue
else I put one variable into the first group
and other into the second group.
After that I divide "free" tasks between the groups...
I hoped that It would get more than two tests...
May be I should try to use graphs...

BTW, tell me youre ICQ number, I cann't find you...

Edited by author 02.05.2006 13:17

Re: I use Dynamic Prog. May Be It's wrong. Help with test or hint, please. WA#3

Posted by 冰渊 26 Jul 2006 13:55

try this test, maybe will help you:

4 6
1 2
2 3
3 4
4 5
6 7
7 8

ANS:
1 3 5 7
2 4 6 8

Thanks! It helps me to find out my program is wrong, but not the bug... (-

Posted by Alexey 2 Aug 2006 13:19

Re: I use Dynamic Prog. May Be It's wrong. Help with test or hint, please. WA#3

Posted by SPIRiT 16 Aug 2006 12:50

You can use it. I used it as well. First you must paint the graph with black and white (use BFS) so that two vertices with the same edge are of different colors. After that you have pairs of integers and you have to combine them so that you have N in each round (that's not always possible).

Re: I use Dynamic Prog. May Be It's wrong. Help with test or hint, please. WA#3

Posted by mosiomohsen 25 Sep 2013 23:00

how I should combine them ??

Discussion of Problem 1156. Two Rounds