Обсуждение @ 1099. Work Scheduling @ Timus Online Judge

Saturn Help me! [22] // Задача 1099. Work Scheduling 21 июн 2004 14:58

Can't you tell me how to solve this problem?
I have used both Blossom and BFS but WA(19).

Dmitry 'Diman_YES' Kovalioff The problem is VERY difficult (+) // Задача 1099. Work Scheduling 21 июн 2004 22:27

Blossom is O(N^4), BFS is wrong in fact - and I don't know absolutely correct and fast algo... So, my solution is just BFS-based heuristics.

Vladimir Yakovlev (USU) I used Gabow's algorithm. It work in O(n^3) [20] // Задача 1099. Work Scheduling 21 июн 2004 22:37

Dmitry 'Diman_YES' Kovalioff Explain, please, or give the link (-) [19] // Задача 1099. Work Scheduling 21 июн 2004 22:50

Vladimir Yakovlev (USU) Re: Explain, please, or give the link (-) [18] // Задача 1099. Work Scheduling 21 июн 2004 22:56

Algorithm is not easy. I can send you a PDF.

Saturn Re: Explain, please, or give the link (-) [2] // Задача 1099. Work Scheduling 22 июн 2004 02:01

Please send me. My email is quangviet2004@yahoo.com
Thanks

Vlad Veselov [PMG17, Vinnitsa] Please, if it is not hard for you, send to me too. veselov@xaker.ru. // Задача 1099. Work Scheduling 22 июн 2004 17:51

Saturn AC now! // Задача 1099. Work Scheduling 5 июл 2004 14:54

I got AC now.Thanks
http://acm.timus.ru/status.aspx?space=1&pos=633550

Dmitry 'Diman_YES' Kovalioff Send it to dimanyes@mail.ru, please (-) // Задача 1099. Work Scheduling 22 июн 2004 18:50

Vladimir Yakovlev (USU) Link [13] // Задача 1099. Work Scheduling 23 июн 2004 01:10

You can download it from
http://dl.by.ru/upload/p221-gabow.pdf

Edited by author 23.06.2004 03:14

mkd easy tests? [11] // Задача 1099. Work Scheduling 23 июн 2004 01:43

To be fair with you I must admit that either the tests are easy or there's a much easier way to solve this problem. I used Berge's theorem (http://mathworld.wolfram.com/BergesTheorem.html) and I have AC (my C source is less than 1.5kB).

Vladimir Yakovlev (USU) Re: easy tests? [10] // Задача 1099. Work Scheduling 23 июн 2004 02:10

Gabow's algorithm also uses Berge's theorem. This theorem is basic in matching theory.

What method did you use?

mkd Re: easy tests? [9] // Задача 1099. Work Scheduling 23 июн 2004 04:35

My algorithm goes as follows:

do
foundPath=false
for i=1 to n do
begin
    if exists augumenting path from vertex i then
    begin
      apply found path
      foundPath=true
    end
end
while (foundPath)

Edited by author 23.06.2004 04:40

Vladimir Yakovlev (USU) Re: easy tests? [8] // Задача 1099. Work Scheduling 23 июн 2004 04:40

But how do you check if exists augumenting path?

mkd Re: easy tests? [7] // Задача 1099. Work Scheduling 23 июн 2004 04:44

I just use a DFS.

Vladimir Yakovlev (USU) Re: easy tests? // Задача 1099. Work Scheduling 23 июн 2004 12:34

A simple DFS? Or something like random search?
Can you send me your source? See e-mail in my profile.

Saturn Re: easy tests? [5] // Задача 1099. Work Scheduling 23 июн 2004 13:40

Can you send it to me? Thanks
quangviet2004@yahoo.com

mkd Re: easy tests? [4] // Задача 1099. Work Scheduling 23 июн 2004 19:32

I can send it to everyone who already has Accepted - otherwise it would be unfair.

But I can give you my DFS:

int FindAndApply(int v)
{
visited[v] = 1;
for (PEdge t=out[v]; t != NULL; t = t->next) {
    int u = t->v;
    if (u == S[v]) continue;
    if (visited[u] || visited[S[u]]) continue;
    visited[u] = 1;
    if (S[u] == 0 || FindAndApply(S[u])) {
      S[u] = v;
      S[v] = u;
      return 1;
    }
}
return 0;
}

S[i] holds a vertex matched with vertex i.

Edited by author 23.06.2004 19:33

Vladimir Yakovlev (USU) Re: easy tests? [3] // Задача 1099. Work Scheduling 23 июн 2004 22:03

You can send it to anybody now becouse it doesn't work anymore ;-) I've added several new tests. All wrong methods (BFS, DFS, random search) won't pass these tests.
If your wrong program still can get AC now, please tell me.

Dmitry 'Diman_YES' Kovalioff Do you have an access to all the tests? If so I do not think it is a fair play (-) [2] // Задача 1099. Work Scheduling 23 июн 2004 22:28

Vladimir Yakovlev (USU) Re: Do you have an access to all the tests? If so I do not think it is a fair play (-) [1] // Задача 1099. Work Scheduling 23 июн 2004 23:40

Yes, I have access, but I don't see the tests if I don't solve the problem.

Vlad Veselov [PMG17, Vinnitsa - KNU, Kiev] Anyone can get any test if he wants it very much. // Задача 1099. Work Scheduling 6 июл 2004 16:42

Dmitry 'Diman_YES' Kovalioff Thanks (-) // Задача 1099. Work Scheduling 23 июн 2004 08:32

Обсуждение задачи 1099. Work Scheduling