Discussion @ 1099. Work Scheduling @ Timus Online Judge

Help me! Saturn 21 Jun 2004 14:58

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

The problem is VERY difficult (+) Dmitry 'Diman_YES' Kovalioff 21 Jun 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.

I used Gabow's algorithm. It work in O(n^3) Vladimir Yakovlev (USU) 21 Jun 2004 22:37

Explain, please, or give the link (-) Dmitry 'Diman_YES' Kovalioff 21 Jun 2004 22:50

Re: Explain, please, or give the link (-) Vladimir Yakovlev (USU) 21 Jun 2004 22:56

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

Re: Explain, please, or give the link (-) Saturn 22 Jun 2004 02:01

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

Please, if it is not hard for you, send to me too. veselov@xaker.ru. Vlad Veselov [PMG17, Vinnitsa] 22 Jun 2004 17:51

AC now! Saturn 5 Jul 2004 14:54

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

Send it to dimanyes@mail.ru, please (-) Dmitry 'Diman_YES' Kovalioff 22 Jun 2004 18:50

Link Vladimir Yakovlev (USU) 23 Jun 2004 01:10

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

Edited by author 23.06.2004 03:14

easy tests? mkd 23 Jun 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).

Re: easy tests? Vladimir Yakovlev (USU) 23 Jun 2004 02:10

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

What method did you use?

Re: easy tests? mkd 23 Jun 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

Re: easy tests? Vladimir Yakovlev (USU) 23 Jun 2004 04:40

But how do you check if exists augumenting path?

Re: easy tests? mkd 23 Jun 2004 04:44

I just use a DFS.

Re: easy tests? Vladimir Yakovlev (USU) 23 Jun 2004 12:34

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

Re: easy tests? Saturn 23 Jun 2004 13:40

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

Re: easy tests? mkd 23 Jun 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

Re: easy tests? Vladimir Yakovlev (USU) 23 Jun 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.

Do you have an access to all the tests? If so I do not think it is a fair play (-) Dmitry 'Diman_YES' Kovalioff 23 Jun 2004 22:28

Re: Do you have an access to all the tests? If so I do not think it is a fair play (-) Vladimir Yakovlev (USU) 23 Jun 2004 23:40

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

Anyone can get any test if he wants it very much. Vlad Veselov [PMG17, Vinnitsa - KNU, Kiev] 6 Jul 2004 16:42

Thanks (-) Dmitry 'Diman_YES' Kovalioff 23 Jun 2004 08:32

Discussion of Problem 1099. Work Scheduling