670  The dog task
Moderator: Board moderators

 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 EdmondsKarp 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..
Thanks in advance !
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 EdmondsKarp 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..
Thanks in advance !
Last edited by Whinii F. on Sat Mar 01, 2003 12:02 am, edited 1 time in total.

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
I assumed you reduced this problem to a bipartitematching problem ... I added 2 nodes (source and sink) whose maxflow will be calculated, ... leftpartition is the mainroute (Bob's route), and rightpartition is the interestingpoints ...
I solved this using max. cardinality bipartitematching exactly the same logic you described, except that I used FordFulkerson ... 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 multipleinput format and specialcorrection. 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 floatingpoint here but I couldn't. I squared both sides of equation and tried to do as much integer operation first before I introduced the floatingpoint stuff.
turuthok
I solved this using max. cardinality bipartitematching exactly the same logic you described, except that I used FordFulkerson ... 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 multipleinput format and specialcorrection. 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 floatingpoint here but I couldn't. I squared both sides of equation and tried to do as much integer operation first before I introduced the floatingpoint stuff.
turuthok
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

 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.
Anyway, thanks for your sincere reply!!
p.s. As far as I know, EdmondsKarp IS FordFulkerson, since FF is a method and not an algorithm. EK is a BFSaugmentingpathfinding version of Ford Fulkerson.
Have a good day!!
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.
Anyway, thanks for your sincere reply!!
p.s. As far as I know, EdmondsKarp IS FordFulkerson, since FF is a method and not an algorithm. EK is a BFSaugmentingpathfinding version of Ford Fulkerson.
Have a good day!!
670 :(
I read data like this and get RUNTIME ERROR
plz help me!
plz help me!
Code: Select all
while(scanf("%d", &N) == 1)
{
.....
}

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
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?
Please  give some explanation...
I have found in Internet other algorithms  e.g. alternating path algorithm  seems to be simple  but no idea what to do with evenlength 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!
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?
Please  give some explanation...
I have found in Internet other algorithms  e.g. alternating path algorithm  seems to be simple  but no idea what to do with evenlength 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!
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 onetoone 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
There's a good description of augmentingpaths method for bipartite matching (without network flows) here: http://www.ecp6.jussieu.fr/pageperso/bo ... apter5.pdf
OMG  so  there can more more than one matchings with the maximum cardinality and  those matching can be determined by completely different sequences (somehow nonintersecting) 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....
only hope, that judge will reckognize any of valid matchings....
That's so obvious... for example in a graph with edges (A, B1), (A, B2), a maximumcardinality matching consists of a single edge, any of the two.OMG  so  there can more more than one matchings with the maximum cardinality
Problem 670 has a special judge (it's marked with a yellow sign), so any correct output should be accepted.only hope, that judge will reckognize any of valid matchings....
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) breadthfirst 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!
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) breadthfirst 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 (lefthandside)
//M  interesting places (righthandside)
i,j,iii: Integer;
target: Integer;
pathExists: boolean;
targetAchieved, targetDecided: boolean;
//for breadthfirstsearch
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;
head,freeSlot: Integer;
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
inc(head);
dec(queueLength);
end;
function queueHead: Integer;
begin
if queueLength>0
then Result:=queue[head]
else Result:=1;
end;
procedure initialiseQueue;
begin
head:=0;
freeSlot:=0;
queueLength:=0;
end;
function d(x1,y1,x2,y2: Integer): double;
begin
Result:=sqrt(sqr(x2x1)+sqr(y2y1));
end;
begin
{
AssignFile(Input, 'in06__.txt');
Reset(Input);
AssignFile(Output, 'out06__.txt');
Rewrite(Output);
}
read(numberOfCases);
for iii:=1 to numberOfCases do begin
readln;
readln;
read(N);
read(M);
readln;
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;
//reading data
for i:=1 to N do begin
read(xn[i]);
read(yn[i]);
if i>1 then begin
db1b2[i1]:=d(xn[i1],yn[i1],xn[i],yn[i]);
end;
end; //for  reading Bob's route
readln;
for i:=1 to M do begin
read(xm[i]);
read(ym[i]);
for j:=1 to (N1) 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]:=0;
predecessors[0]:=0;
enqueue(0);
targetAchieved:=false;
targetDecided:=false;
for i:=1 to target do
color[i]:=1;
color[0]:=2;
while ((not targetAchieved) and (not targetDecided)) do begin
//the search is done if no more vortices are in queue
u:=queueHead;
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
//read the result
resultLength:=0;
for i:=1 to N1 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[jN];
resultY[resultLength+1]:=ym[jN];
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.
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?
thanx in advance
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?
thanx in advance
simply  the only thing that You need is the result of comparison  so  try to compare the squares instead of squareroots.
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...
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...
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.
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...
Re: 670  The dog task
i am getting WR in this problem.
here is my code
What is wrong in my code . anyone please help..
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)(s1); 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[101],Ralph[101];
int N,M;
bool graph[101][101], seen[101];
int matchL[101],matchR[101];
double Cal_distance(Point a, Point b)
{
return sqrt( (a.x  b.x)*(a.x  b.x) + (a.yb.y)*(a.yb.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, N1)
{
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, N1)
{
if( Bpm(i) ) cnt++;
reset(seen, 0);
}
printf("%d\n", N+cnt);
printf("%.0lf %.0lf", Bob[0].x, Bob[0].y);
Fr(i, 1, N1)
{
if( matchL[i1] != 1 )
printf("% .0lf %.0lf", Ralph[ matchL[i1] ].x, Ralph[ matchL[i1] ].y );
printf(" %.0lf %.0lf", Bob[i].x, Bob[i].y);
}
printf("\n");
reset(graph, 0);
}
return 0;
}