| ENG RUS | Timus Online Judge |
Discussion of Problem 1099. Work Schedulingsamwang AC! I love "Flower Tree". // Problem 1099. Work Scheduling 26 Feb 2003 18:38 abc Help!I used blossom in my program but i get TLE. How to beat the time limit? [1] // Problem 1099. Work Scheduling 15 Feb 2003 08:51 abc Oh i find the problem with my code already. Now i get AC. // Problem 1099. Work Scheduling 16 Feb 2003 20:40 Innovative Cat. Could anybody help me to test your ACed program. My friend's ACed program can't get AC now, and...(See in) [3] // Problem 1099. Work Scheduling 9 Jan 2003 16:30 I wrote a program, and I also can't get AC, I have tested 4 days, but still...... I have written to the author, but no reply..... Innovative Cat. My program here. Could anybody help me? [2] // Problem 1099. Work Scheduling 9 Jan 2003 17:07 [deleted by moderator] Edited by moderator 11.04.2004 01:53 Innovative Cat. Nobdy can????? crying........ [1] // Problem 1099. Work Scheduling 10 Jan 2003 16:14 > > [deleted by moderator] Edited by moderator 11.04.2004 01:53 Innovative Cat. I have found the problem....(See in) // Problem 1099. Work Scheduling 10 Jan 2003 17:08 Because the judger use something like "fc" in dos, to compare your output and right output directly....... I tried to change "for u:=1 to n do" to "for u:=n downto 1 do", and a ACed program get WA....... So you'd better ask a ACed person for program.......... Petar Zhivkov Petrov Acc (+) [1] // Problem 1099. Work Scheduling 21 Sep 2002 20:10 I got accepted, but I'm sure there exists a test, which my solution will fail to solve. My solution is nothing but hungarian algo ( bipartite version ), but it passes the tests because of some greedies assisting with it. It would be nice to code the real algo some day ( it seems pretty sophisticated :). pesho hawking but this is not bipartite graph:(,why you can got acc,but i can't // Problem 1099. Work Scheduling 8 Oct 2002 16:00 > I got accepted, but I'm sure there exists a test, which my solution > will fail to solve. My solution is nothing but hungarian algo ( > bipartite version ), but it passes the tests because of some greedies > assisting with it. It would be nice to code the real algo some day ( > it seems pretty sophisticated :). > > pesho Miguel Angel Bipartite graph + Maximum Flow, i get WA, why??? (+) [1] // Problem 1099. Work Scheduling 20 Sep 2002 05:01 [deleted by moderator] Edited by moderator 11.04.2004 01:52 Andrey Popyk (popyk@ief.tup.km.ua) This graph is not bipartite! // Problem 1099. Work Scheduling 21 Sep 2002 15:55 Algorithmus_UA(algorithmus@univ.kiev.ua) What is wrong in my program, I got WA. Please give me some test [1] // Problem 1099. Work Scheduling 19 Jun 2002 17:03 [deleted by moderator] Edited by moderator 11.04.2004 01:52 Andrey Popyk (popyk@ief.tup.km.ua) Re: What is wrong in my program, I got WA. Please give me some test // Problem 1099. Work Scheduling 20 Jun 2002 12:48 This is general graph matching, and you cannot find augmenting path in such way, that you use in bipartite graph matching. asif Is there an algorithm of time complexity less than O(n^4)? // Problem 1099. Work Scheduling 5 Apr 2002 14:41 Is there an algorithm of time complexity less than O(n^4)? Edmond's blossom algorithm with adjacency matrix of time complexity O(n^4) gets TLE. RightAnswer Please correct the mistake in the test-data! // Problem 1099. Work Scheduling 14 Aug 2001 08:11 There are two equal numbers in a line, but this should not appear according to the problem. Longman 2001 @Killer team ZJU 1099,Do we need blossoms? [2] // Problem 1099. Work Scheduling 3 Jun 2001 14:46 I've used the algorithm for bipartite graph to this problem,and it got WA.So i refer to some graph theory book,it says that we must handle blossoms,but it did not say why this!From my test data the bipartite graph algorithm works fine!Can anybody explain this to me?Or give out some counter examples that the bipartite graph algorithm fails... Petko Minkov Re: 1099,Do we need blossoms? [1] // Problem 1099. Work Scheduling 4 Jun 2001 01:38 I asked about this problem. There are some "flowers" things that make the bipartite algorithm to fail. IT's based on a true theorem, but the DFS fails. However, I do the following thing - DFS, but observse the edges in random way, not for(i=1;i<=n;i++) and things like that but a permutation. Damn, i think my English is not good :))) Jivko Ganev Re: 1099,Do we need blossoms? // Problem 1099. Work Scheduling 4 Jun 2001 19:50 I have generated case(not randomly) where your solution fails. But it is not uploaded, expect rejudge. Longman 2001 @Killer team ZJU 1099,Are we need blossoms? // Problem 1099. Work Scheduling 3 Jun 2001 14:46 I've used the algorithm for bipartite graph to this problem,and it got WA.So i refer to some graph theory book,it says that we must handle blossoms,but it did not say why this!From my test data the bipartite graph algorithm works fine!Can anybody explain this to me?Or give out some counter examples that the bipartite graph algorithm fails...
|