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