10804 - Gopher Strategy

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by Farid Ahmadov » Mon May 09, 2005 12:16 pm

well, it depends on how big are distances... there is nothing about coordinates in the description of the problem... anyway tnx for reply, i'll try bsearch on distance...
_____________
NO sigNature

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

Post by Farid Ahmadov » Mon May 09, 2005 4:24 pm

bsearch on distance gives me TLE, while bsearch on array WA...
I don't understand what's the problem, algo seems to be correct and program also.
I/O please...
_____________
NO sigNature

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue May 10, 2005 12:40 am

If you post your code here, I can run it on the official data and give you some hints.
If only I had as much free time as I did in college...

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

Post by Farid Ahmadov » Tue May 10, 2005 4:09 pm

got AC...
Last edited by Farid Ahmadov on Tue May 10, 2005 9:23 pm, edited 1 time in total.
_____________
NO sigNature

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue May 10, 2005 5:25 pm

Here are two of the cases that your program gives wrong answers for:

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
The correct answer is 128.685.

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

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

Post by Farid Ahmadov » Tue May 10, 2005 9:07 pm

Thank you very much!!! As always I had only to change one thing in my program... 3 bytes :)) Thanks again... got AC 0:07.648 and I'm going to optimize it, just wanted to know what complexity does your program have?
Did you use Dijktstra or BFS for max flow?
_____________
NO sigNature

xuhuan
New poster
Posts: 1
Joined: Tue Aug 23, 2005 3:43 am
Contact:

10804 - Gopher Strategy

Post by xuhuan » Tue Aug 23, 2005 3:57 am

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=1e-10;

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 ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); }

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[(i-1)*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])//e-j-match[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 (m-k==0) { printf ("0.000\n\n"); continue; }
if (n<m-k) { 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==m-k) 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<m-k) low=mid+1;
else if (count>=m-k) high=mid-1;

if (low>high) break;

}

printf ("%.3lf\n",premax);
printf ("\n");
}

return 1;
}
day up day

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: help-help -10804--Gopher Strategy--WA &#21834;

Post by Martin Macko » Tue Aug 23, 2005 5:09 am

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:

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
My AC's output:

Code: Select all

Case #1:
30.187

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Mar 13, 2006 3:54 pm

My program took 8.xxx seconds to get AC.

I do a binary search on the sorted array of distances and then apply bipartite matching.

How can I reduce the run time?

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Mar 13, 2006 11:47 pm

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
If only I had as much free time as I did in college...

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

merci bau coup

Post by sohel » Tue Mar 14, 2006 8:55 am

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.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue Mar 14, 2006 9:18 am

I do binary search on the distance, but I don't rebuild the graph before each matching. I just use a global cutoff variable. It's 0.6 seconds.

Also, note that n is at most 50.
If only I had as much free time as I did in college...

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Tue Mar 14, 2006 2:35 pm

Abednego:
Could you explain why your bpm algorithm works? The only one I know of is that based on the Ford-Fulkerson 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 Ford-Fulkerson method may find several alternating paths starting at one vertex.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Mar 14, 2006 4:00 pm

Abednego's implementation is in fact Ford-Fulkerson, it's just specialized for bipartite graphs.
as the general Ford-Fulkerson method may find several alternating paths starting at one vertex.
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.
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.

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

Post by Farid Ahmadov » Tue Mar 14, 2006 4:46 pm

My past program in Pascal was giving AC in 7.xxx seconds, I modified my program (BFS to DFS) and wrote it in C++, got AC in 0.5 seconds :wink:
_____________
NO sigNature

Post Reply

Return to “Volume 108 (10800-10899)”