11262 - Weird Fence

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

Moderator: Board moderators

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

11262 - Weird Fence

Post by FAQ » Tue Sep 04, 2007 7:44 am

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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

This Problem is Identical to 10804

Post by baodog » Tue Sep 04, 2007 7:46 am

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

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Tue Sep 04, 2007 3:33 pm

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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Maybe binary search issues

Post by baodog » Tue Sep 04, 2007 8:22 pm

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
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Wed Sep 05, 2007 3:18 am

that's what I did but WA :(

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Wed Sep 05, 2007 6:17 am

I found my bug :-? Misunderstood the problem statement, the word "linear distance", I thought it's Manhattan :o
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)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re:

Post by mak(cse_DU) » Wed Jun 16, 2010 2:41 pm

FAQ wrote:I found my bug :-? Misunderstood the problem statement, the word "linear distance", I thought it's Manhattan :o
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).
Mak
Help me PLZ!!

xenocratus
New poster
Posts: 2
Joined: Sat Dec 15, 2012 2:26 am

Re: 11262 - Weird Fence

Post by xenocratus » Sat Dec 15, 2012 2:39 am

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? :oops:

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11262 - Weird Fence

Post by brianfry713 » Sat Dec 15, 2012 6:55 am

Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

xenocratus
New poster
Posts: 2
Joined: Sat Dec 15, 2012 2:26 am

Re: 11262 - Weird Fence

Post by xenocratus » Sat Dec 15, 2012 4:49 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11262 - Weird Fence

Post by brianfry713 » Tue Dec 18, 2012 12:19 am

Post your updated code without using floating point if you still want help. Instead of comparing distance you can use distance squared.
Check input and AC output for thousands of problems on uDebug!

lehuyduc
New poster
Posts: 5
Joined: Tue Dec 02, 2014 6:03 pm

Re: 11262 - Weird Fence

Post by lehuyduc » Tue Dec 02, 2014 6:10 pm

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;
}
Last edited by brianfry713 on Tue Dec 02, 2014 9:32 pm, edited 1 time in total.
Reason: Added code blocks

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11262 - Weird Fence

Post by brianfry713 » Wed Dec 03, 2014 12:17 am

brianfry713 wrote:Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

lehuyduc
New poster
Posts: 5
Joined: Tue Dec 02, 2014 6:03 pm

Re: 11262 - Weird Fence

Post by lehuyduc » Wed Dec 03, 2014 9:22 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11262 - Weird Fence

Post by brianfry713 » Thu Dec 04, 2014 1:04 am

d is still type double.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 112 (11200-11299)”