Angry Cows - Gold January 2016 Problem 1

#1

https://usaco.org/index.php?page=viewproblem2&cpid=597

#include <bits/stdc++.h>
#define int long long

using namespace std;

ifstream fin("angry.in");
ofstream fout("angry.out");

bool checkRight(int pos, int curR, vector<int> a){
    while(pos<a[a.size()-1] && curR>0){
        if(find(a.begin(),a.end(),pos+curR) != a.end()){
            pos+=curR;
        } else if(*(upper_bound(a.begin(),a.end(),pos+curR)-1)!=pos){
            pos=*(upper_bound(a.begin(),a.end(),pos+curR)-1);
        } else {
            return false;
        }
        curR--;
    }
    if(pos<a[a.size()-1]){
        return false;
    }
    return true;
}

bool checkLeft(int pos, int curR, vector<int> a){
    while(pos>a[0] && curR>0){
        if(find(a.begin(),a.end(),pos-curR) != a.end()){
            pos-=curR;
        } else if(*(upper_bound(a.begin(),a.end(),pos-curR))!=pos){
            pos=*(upper_bound(a.begin(),a.end(),pos-curR));
        } else {
            return false;
        }
        curR--;
    }
    if(pos>a[0]){
        return false;
    }
    return true;
}
// bool check(int R, vector<int> a, int p){
    
//     pos=p;
//     curR=R;
//     if(!checkLeft(pos,curR,a)){
//         return false;
//     }
//     return true;
// }

bool works(int R, vector<int> a){
    int low=a[0], high=a[a.size()-1];
    while(low<=high){
        int mid=low+(high-low)/2;
        if(!checkRight(mid,R,a) && !checkLeft(mid,R,a)){
            return false;
        }
        if(checkLeft(mid,R,a) && !checkRight(mid,R,a)){
            low=mid+1;
        } else if(!checkLeft(mid,R,a) && checkRight(mid,R,a)){
            high=mid-1;
        } else {
            return true;
        }
    }
    return false;
}

int binSearch(vector<int> a){
    int low=0, high=a[a.size()-1],ans=a[a.size()-1];
    while(low<=high){
        int mid=low+(high-low)/2;
        if(works(mid,a)){
            high=mid-1;
            ans=mid;
        } else {
            low=mid+1;
        }
    }
    return ans;
}

signed main(){
    int n; fin >> n;
    vector<int> a(n);
    for(int i=0 ; i < n ; i++){
        fin >> a[i];
    }
    sort(a.begin(),a.end());
    int x=binSearch(a);
    fout << x << ".0" << endl;
}

I got test cases 1,7,10 correct. 3,5,6,8 wrong. 2,4,9 tle.

My code is binary searching for the radius from [0,location of furthest haybale and then binary searching for each position, then seeing if those work for meeting all haybales left and right from the position. for 3/10 test cases I’m getting tle, so it might be a little slow at some places. I don’t understand why it doesn’t work. Is there a side case I need to check, or is my method wrong?

#2

Hello,

I believe your code fails on the case where it is optimal to launch a cow inbetween two positions.
For example, if there are two haybales at positions 1 and 2. It is optimal to launch a cow at position 1.5 with blast radius 0.5.

Hope that helps,
Eric Liu

#3

Hi, I tried fixing that by multiplying the haybale positions by 2 and subtracting 2 from the radius but it still shows the same result.

#4 
#include <bits/stdc++.h>
#define int long long

using namespace std;

ifstream fin("angry.in");
ofstream fout("angry.out");

bool checkRight(int pos, int curR, vector<int> a){
    while(pos<a[a.size()-1] && curR>0){
        if(find(a.begin(),a.end(),pos+curR) != a.end()){
            pos+=curR;
        } else if(*(upper_bound(a.begin(),a.end(),pos+curR)-1)!=pos){
            pos=*(upper_bound(a.begin(),a.end(),pos+curR)-1);
        } else {
            return false;
        }
        curR-=2;
    }
    if(pos<a[a.size()-1]){
        return false;
    }
    return true;
}

bool checkLeft(int pos, int curR, vector<int> a){
    while(pos>a[0] && curR>0){
        if(find(a.begin(),a.end(),pos-curR) != a.end()){
            pos-=curR;
        } else if(*(upper_bound(a.begin(),a.end(),pos-curR))!=pos){
            pos=*(upper_bound(a.begin(),a.end(),pos-curR));
        } else {
            return false;
        }
        curR-=2;
    }
    if(pos>a[0]){
        return false;
    }
    return true;
}
// bool check(int R, vector<int> a, int p){
    
//     pos=p;
//     curR=R;
//     if(!checkLeft(pos,curR,a)){
//         return false;
//     }
//     return true;
// }

bool works(int R, vector<int> a){
    int low=a[0], high=a[a.size()-1];
    while(low<=high){
        int mid=low+(high-low)/2;
        if(!checkRight(mid,R,a) && !checkLeft(mid,R,a)){
            return false;
        }
        if(checkLeft(mid,R,a) && !checkRight(mid,R,a)){
            low=mid+1;
        } else if(!checkLeft(mid,R,a) && checkRight(mid,R,a)){
            high=mid-1;
        } else {
            return true;
        }
    }
    return false;
}

int binSearch(vector<int> a){
    int low=0, high=a[a.size()-1],ans=a[a.size()-1];
    while(low<=high){
        int mid=low+(high-low)/2;
        if(works(mid,a)){
            high=mid-1;
            ans=mid;
        } else {
            low=mid+1;
        }
    }
    return ans;
}

signed main(){
    int n; fin >> n;
    vector<int> a(n);
    for(int i=0 ; i < n ; i++){
        fin >> a[i];
        a[i]*=2;
    }
    sort(a.begin(),a.end());
    int x=binSearch(a);
    fout << x/2 << ".0" << endl;
}
#5

Hello,

I believe this line is incorrect, as your code is unable to output a .5 number.
For example, if there are two haybales at positions 1 and 2. It is optimal to launch a cow at position 1.5 with blast radius 0.5.

Hope that helps,
Eric Liu

#6

i optimized your code now it’s accepted:
#include <bits/stdc++.h>
using namespace std;

const int N=2e5+10;
const ll mod=1e9+7;
int n;
vi a;
bool okl(int x,ll r)
{
while(x>a[0] && r>0)
{
if(lower_bound(all(a),x-r)!=a.end() && (lower_bound(all(a),x-r))==x-r)
{
x-=r;
}
else if((upper_bound(all(a),x-r))!=x)
{
x=(upper_bound(all(a),x-r));
}
else
{
return false;
}
r-=2;
}
if(x>a[0])
{
return false;
}
return true;
}
bool okr(int x,ll r)
{
while(x<a[n-1] && r>0)
{
if(lower_bound(all(a),x+r)!=a.end() && (lower_bound(all(a),x+r))==x+r)
{
x+=r;
}
else if((lower_bound(all(a),x+r)-1)!=x)
{
x=(lower_bound(all(a),x+r)-1);
}
else
{
return false;
}
r-=2;
}
if(x<a[n-1])
{
return false;
}
return true;
}
bool ok(ll r)
{
ll lx=0,rx=a[n-1];
while(lx<=rx)
{
ll mid=(lx+rx)/2;
bool ok1=okl(mid,r),ok2=okr(mid,r);
if(!ok1 && !ok2)
{
return false;
}
if(ok1 && ok2)
{
return true;
}
if(ok1 && !ok2)
{
lx=mid+1;
}
else if(!ok1 && ok2)
{
rx=mid-1;
}
}
return true;
}
void solve()
{
ll i=0,j=0,col=0,pol=0,sum=0,pum=0,tum=0,mx=-1e18,mn=1e18;
cin>>n;
a=vi(n);
for(i=0;i<n;i++)
{
cin>>a[i];
a[i]*=2;
}
sort(all(a));
ll l=0,r=a[n-1];
col=r;
while(l<=r)
{
ll mid=(l+r)/2;
if(ok(mid))
{
r=mid-1;
col=mid;
}
else
{
l=mid+1;
}
}
cout<<col/2;
if(col%2==1)
{
cout<<".5";
r0;
}
cout<<".0";
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int test=1;
//cin>>test;
while(test–)
{
solve();
cout<<endl;
}
}
i multiplied by 2 to handle .5 case