10804  Gopher Strategy
Moderator: Board moderators

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan
got AC...
Last edited by Farid Ahmadov on Tue May 10, 2005 9:23 pm, edited 1 time in total.
_____________
NO sigNature
NO sigNature
 Abednego
 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
Here are two of the cases that your program gives wrong answers for:
The correct answer is 128.685.
And here is another test case:
Code: Select all
50 50 13
930.8860 692.7770
636.9150 747.7930
238.3350 885.3860
760.4920 516.6490
641.4210 202.3620
490.0270 368.6900
520.0590 897.7630
513.9260 180.5400
383.4260 89.1720
455.7360 5.2110
595.3680 702.5670
956.4290 465.7820
21.5300 722.8620
665.1230 174.0670
703.1350 513.9290
979.8020 634.0220
723.0580 133.0690
898.1670 961.3930
18.4560 175.0110
478.0420 176.2290
377.3730 484.4210
544.9190 413.7840
898.5370 575.1980
594.3240 798.3150
664.3700 566.4130
803.5260 776.0910
268.9800 759.9560
241.8730 806.8620
999.1700 906.9960
497.2810 702.3050
420.9250 477.0840
336.3270 660.3360
126.5050 750.8460
621.7290 661.3130
925.8570 616.1240
353.8950 819.5820
100.5450 898.8140
233.3670 515.4340
990.3640 344.0430
313.7500 171.0870
426.8080 117.2760
947.1780 695.7880
393.5840 705.4030
502.6510 392.7540
612.3990 999.9320
95.0600 549.6760
993.3680 947.7390
210.0120 636.2260
698.5860 348.0940
297.5390 140.7950
480.5700 651.4340
960.3780 97.4670
66.6010 710.0970
612.9020 573.3170
570.4920 926.6520
260.7560 997.3010
560.2800 724.2860
209.4410 953.8650
429.6890 228.4440
346.6190 558.4400
744.7290 958.0310
108.1170 738.0970
905.7710 834.4810
890.6750 120.7090
698.9270 704.5670
777.8560 179.4970
872.3530 254.5860
276.9650 455.3060
964.6830 406.2190
28.6240 51.5280
332.8710 805.7320
48.8290 409.5030
530.0190 258.2700
363.3680 959.7080
486.7150 226.3400
518.1490 747.7960
700.7230 142.6180
2.2450 122.8460
493.4510 892.9210
243.5550 192.3790
597.4880 537.7640
888.2280 469.8410
792.3500 165.1930
441.5000 757.0340
87.7640 470.1240
324.9140 936.9870
275.8560 373.7430
346.4910 322.2270
148.3650 709.8590
281.9360 151.4320
452.5510 316.4370
899.2280 153.2750
975.4070 901.4740
276.1210 468.8580
794.3950 36.0290
661.2370 908.2350
573.7930 65.8180
894.4280 366.1430
231.0110 335.9280
639.5290 318.7760
And here is another test case:
Code: Select all
1 0 1
123.4 234.4
If only I had as much free time as I did in college...

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan
10804  Gopher Strategy
i have test all possible data
could you give me some more data
think you very much! i have wrong many times!!
3x
here is my code :
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
const int MaxN=110;
const double expsion=1e10;
double graph[MaxN][MaxN];
int match[MaxN];
int m,n,k;
double mx[MaxN],my[MaxN];
double nx[MaxN],ny[MaxN];
double distance[2660];
int N;
double dis(double x1,double y1,double x2,double y2)
{ return sqrt ((x1x2)*(x1x2)+(y1y2)*(y1y2)); }
int cmp (const void *a,const void *b)
{
double *t1=(double *)a;
double *t2=(double *)b;
if ((*t1)(*t2)>expsion) return 1;
if ((*t1)(*t2)<expsion) return 1;
return 0;
}
void read ()
{
int i,j;
for (i=1;i<=m;i++)
scanf ("%lf%lf",&mx,&my);
for (i=1;i<=n;i++)
scanf ("%lf%lf",&nx,&ny);
distance[0]=0;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
distance[(i1)*n+j]=dis(mx,my,nx[j],ny[j]);
qsort (distance,m*n+1,sizeof(double),cmp);
}
bool find (int i)
{
if (match) return 1;
int back[MaxN];
memset (back,0,sizeof (back));
int qn[MaxN];
int front;
int rear=1;
qn[1]=i;
int e,j,r;
for (front=1;front<=rear;front++)
{
e=qn[front];
for (j=1;j<=N;j++)
{
if (graph[e][j]<=expsion) continue;
if (match[j])
{
if (!back[j])//ejmatch[j]
{back[j]=e; back[match[j]]=j; qn[++rear]=match[j]; }
}
else
{
match[e]=j; match[j]=e;
for (r=back[e];r;r=back[back[r]])
{ match[r]=back[r]; match[back[r]]=r; }
return 0;
}
}
}
return 1;
}
int main ()
{
int c=0;
int Nn;
scanf ("%d",&Nn);
while (Nn)
{
scanf ("%d%d%d",&m,&n,&k);
read ();
printf ("Case #%d:\n",++c);
if (mk==0) { printf ("0.000\n\n"); continue; }
if (n<mk) { printf ("Too bad.\n\n"); continue; }
int i,j;
int low=1;
int high=m*n+1;
int mid;
N=m+n;
double premax=0;
double max=0;
int precount=0;
int count=0;
bool flag=false;
while (true)
{
memset (match,0,sizeof (match));
memset (graph,0,sizeof (graph));
//
mid=(low+high)/2;
if (count==mk) premax=max;
max=distance[mid];
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
if (dis(mx,my,nx[j],ny[j])max<=expsion)
graph[m+j]=graph[m+j][i]=1;
for (i=1;i<=N;i++)
if (!find(i)) i=0;
count=0;
for (i=1;i<=m;i++)
if (match[i])
count++;
if (count<mk) low=mid+1;
else if (count>=mk) high=mid1;
if (low>high) break;
}
printf ("%.3lf\n",premax);
printf ("\n");
}
return 1;
}
could you give me some more data
think you very much! i have wrong many times!!
3x
here is my code :
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
const int MaxN=110;
const double expsion=1e10;
double graph[MaxN][MaxN];
int match[MaxN];
int m,n,k;
double mx[MaxN],my[MaxN];
double nx[MaxN],ny[MaxN];
double distance[2660];
int N;
double dis(double x1,double y1,double x2,double y2)
{ return sqrt ((x1x2)*(x1x2)+(y1y2)*(y1y2)); }
int cmp (const void *a,const void *b)
{
double *t1=(double *)a;
double *t2=(double *)b;
if ((*t1)(*t2)>expsion) return 1;
if ((*t1)(*t2)<expsion) return 1;
return 0;
}
void read ()
{
int i,j;
for (i=1;i<=m;i++)
scanf ("%lf%lf",&mx,&my);
for (i=1;i<=n;i++)
scanf ("%lf%lf",&nx,&ny);
distance[0]=0;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
distance[(i1)*n+j]=dis(mx,my,nx[j],ny[j]);
qsort (distance,m*n+1,sizeof(double),cmp);
}
bool find (int i)
{
if (match) return 1;
int back[MaxN];
memset (back,0,sizeof (back));
int qn[MaxN];
int front;
int rear=1;
qn[1]=i;
int e,j,r;
for (front=1;front<=rear;front++)
{
e=qn[front];
for (j=1;j<=N;j++)
{
if (graph[e][j]<=expsion) continue;
if (match[j])
{
if (!back[j])//ejmatch[j]
{back[j]=e; back[match[j]]=j; qn[++rear]=match[j]; }
}
else
{
match[e]=j; match[j]=e;
for (r=back[e];r;r=back[back[r]])
{ match[r]=back[r]; match[back[r]]=r; }
return 0;
}
}
}
return 1;
}
int main ()
{
int c=0;
int Nn;
scanf ("%d",&Nn);
while (Nn)
{
scanf ("%d%d%d",&m,&n,&k);
read ();
printf ("Case #%d:\n",++c);
if (mk==0) { printf ("0.000\n\n"); continue; }
if (n<mk) { printf ("Too bad.\n\n"); continue; }
int i,j;
int low=1;
int high=m*n+1;
int mid;
N=m+n;
double premax=0;
double max=0;
int precount=0;
int count=0;
bool flag=false;
while (true)
{
memset (match,0,sizeof (match));
memset (graph,0,sizeof (graph));
//
mid=(low+high)/2;
if (count==mk) premax=max;
max=distance[mid];
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
if (dis(mx,my,nx[j],ny[j])max<=expsion)
graph[m+j]=graph[m+j][i]=1;
for (i=1;i<=N;i++)
if (!find(i)) i=0;
count=0;
for (i=1;i<=m;i++)
if (match[i])
count++;
if (count<mk) low=mid+1;
else if (count>=mk) high=mid1;
if (low>high) break;
}
printf ("%.3lf\n",premax);
printf ("\n");
}
return 1;
}
day up day
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: helphelp 10804Gopher StrategyWA 啊
Any word about the algorithm you are using? Why just pasting the code?
In the future please put the code into [ code ] BBCode tags (do not forget to enable the BBCode when posting) to make it more readable.
And if there is a topic on the problem your post is about, please use that topic!
anyway... your code's not working on:
My AC's output:
In the future please put the code into [ code ] BBCode tags (do not forget to enable the BBCode when posting) to make it more readable.
And if there is a topic on the problem your post is about, please use that topic!
anyway... your code's not working on:
Code: Select all
1
10 10 9
360.751 805.387
382.554 122.378
875.564 364.891
786.047 707.597
483.656 446.970
515.931 815.145
308.483 741.762
111.833 853.097
146.959 379.672
213.022 921.950
445.904 500.701
770.458 769.137
61.531 516.973
204.572 643.641
75.553 636.290
511.896 436.304
958.029 894.450
558.682 833.593
775.693 861.081
541.190 775.701
Code: Select all
Case #1:
30.187
 Abednego
 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
1. You can do binary search on the distance itself instead of an array of distances.
2. You can use a faster bipartite matching. For example,
http://shygypsy.com/tools/bpm.cpp
2. You can use a faster bipartite matching. For example,
http://shygypsy.com/tools/bpm.cpp
If only I had as much free time as I did in college...
merci bau coup
Thanks a lot,
Switching from bfs to dfs to find the augmenting path reduced the run time significantly to 2.98 seconds.
But doing the searching on distance, as opposed to array increased the run time to 4.xxx seconds.
Looking back at the contest, I see that the time limit for the contest is 3 seconds... 2.98 < 3, but it's a little too close for comfort.
How can I further reduce the run time..
for every bipartite call.. i reconstruct the graph  > O(n^2) n = 100,with high constant factor as floating point calculation is done.
Then I run a dfs for every source node ( O(nlogn) ).
Is there anything that I am doing extra.
Switching from bfs to dfs to find the augmenting path reduced the run time significantly to 2.98 seconds.
But doing the searching on distance, as opposed to array increased the run time to 4.xxx seconds.
Looking back at the contest, I see that the time limit for the contest is 3 seconds... 2.98 < 3, but it's a little too close for comfort.
How can I further reduce the run time..
for every bipartite call.. i reconstruct the graph  > O(n^2) n = 100,with high constant factor as floating point calculation is done.
Then I run a dfs for every source node ( O(nlogn) ).
Is there anything that I am doing extra.
Abednego:
Could you explain why your bpm algorithm works? The only one I know of is that based on the FordFulkerson method, which requires finding alternating paths (which is what your bpm function does) until none remains. Instead, for each vertex, you check only once for the existence of an alternating path starting at it. I don't quite understand why this suffices, as the general FordFulkerson method may find several alternating paths starting at one vertex.
Could you explain why your bpm algorithm works? The only one I know of is that based on the FordFulkerson method, which requires finding alternating paths (which is what your bpm function does) until none remains. Instead, for each vertex, you check only once for the existence of an alternating path starting at it. I don't quite understand why this suffices, as the general FordFulkerson method may find several alternating paths starting at one vertex.
Abednego's implementation is in fact FordFulkerson, it's just specialized for bipartite graphs.
And if a vertex x is matched with some vertex, it will still be matched with some (possibly another) vertex after augmentation along an alternating path. So you don't need to look for an alternating path, starting from same vertex twice.
In a bipartite matching you can't have matched edges (x,y) and (x,z) at the same time, or else it's not a matching.as the general FordFulkerson method may find several alternating paths starting at one vertex.
And if a vertex x is matched with some vertex, it will still be matched with some (possibly another) vertex after augmentation along an alternating path. So you don't need to look for an alternating path, starting from same vertex twice.

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan