## 11262 - Weird Fence

Moderator: Board moderators

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

### 11262 - Weird Fence

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

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

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
that's what I did but WA

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
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)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

### Re:

FAQ wrote: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.
Mak
Help me PLZ!!

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

### Re: 11262 - Weird Fence

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

### Re: 11262 - Weird Fence

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

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

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

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.

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

### Re: 11262 - Weird Fence

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

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

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