11262 - Weird Fence

[FAQ]

I tried this problem with binary search and matching but got tons of WAs
If you know some tricky tests, please tell me

Thanks

[baodog]

This is an identical problem to 10804,
you can try the test cases for 10804 ... just
reformat the i/o a little bit.

[FAQ]

in 10804, I got a lot of WAs too, but after fixed a precision error it worked.
This problem...no 'real/float/double' numbers so I don't know what the trick is

[baodog]

In this one make sure you take the hi in your binary
search, and use lo=mid+1, not lo=mid.
That could cause problems.
Hope this helps.

[FAQ]

that's what I did but WA

[FAQ]

I found my bug Misunderstood the problem statement, the word "linear distance", I thought it's Manhattan
Anyway, some tests for who still get WA

Code: Select all

12

2 1
5 0 red
1 2 blue

3 1
-1000 -1000 blue
0 0 blue
1000 1000 red

4 20
-1000 -1000 blue
-1000 1000 red
1000 -1000 red
1000 1000 blue

4 2
-1000 -1000 blue
-1000 1000 red
1000 -1000 red
1000 1000 blue

6 1
-3 5 red
-3 3 red
1 5 red
2 0 red
4 6 red
4 -1 blue

4 2
0 0 blue
0 1 red
1 0 red
1 1 blue

6 2
-3 5 blue
-3 3 blue
1 5 blue
2 0 blue
4 6 blue
4 -1 red

1 1 
0 0 red

6 1
-3 5 blue
-3 3 blue
1 5 blue
2 0 blue
4 6 blue
4 -1 red

6 2
-3 5 blue
-3 3 red
1 5 blue
2 0 red
4 6 blue
4 -1 red

6 4
-3 5 blue
-3 3 red
1 5 blue
2 0 red
4 6 blue
4 -1 red

1 1
2 2 blue

Code: Select all

5
1415
Impossible
2000
3
1
Impossible
Impossible
3
6
Impossible
Impossible

[mak(cse_DU)]

I found my bug Misunderstood the problem statement, the word "linear distance", I thought it's Manhattan
Anyway, some tests for who still get WA

Code: Select all

12

2 1
5 0 red
1 2 blue

3 1
-1000 -1000 blue
0 0 blue
1000 1000 red

4 20
-1000 -1000 blue
-1000 1000 red
1000 -1000 red
1000 1000 blue

4 2
-1000 -1000 blue
-1000 1000 red
1000 -1000 red
1000 1000 blue

6 1
-3 5 red
-3 3 red
1 5 red
2 0 red
4 6 red
4 -1 blue

4 2
0 0 blue
0 1 red
1 0 red
1 1 blue

6 2
-3 5 blue
-3 3 blue
1 5 blue
2 0 blue
4 6 blue
4 -1 red

1 1 
0 0 red

6 1
-3 5 blue
-3 3 blue
1 5 blue
2 0 blue
4 6 blue
4 -1 red

6 2
-3 5 blue
-3 3 red
1 5 blue
2 0 red
4 6 blue
4 -1 red

6 4
-3 5 blue
-3 3 red
1 5 blue
2 0 red
4 6 blue
4 -1 red

1 1
2 2 blue

Code: Select all

5
1415
Impossible
2000
3
1
Impossible
Impossible
3
6
Impossible
Impossible

I made a stupid code. But above output matched.
I forgot to partition the pole with one color in left side and other color in right side.
Your Outpurs were right(AC).

[xenocratus]

Hello, I have tried in a number of ways to solve this problem [improving each algorithm to the cases it didn't cover before], but i came to a stand-still; can't find what's not quite right with it. can anyone help or provide a failing test for me, please?

Code: Select all

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <vector>
using namespace std;
//fstream fin("weird_fence.in",ios::in);
int v[101][101],i,j,l,n,p,k,ch[2][101];
vector<int> xr,yr,xb,yb;
bool chk(int mid){    //function checking if there are more than k possible fences built with chains of length mid
	for(int i=0;i<=p;i++)ch[0][i]=ch[1][i]=0;  //emptying ch which keeps the number of possible fences starting from a pole
	for(int i=0;i<xr.size();i++)
		for(int j=0;j<xb.size();j++)
			if(v[i][j]<=mid){     //detecting how many
				ch[0][i]++;		//ch[0] keeps the number of possibilities for red poles
				ch[1][j]++;		//ch[1] keeps the same number for blue poles
			}

	int sm2=0,sw=1;
	while(sw==1){//as far as i still have some possibilities of tying things up
		sw=0; int mx=0,poz=0;
		for(int i=0;i<=p;i++){		//determining the maximum number of possibilities in one pole and its position
			if(ch[0][i]>mx){mx=ch[0][i];poz=i;sw=1;}
			if(ch[1][i]>mx){mx=ch[1][i];poz=i;sw=1;}
		}
		//i then check to see if the maximum is reached between red or blue poles
		//i cut one possibility from each pole of the other colour that is close enough
		//and i keep track of the one who has the smallest number of possibilities
		//the maximum possibility pole and the minimum possibility neighbour of it are then removed
		//for each removal i increase sm2 and test for sm2>=k
		if(ch[0][poz]==mx&&sw==1){
			int mn=101,poz2=poz;
			for(int j=0;j<xb.size();j++){
				if(v[poz][j]<=mid){ch[1][j]--;
					if(mn>ch[1][j]){mn=ch[1][j]; poz2=j;}
				}
			}
			ch[1][poz2]*=0;
			ch[0][poz]*=0;
			sm2++;
		}
		else if(ch[1][poz]==mx&&sw==1) {
			int mn=101,poz2=poz;
			for(int j=0;j<xr.size();j++){
				if(v[j][poz]<=mid){ch[0][j]--;
					if(mn>ch[0][j]){mn=ch[0][j]; poz2=j;}
				}
			}
			ch[0][poz2]*=0;
			ch[1][poz]*=0;
			sm2++;
		}
	}
	if(sm2>=k) return true;
	return false;
}
int main() {
	cin>>n;
	for(l=1;l<=n;l++){
		cin>>p>>k; int x,y; char c[5];
		xr.clear();
		yr.clear();
		xb.clear();
		yb.clear();
		for(i=1;i<=p;i++){
			cin>>x>>y>>c;
			if(strcmp(c,"blue")==0){ //creating coordinates vectors
				xb.push_back(x);
				yb.push_back(y);
			}
			else {
				xr.push_back(x);
				yr.push_back(y);
			}
		}
		if(k>xb.size()||k>xr.size()){printf("Impossible\n"); continue;} //testing for impossible case
		int mx=0;
		for(i=0;i<xr.size();i++)
			for(j=0;j<xb.size();j++){
				double dst=sqrt((xb[j]-xr[i])*(xb[j]-xr[i])+(yb[j]-yr[i])*(yb[j]-yr[i])); //creating distance matrix
				v[i][j]=ceil(dst);
				if(mx<v[i][j])mx=v[i][j];   //extracting maximum for later use in binary search
				}
		int st=1,dr=mx,mij=(st+dr)/2;
		while(st<dr){		//binary search
			if(chk(mij))dr=mij;
			else st=mij+1;
			mij=(st+dr)/2;
		}
		printf("%d\n",mij);    //output

	}
	return 0;
}

[brianfry713]

Try solving it without using floating point.

[xenocratus]

I changed the distance calculation part to a binary search but still WA. I'm more concerned about my approach in checking if a chain length of "mid" would yield a good result (number of possible simultaneous fences >= k); i'm trying to eliminate the pole which has the most ways of combining with another pole and its neighbour with the smallest number of such combinations. I can't prove that this method will work (not sure that it delivers a good result, it's more of a feeling that this should be a good way of checking), but can't find failing examples either.

[brianfry713]

Post your updated code without using floating point if you still want help. Instead of comparing distance you can use distance squared.

[lehuyduc]

Can someone check my code for me ? I can't find the mistake
I binary search the answer then perform maximal matching.
Thanks in advance.

Code: Select all

/*
ID: lehuydu1
PROG:
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define xx first.first
#define xy first.second
#define yx second.first
#define yy second.second
#define cint const int
typedef long long ll;
typedef double rl;
typedef pair<int,int> pt;
typedef pair<int,pt> pt3;
typedef pair<pt,pt> pt4;
int dx[5]={0,0,0,1,-1},
    dy[5]={0,1,-1,0,0};
const int base = 1000000007;

int n,m,res=0,K,sink,source;
vector <int> a[202];
int c[202][202], f[202][202]; // capacity and flow
int trace[202];
vector <pt> b1,b2;
rl d[202][202];
queue <int> q;

rl sqr(int a) {return rl(a*a);}
rl dist(pt a,pt b)
{
    return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}

bool find_flow()
{
    int i,j,k,u,v;
    while (!q.empty()) q.pop();
    for (i=1;i<=n+m+1;i++) trace[i] = 0; trace[0] = -1;
    q.push(0);

    while (!q.empty())
    {
        u = q.front(); q.pop();
        for (i=0;i<a[u].size();i++)
        {
            v = a[u][i];
            if (f[u][v] < c[u][v] && !trace[v])
            {
                trace[v] = u;
                if (v==sink) return true;
                q.push(v);
            }
        }
    }
    return false;
}

void augment_path()
{
    int i,u,v,delta=base;
    for (v=sink;(u=trace[v])!=-1;v=u) delta = min(delta,c[u][v]-f[u][v]);
    for (v=sink;(u=trace[v])!=-1;v=u)
    {
        f[u][v] += delta;
        f[v][u] -= delta;
    }
}

int max_flow()
{
    int i,j=0;
    for (i=0;i<a[0].size();i++) j += f[0][a[0][i]];
    return j;
}

void solve()
{
    int i,j,k,u,v,l,r,x;
    string s;
    b1.clear(); b1.push_back(pt(0,0)); // vector of red points
    b2.clear(); b2.push_back(pt(0,0)); // vector of blue points

    cin >> n >> K; source = 0; sink = n+1;
    for (i=0;i<=n;i++) a[i].clear();
    for (i=1;i<=n;i++)
    {
        cin >> j >> k >> s;
        if (s=="red") b1.push_back(pt(j,k));
        else b2.push_back(pt(j,k));
    }

    n = b1.size()-1; m = b2.size()-1;
    // add edge with capacity = 1 from source to all red points
    for (i=1;i<=n;i++) {a[0].push_back(i); c[0][i] = 1;}
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++) d[i][j] = dist(b1[i],b2[j]);
    // add edge with capacity = 1 from blue points to sink
    for (i=1;i<=m;i++) {a[i+n].push_back(sink); c[i+n][sink] = 1;}

    res = base;
    l = 0; r = 10000;
    while (l<=r)
    {
        x = (l+r)/2;
        for (i=1;i<=n;i++) a[i].clear();

        for (i=0;i<=sink;i++)
            for (j=0;j<=sink;j++) f[i][j] = 0;

        // add edge between points that have distance <= x
        for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (d[i][j] <= x) {a[i].push_back(j+n);c[i][j+n] = 1;}
            else c[i][j+n] = 0;

        while (find_flow()) augment_path();
        if (max_flow() >= K) {res = x; r=x-1;} else l=x+1;
    }

    if (res==base) cout << "Impossible\n";else cout << res << "\n";
}

int main()
{
    int i,j,t;
   // freopen("uva11262.inp","r",stdin);

    cin >> t;
    for (i=1;i<=t;i++) solve();
    return 0;
}

[brianfry713]

Try solving it without using floating point.

[lehuyduc]

Code: Select all

/*
ID: lehuydu1
PROG:
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define xx first.first
#define xy first.second
#define yx second.first
#define yy second.second
#define cint const int
typedef long long ll;
typedef double rl;
typedef pair<int,int> pt;
typedef pair<int,pt> pt3;
typedef pair<pt,pt> pt4;
int dx[5]={0,0,0,1,-1},
    dy[5]={0,1,-1,0,0};
const int base = 1000000007;

int n,m,res=0,K,sink,source;
vector <int> a[202];
int c[202][202], f[202][202]; // capacity and flow
int trace[202];
vector <pt> b1,b2;
rl d[202][202];
queue <int> q;

int sqr(int a) {return a*a;}
int dist(pt a,pt b)
{
    return sqr(a.x-b.x)+sqr(a.y-b.y);
}

bool find_flow()
{
    int i,j,k,u,v;
    while (!q.empty()) q.pop();
    for (i=1;i<=n+m+1;i++) trace[i] = 0; trace[0] = -1;
    q.push(0);

    while (!q.empty())
    {
        u = q.front(); q.pop();
        for (i=0;i<a[u].size();i++)
        {
            v = a[u][i];
            if (f[u][v] < c[u][v] && !trace[v])
            {
                trace[v] = u;
                if (v==sink) return true;
                q.push(v);
            }
        }
    }
    return false;
}

void augment_path()
{
    int i,u,v,delta=base;
    for (v=sink;(u=trace[v])!=-1;v=u) delta = min(delta,c[u][v]-f[u][v]);
    for (v=sink;(u=trace[v])!=-1;v=u)
    {
        f[u][v] += delta;
        f[v][u] -= delta;
    }
}

int max_flow()
{
    int i,j=0;
    for (i=0;i<a[0].size();i++) j += f[0][a[0][i]];
    return j;
}

void solve()
{
    int i,j,k,u,v,l,r,x;
    string s;
    b1.clear(); b1.push_back(pt(0,0)); // vector of red points
    b2.clear(); b2.push_back(pt(0,0)); // vector of blue points

    cin >> n >> K; source = 0; sink = n+1;
    for (i=0;i<=n;i++) a[i].clear();
    for (i=1;i<=n;i++)
    {
        cin >> j >> k >> s;
        if (s=="red") b1.push_back(pt(j,k));
        else b2.push_back(pt(j,k));
    }

    n = b1.size()-1; m = b2.size()-1;
    // add edge with capacity = 1 from source to all red points
    for (i=1;i<=n;i++) {a[0].push_back(i); c[0][i] = 1;}
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++) d[i][j] = dist(b1[i],b2[j]);
    // add edge with capacity = 1 from blue points to sink
    for (i=1;i<=m;i++) {a[i+n].push_back(sink); c[i+n][sink] = 1;}

    res = base;
    l = 0; r = 10000;
    while (l<=r)
    {
        x = (l+r)/2;
        for (i=1;i<=n;i++) a[i].clear();

        for (i=0;i<=sink;i++)
            for (j=0;j<=sink;j++) f[i][j] = 0;

        // add edge between points that have distance <= x
        for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (d[i][j] <= x*x) {a[i].push_back(j+n);c[i][j+n] = 1;}
            else c[i][j+n] = 0;

        while (find_flow()) augment_path();
        if (max_flow() >= K) {res = x; r=x-1;} else l=x+1;
    }

    if (res==base) cout << "Impossible\n";else cout << res << "\n";
}

int main()
{
    int i,j,t;
   // freopen("uva11262.inp","r",stdin);

    cin >> t;
    for (i=1;i<=t;i++) solve();
    return 0;
}

I tried to use square distance but it still gives WA. Could you find some tricky test cases ? Thanks again

[brianfry713]

d is still type double.