10380 - Shogi Tournament

[hank]

Thanks in advance.

[Whinii F.]

Your program easily fails on big inputs..

like

1
6 4
-- -- -- -- -- --
-- -- -- -- -- --
-- -- -- -- -- --
-- -- -- -- -- --
-- -- -- -- -- --
-- -- -- -- -- --

Your program's output is

Player 4 can win with 3 point(s).

-- 11 11 00 11 10 : 7
00 -- 00 00 00 00 : 0
00 11 -- 00 00 00 : 2
11 11 11 -- 11 11 : 10
00 11 11 00 -- 00 : 4
01 11 11 00 11 -- : 7

While the correct output is

Player 4 can win with 6 point(s).

-- 11 10 00 10 00 : 4
00 -- 10 00 10 11 : 4
01 01 -- 00 10 10 : 4
11 11 11 -- 11 11 : 10
01 01 01 00 -- 10 : 4
11 00 01 00 01 -- : 4

I suggest you to think of a different approach.
Good luck!

[hank]

Thanks for your help.
After I realized the problem could be solved by MaxFlow, I fixed my code.
But now I have difficulty dealing with finding the augmenting path.
I think BFS is not a good idea because it is too slow and takes too much space.
Finally, I use DFS to find the augmenting path. But this time, I still got TLE.
Do you know how to improve this situation?

[Larry]

I have not solved this problem yet, but preflow-push works for me pretty quick, usually..

[Whinii F.]

BFS it may be slower itself, but it is proven BFS results in higher performance because BFS returns a shortest path.. A variation of Ford-Fulkerson method using BFS to find augmenting paths is called Edmonds-Karp. CLR handles it so you can look up.

Anyway there are problems that E-K doesn't work too. I should code my own preflow-push someday. :3

[koala]

I got WA at about 10.x sec.
Can anyone tell me why or give me some testcases?
[pascal]
Program Shogi_Tournament;

Const
Maxn=50;
Maxmatch=Maxn*Maxn;

Type
Link=^Node;
Node=Record
data,c,f:Longint;
next,g:Link;
End;

Var
a:Array [1..Maxmatch+Maxn+2] of Link;
res:Array [1..Maxn,1..Maxn,1..2] of Longint;
score:Array [1..Maxn] of Longint;
NumOfTestcases,Testcase,m,n,winner,ans:Longint;

Procedure Read_Result(Var k:Longint);
Var
ch:Char;
Begin
Repeat
Read(ch);
Until (ch='-') or (ch='0') or (ch='1');
If ch='-' Then k:=-1 Else k:=Ord(ch)-Ord('0');
End;

Procedure Input_Data;
Var
i,j:Longint;
Begin
Read(n,winner);
For i:=1 to n Do
For j:=1 to n Do
Begin
Read_Result(res[i,j,1]);
Read_Result(res[i,j,2]);
End;
End;

Procedure Insert(x,y,c:Longint);
Var
d,p:Link;
Begin
New(d); d^.data:=y; d^.c:=c; d^.f:=0; d^.next:=a[x]; a[x]:=d;
New(p); p^.data:=x; p^.c:=0; p^.f:=0; p^.next:=a[y]; a[y]:=p;
d^.g:=p; p^.g:=d;
End;

Procedure Refresh(c:Longint);
Var
i:Longint;
p:Link;
Begin
For i:=1 to m+n+2 Do
Begin
p:=a;
While p<>Nil Do
Begin
p^.f:=0;
p:=p^.next;
End;
End;
p:=a[m+n+2];
While p<>Nil Do
Begin
p^.g^.c:=c-score[p^.data-m];
p:=p^.next;
End;
End;

Function Ford(u,v,n:Longint):Boolean;
Var
l,p,q:Array [1..Maxmatch+Maxn+2] of Longint;
w:Array [1..Maxmatch+Maxn+2] of Link;
head,tail,i,j,delta:Longint;
x:Link;
Begin
While True Do
Begin
Fillchar(l,Sizeof(l),0); l:=Maxlongint;
Fillchar(p,Sizeof(p),0); p:=u;
head:=1; tail:=1; q[1]:=u;
While head<=tail Do
Begin
i:=q[head];
x:=a;
While x<>Nil Do
Begin
j:=x^.data;
If (p[j]=0) and (x^.f<x^.c) Then
Begin
l[j]:=l; If x^.c-x^.f<l[j] Then l[j]:=x^.c-x^.f;
p[j]:=i;
Inc(tail); q[tail]:=j;
w[j]:=x;
End;
x:=x^.next;
End;
Inc(head);
End;
If l[v]=0 Then Break;
delta:=l[v];
j:=v;
While j<>u Do
Begin
Inc(w[j]^.f,delta); w[j]^.g^.f:=-w[j]^.f;
j:=p[j];
End;
End;
x:=a;
While x<>Nil Do
Begin
If (x^.c>0) and (x^.c>x^.f) Then
Begin
Ford:=False;
Exit;
End;
x:=x^.next;
End;
Ford:=True;
End;

Procedure Solve;
Var
i,j,k,low,high,mid,cur:Longint;
Begin
Fillchar(score,Sizeof(score),0);
m:=0;
For i:=1 to n-1 Do
For j:=i+1 to n Do
For k:=1 to 2 Do
If res[i,j,k]<>-1
Then
If res[i,j,k]=0 Then Inc(score[j]) Else Inc(score)
Else
If (i=winner) or (j=winner)
Then Begin
Inc(score[winner]);
If i=winner
Then Begin res[i,j,k]:=1; res[j,i,k]:=0 End
Else Begin res[i,j,k]:=0; res[j,i,k]:=1 End;
End
Else Inc(m);
low:=0;
For j:=1 to n Do
If j<>winner Then
Begin
If score[j]>low Then low:=score[j];
If score[winner]<score[j] Then
Begin
ans:=-1;
Exit;
End;
End;
Fillchar(a,Sizeof(a),0);
For j:=1 to m Do Insert(m+n+1,j,1);
cur:=1;
For i:=1 to n-1 Do
For j:=i+1 to n Do
For k:=1 to 2 Do
If res[i,j,k]=-1 Then
Begin
Insert(cur,m+i,1); Insert(cur,m+j,1);
Inc(cur);
End;
For i:=1 to n Do
If i<>winner Then Insert(m+i,m+n+2,score[winner]-score);
If not Ford(m+n+1,m+n+2,m+n+2) Then
Begin
ans:=-1;
Exit;
End;
high:=score[winner];
While low<high Do
Begin
mid:=(low+high) div 2;
Refresh(mid);
If Ford(m+n+1,m+n+2,m+n+2) Then high:=mid Else low:=mid+1;
End;
Refresh(low);
If Ford(m+n+1,m+n+2,m+n+2) Then ans:=low;
End;

Procedure Output_Data;
Var
i,j,k,tot,x,y,temp:Longint;
inverse:Boolean;
p:Link;
Begin
If Testcase>1 Then Writeln;
If ans=-1
Then Writeln('Player ',winner,' can''t win!')
Else Begin
Writeln('Player ',winner,' can win with ',score[winner]-ans,' point(s).');
Writeln;
For i:=1 to m Do
Begin
x:=0; y:=0;
inverse:=False;
p:=a;
While p<>Nil Do
Begin
If p^.c>0 Then
If x=0
Then Begin
x:=p^.data-m;
If p^.f=0 Then inverse:=True;
End
Else y:=p^.data-m;
p:=p^.next;
End;
If inverse Then
Begin
temp:=x; x:=y; y:=temp;
End;
If res[x,y,1]=-1
Then Begin
res[x,y,1]:=1; res[y,x,1]:=0;
End
Else Begin
res[x,y,2]:=1; res[y,x,2]:=0;
End;
End;
For i:=1 to n Do
Begin
tot:=0;
For j:=1 to n Do
Begin
For k:=1 to 2 Do
If res[i,j,k]=-1
Then Write('-')
Else Begin
Write(res[i,j,k]);
Inc(tot,res[i,j,k]);
End;
Write(' ');
End;
Writeln(': ',tot);
End;
End;
End;

Procedure Release(p:Link);
Begin
If p<>Nil Then
Begin
Release(p^.next);
Dispose(p);
End;
End;

Procedure Set_Free;
Var
i:Longint;
Begin
For i:=1 to m+n+2 Do Release(a);
End;

Begin
Read(NumOfTestcases);
For Testcase:=1 to NumOfTestcases Do
Begin
Input_Data;
Solve;
Output_Data;
Set_Free;
End;
End.
[/pascal]

[fushar]

This problem is very interesting. But can anybody here explain, why this problem can be solved with maxflow? How is the graph then? I'm really confused....

[bcde906]

discount Diesel,wholesale diesel jeans is an Italian design company. It is best known for clothing aimed at the youth market, particularly wholesale diesel jeans.

[fushar]

????????????????
Are you advertising??

Come on, please help me solve this problem....

[fushar]

Hello, anyone please help me!!

[Bruno]

If I set the games as nodes, linking with the guys, on the worst case (50 guys) there will be +- 2000 games (vertexes), and +- 4000 links (edges)? Is that right? Edmons-Karp is VE², I guess it wont run on time :/ .. I used the wikipedia code and for 50 guys it is still running.. is there any improvements I can make? Is there any other approach for the problem?

Thank you!