670 - The dog task

[Whinii F.]

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..

Thanks in advance !

[turuthok]

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-

[Whinii F.]

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, 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]

I read data like this and get RUNTIME ERROR

plz help me!

Code: Select all

while(scanf("%d", &N) == 1)
    { 
        .....
     }

[titid_gede]

this is a multiple input problem. you should read the format of multiple input problem.

[kwedeer]

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 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]

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]

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]

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]

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]

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;
  //for breadth-first-search
  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(x2-x1)+sqr(y2-y1));
  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[i-1]:=d(xn[i-1],yn[i-1],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 (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]:=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 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]

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

[kwedeer]

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]

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.

[Yousuf]

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[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.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[0].x, Bob[0].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;
}

What is wrong in my code . anyone please help..