## 670 - The dog task

Moderator: Board moderators

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

### 670 - The dog task

Hello!

I'm trying to solve this problem by applying network flow to it, with multiple sources for each meeting position and multiple sources for each interesting positions.

I set d[u, v] (capacity) 1 if the dog can visit intereseted point v after meeting its master at point u..

then I apply Edmonds-Karp to calculate the maximum flow, and if the edge f[u, v] has a positive flow in the maximum flow network, then the dog visits v after u ..

and I'm getting many WAs. :'(

Any ideas or suggestions, or tricky cases(I wonder?) would be welcome..

Last edited by Whinii F. on Sat Mar 01, 2003 12:02 am, edited 1 time in total.
turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
I assumed you reduced this problem to a bipartite-matching problem ... I added 2 nodes (source and sink) whose max-flow will be calculated, ... left-partition is the main-route (Bob's route), and right-partition is the interesting-points ...

I solved this using max. cardinality bipartite-matching exactly the same logic you described, except that I used Ford-Fulkerson ... I didn't see any trick here ... but here's a list that I looked at the most when trying to solve this problem:

1. This problem has multiple-input format and special-correction. Almost tripped me there ...

2. The way to determine if Ralph can visit c when Bob's walking from a to b. I tried to avoid floating-point here but I couldn't. I squared both sides of equation and tried to do as much integer operation first before I introduced the floating-point stuff.

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).
Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

### Thanks, turuthok!

Yes, I've modeled this problem as maximum bipartite matching. =)

I knew that it was a multiple input problem, so it wasn't the problem. Today I analyzed my code and found a bug.. not initializing flow capacity FROM the sink to the nodes.. after that I got AC. p.s. As far as I know, Edmonds-Karp IS Ford-Fulkerson, since F-F is a method and not an algorithm. E-K is a BFS-augmenting-path-finding version of Ford Fulkerson.

Have a good day!! liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

### 670 :(

I read data like this and get RUNTIME ERROR

plz help me!

Code: Select all

``````while(scanf("%d", &N) == 1)
{
.....
}``````
titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
this is a multiple input problem. you should read the format of multiple input problem.
Kalo mau kaya, buat apa sekolah?
kwedeer
New poster
Posts: 44
Joined: Thu Dec 15, 2005 11:28 pm
well - I am totally confused - this is a maximum bipartite matching problem - I know algorithm but I have two unclear things:
1) in any step when we should choose augmenting path - there are the same capacity for each possible path (from source to target) - always 1 - so - which path to choose. This is important thing because one can choose path which can prohibit further increase of matching...
2) if the wrong path is choosen and assigned to matching (and therefore this path has capacity 1 from target to source - so - it can be removed from matching as augmenting path) - how can we determine that some of matching edges should be deleeted and so - to open possibiliities for increase?

I have found in Internet other algorithms - e.g. alternating path algorithm - seems to be simple - but no idea what to do with even-length paths...

Well - actually I am looking now on pics of Cormen book 27chapter where the matching with 2 edges is converted to matching with 3 edges... at least one edge is removed in process (the upper one) - but what is rationale behind this removal? What argruments Cormen et al can use to do this?

Thanx for any idea in advance!
kwedeer
New poster
Posts: 44
Joined: Thu Dec 15, 2005 11:28 pm
I went out to Internet again and looked for some good practicel maximal matching explanation - so - I found approx dozen of lecture notes and presentations - and all the same - all of them contains one-to-one texts, theorem numeration, pictures from Cormen - and all of them says - that flow should be applied and noone goes further... and it is well done - because further any logic isn't... it is impossibe to explain why should do in tha way  mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
There's a good description of augmenting-paths method for bipartite matching (without network flows) here: http://www.ecp6.jussieu.fr/pageperso/bo ... apter5.pdf
kwedeer
New poster
Posts: 44
Joined: Thu Dec 15, 2005 11:28 pm
OMG - so - there can more more than one matchings with the maximum cardinality and - those matching can be determined by completely different sequences (somehow non-intersecting) of augmenting paths, in the case with Cormend picture - 27.8 (a) and (b) belongs to different sequeces and I state that there doesn't exist sequence of augmenting paths how to arrive from (a) to (b)... so - why this fact is not mentioned in any tutorial? (acm task therefore is asked to wrie any of routes) why there is no done any classification of possible maximum matchings regarding of different bipartita graph porperties (one can imagine the investigation of such number os maximum matchingas some function of density and so on...)

only hope, that judge will reckognize any of valid matchings....
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
OMG - so - there can more more than one matchings with the maximum cardinality
That's so obvious... for example in a graph with edges (A, B1), (A, B2), a maximum-cardinality matching consists of a single edge, any of the two.
only hope, that judge will reckognize any of valid matchings....
Problem 670 has a special judge (it's marked with a yellow sign), so any correct output should be accepted.
kwedeer
New poster
Posts: 44
Joined: Thu Dec 15, 2005 11:28 pm
I have finally made my solution.

I have used:
1) max flow algorithm for finding the maximum matching of bipartite graph (on graph represented as matrix - total points (bob points + dog points + dummy source + dummy target)^2 - well this is not the best way - but - as far I have tried some time ago - then judge is giving errors in case of use of dynamic arrays... and so on...)
2) breadth-first search for finding the augmenting path

My program gives correct answer for the test case provided in task, but - judge gives WA. Can anyone provide some test case for which the program fails to return corect answer? Thanks in advance!

Code: Select all

``````program Prg6700(input, output);

{\$APPTYPE CONSOLE}

uses
SysUtils;

var
{0 - source,
1...N - Bob points,
N+1...M - dog points,
N+M+1 - target}
numberOfCases: Integer;
gm: array [0..201] of array [0..201] of byte; //adjacnecy list for graph
N,M: Integer;
xn,yn,xm,ym: array [1..100] of Integer;
db1b2: array[1..99] of double;
//N - Bobs route (left-hand-side)
//M - interesting places (right-hand-side)
i,j,iii: Integer;
target: Integer;
pathExists: boolean;
targetAchieved, targetDecided: boolean;
distance: array [0..201] of Integer;
queue: array [0..201] of Integer;
queueLength: Integer;
predecessors: array [0..201] of Integer;
color: array [0..201] of byte;
u: Integer;
resultX,resultY: array[0..402] of Integer;
resultLength: Integer;
//for updating using augmenting path data
sourceAchieved: boolean;
currVertex: Integer;

procedure printGm;
var ii,jj: Integer;
begin
writeln('=== begin ===');
for ii:=0 to target do begin
if ((ii=1) or (ii=N+1) or (ii=N+M+1)) then begin
for jj:=0 to N+M+4 do
write('===');
writeln;
end;
for jj:=0 to target do begin
if ((jj=1) or (jj=N+1) or (jj=N+M+1)) then
write('|||');
write(Format('%.2d ',[gm[ii,jj]]));
end;
writeln;
end;
writeln('=== end ===');
end;

procedure printPath;
var ii: Integer;
begin
writeln('--- path - begin ---');
for ii:=0 to target do begin
if predecessors[ii]>-1 then
writeln(IntToStr(predecessors[ii])+' -> '+IntToStr(ii));
end;
writeln('--- path - end ---');
end;

procedure enqueue(value: Integer);
begin
queue[freeSlot]:=value;
inc(freeSlot);
inc(queueLength);
end;

procedure dequeue;
begin
dec(queueLength);
end;

begin
if queueLength>0
else Result:=-1;
end;

procedure initialiseQueue;
begin
freeSlot:=0;
queueLength:=0;
end;

function d(x1,y1,x2,y2: Integer): double;
begin
Result:=sqrt(sqr(x2-x1)+sqr(y2-y1));
end;
begin
{
AssignFile(Input, 'in06__.txt');
Reset(Input);
AssignFile(Output, 'out06__.txt');
Rewrite(Output);
}

for iii:=1 to numberOfCases do begin

target:=N+M+1;
for i:=0 to 201 do
for j:=0 to 201 do
gm[i,j]:=0;
//for source to left part
for i:=1 to N do
gm[0,i]:=1;
//from right part to target
for i:=N+1 to target do
gm[i,target]:=1;
for i:=1 to N do begin
if i>1 then begin
db1b2[i-1]:=d(xn[i-1],yn[i-1],xn[i],yn[i]);
end;
end; //for - reading Bob's route
for i:=1 to M do begin
for j:=1 to (N-1) do begin
if ( (d(xn[j],yn[j],xm[i],ym[i])+
d(xm[i],ym[i],xn[j+1],yn[j+1])) <=2*db1b2[j] ) then begin
gm[j,N+i]:=1;
end;
end; //for j...
end; //for - reading interesting places or dog

repeat
//finding the path
for i:=1 to 201 do
predecessors[i]:=-1;
initialiseQueue;
distance:=0;
predecessors:=0;
enqueue(0);
targetAchieved:=false;
targetDecided:=false;
for i:=1 to target do
color[i]:=1;
color:=2;
while ((not targetAchieved) and (not targetDecided)) do begin
//the search is done if no more vortices are in queue
if u>-1 then begin
for i:=0 to target do begin
if ((gm[u,i]>0) and (color[i]=1) and (i<>u)) then begin
color[i]:=2;
distance[i]:=distance[u]+1;
predecessors[i]:=u;
enqueue(i);
if i=target then begin
targetAchieved:=True;
targetDecided:=True
end;
end;
end; //for i... - over all the members of adjacency list
dequeue;
color[u]:=3;
end else begin
targetDecided:=True
end;
end; //while not targetAchieved...
if targetAchieved then begin
// update the graphs for the next iteration - to extend the bipartite matching
//source vertex is excluded from check
// update should be done only for vortices on augmenting path
//(not on all the vortices which belong to bfs tree)

//printGm;
//printPath;
sourceAchieved:=False;
currVertex:=target;
while not sourceAchieved do begin
gm[predecessors[currVertex],currVertex]:=0;
gm[currVertex,predecessors[currVertex]]:=1;
if predecessors[currVertex]=0
then sourceAchieved:=True
else currVertex:=predecessors[currVertex];
end;
//printGm;
pathExists:=True;
end else begin //if targetAchieved
resultLength:=0;
for i:=1 to N-1 do begin
resultX[resultLength+1]:=xn[i];
resultY[resultLength+1]:=yn[i];
inc(resultLength);
//check whether dog has been at interesting point
{dog has been in interesting point if matching edge exists -
and matching edge exists only in case of existence of backflow - i.e.
so - seek in quadrant where the flow flows back - i.e. left bottom corner,
go through entire column (corresponding to Bob point) and
find if any dog point exists in this column (there should be only
one point in column)}
for j:=N+1 to N+M do begin
if gm[j,i]>0 then begin
resultX[resultLength+1]:=xm[j-N];
resultY[resultLength+1]:=ym[j-N];
inc(resultLength);
end;
end; //for over all dog point in column
end; //for over all Bob points to form the resulting array
resultX[resultLength+1]:=xn[N];
resultY[resultLength+1]:=yn[N];
inc(resultLength);
//write output
if iii>1 then begin
writeln;
writeln;
end;
writeln(resultLength);
for i:=1 to resultLength do begin
if i>1 then write(' ');
write(resultX[i]);
write(' ');
write(resultY[i]);
end;
pathExists:=false;
end; //if targetAchieved
until not pathExists; //repeat until...

end; //over numberOfCases
end.
``````
Genxcop
New poster
Posts: 3
Joined: Wed Jul 26, 2006 3:58 pm

### 670 Sqrt Problem

The online judge won't recognise math.h

Is there a way to work around the distance formula which requires the square root function or will I have to program my own to work out the square root of numbers?

kwedeer
New poster
Posts: 44
Joined: Thu Dec 15, 2005 11:28 pm
simply - the only thing that You need is the result of comparison - so - try to compare the squares instead of square-roots.

btw - I have solution for the dog tasks which runs OK against tests cases given in task, but judge is giving WA, so - big please - can someone put some additional test cases for this, I have posted code in the previous thread for this tasks - so - one can even detect which judge test case produces the error and put this test case for general availability...
tuman
New poster
Posts: 24
Joined: Sat Oct 22, 2005 7:30 pm
Location: CUET
Contact:

### Input Output Requird

Hi can anybody provide some i/o for that problem.
Unfortunately there is no i/o for that problem !!!!!!!!!!!!! I m getting wrong answer and just dont know why..... so i m waiting for somebody's help. We the dreamer of the dreamy dream...
Yousuf
New poster
Posts: 13
Joined: Thu Jun 09, 2011 8:22 am

### Re: 670 - The dog task

i am getting WR in this problem.

here is my code

Code: Select all

``````
#include<iostream>
#include<stdio.h>
#include<vector>
#include<stdlib.h>
#include<algorithm>
#include<set>
#include<map>
#include<sstream>
#include<stack>
#include<queue>
#include<cmath>
#include<string.h>
#include<utility>
#include <bitset>
#include <limits>
using namespace std;

#define rep(i,  e) for( int i=0; i<(int)e; i++)
#define repr(i, s) for( int i=(int)(s-1); i>=0; i--)
#define Fr(i,s,e) for( int i=(int)s; i<=(int)e; i++)
#define fr(i,s,e) for( int i=(int)s; i>=(int)e; i--)
#define sqr( n) ( (n)*(n))
#define sz size()
#define reset(a, value) memset(a,value, sizeof(a))

struct Point{
double x, y;
} Bob,Ralph;

int N,M;
bool graph, seen;
int matchL,matchR;

double  Cal_distance(Point a, Point b)
{
return sqrt( (a.x - b.x)*(a.x - b.x) + (a.y-b.y)*(a.y-b.y) );
}

bool Bpm( int u )
{
rep(v, M) if( graph[u][v] )
{
if( seen[v] ) continue;
seen[v] = true;

if( matchR[v] <0 || Bpm( matchR[v] ) )
{
matchL[u]=v;
matchR[v]=u;
return true;
}

}
return false;
}

int main()
{
//  freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);

int t_case, cnt;
double dis1;
scanf("%d", &t_case);

rep(t, t_case)
{
scanf("%d%d", &N,&M);

rep(i, N)
{
scanf("%lf%lf", &Bob[i].x, &Bob[i].y);
}
rep(i, M)
{
scanf("%lf%lf", &Ralph[i].x, &Ralph[i].y);
}

rep(i, N-1)
{
dis1 = 2* Cal_distance( Bob[i], Bob[i+1] );
rep(j, M)
{
if( dis1 >= Cal_distance( Bob[i], Ralph[j] ) + Cal_distance( Ralph[j], Bob[i+1])  )
graph[i][j]=true;
}
}

cnt=0;
reset(matchL, -1);
reset(matchR, -1);

rep(i, N-1)
{
if( Bpm(i) ) cnt++;

reset(seen, 0);
}

printf("%d\n", N+cnt);
printf("%.0lf %.0lf", Bob.x, Bob.y);

Fr(i, 1, N-1)
{
if( matchL[i-1] != -1 )
printf("% .0lf %.0lf", Ralph[ matchL[i-1] ].x, Ralph[ matchL[i-1] ].y );

printf(" %.0lf %.0lf", Bob[i].x, Bob[i].y);
}

printf("\n");
reset(graph, 0);

}

return 0;
}

``````