Angry Cows USACO 2016

#1 
// Created by Jesse Choe - Bronze Template

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

// Type aliases

using ll = long long;
using str = string; 
using vi = vector<int>;
using pi = pair<int,int>;
using vpi = vector<pi>;
using si = set<int>;

// Vector Operations

#define sz(x) (int)(x).size()
#define pb push_back
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rev(x) reverse(all(x))
#define del(x, i) erase(begin(x)+i)
#define rem(x,i) erase(begin(x), begin(x)+i)

// Pairs

#define mp make_pair
#define sec second
#define fir first

// Sets and Maps

#define ins insert
#define ez erase
#define cnt count

// Math

#define MOD 1e9+7
#define MAX_INT 1e18*9

// Permutation

#define possibilities(x) while(next_permutation(all(x))

// Loops

#define Trav(a,x) for (auto& a: x)
#define For(i,a,b) for (int i = (a); i < (b); ++i)

// Input/Output - s is basically the file name without the ".in" and ".out"

void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

vi x;

int numberOfBalesBetween(int a, int b){
	int bales = 0;
	For(i, 0, x.size()){
		if(x[i] >= a && x[i] <= b){
			bales++;
		}
	}
	return bales;
}

int lastElementBetween(int a, int b){
	for(int i=x.size()-1; i>=0; i--){
		if(x[i] <= b){
			return x[i];
		}
	}
	return x.size()-1;
} 

int firstElementBetween(int a, int b){
	For(i, 0, x.size()){
		if(x[i] >= a){
			return x[i];
		}
	}
	return 0;
}

int hayBales(int start){

	int upper = start;
	int lower = start;
	
	for(int i=1; i<=100; i++){
		if(numberOfBalesBetween(lower, upper) == numberOfBalesBetween(lower-i, upper+i)){
			break;
		} else {
			lower = firstElementBetween(lower-i, upper+i);
			upper = lastElementBetween(lower-i, upper+i);
		}
	}
	return numberOfBalesBetween(lower, upper);
}

int main(){

setIO("angry"); 

int N; cin >> N;

For(i, 0, N){
	int a; cin >> a; 
	x.pb(a);
}

sor(x);

int ans = 0;

For(i, 0, N){
	ans = max(ans, hayBales(x[i]));
}

cout << ans << endl;

}

My code for this problem is attached above. I got 9/10 test cases :disappointed_relieved: unfortunately. I viewed the test case, but I can’t identify my error. Could you please help me?

#2

You’re not simulating the process exactly. Try stress testing against the solution given in USACO Guide if you want to find a smaller case …

#3

This thread is old so I assume either the author solved the problem by stress testing or gave up. I myself couldn’t past testcase 5 like this author. Though I haven’t studied his code carefully, the issue for me was that I was performing the left movements and right movements simultaneously inside one big while loop. This way, even if I cannot move left any further with the given radius, if the right side keeps exploding, the radius will keep increase. The left side will be checked again and again with the increasing radius (which it shouldn’t because once explosions stop on either side, it should never resume). If this is the problem the author is facing, I would suggest 2 possibilities,

  1. Use boolean values to keep track of whether there has been any further explosion on the left and right side. If not, make sure to never check that side again (using more boolean values).
  2. Just check the left and right side separately (like official solution and usaco.guide solution).

Code:

#include <bits/stdc++.h>

using namespace std;

int main(){

    freopen("angry.in", "r", stdin);

    freopen("angry.out", "w", stdout);

    long long n;

    cin >> n;

    vector <long long> arr (n);

    for (long long i=0;i<n;i++){

        cin >> arr[i];

    }

    sort(arr.begin(), arr.end());

    long long currRadius = 1;

    //bool ok = true;

    long long result =1;

    for (long long i=0;i<n;i++){

        currRadius = 1;

        /*

        if (i==1){

            cout << "";

        }

        */

        bool ok = true, moveL = true, moveR = true;

        long long l = i-1, r = i+1;

        while (ok){

            ok = false;

            long long prevL = l+1, prevR = r-1;

            bool lmoved = false, rmoved = false;

            while (moveL && l >= 0 && arr[l]>=arr[prevL]-currRadius){

                l--;

                ok = true;

                lmoved= true;

            }

            while (moveR && r <n && arr[r] <= arr[prevR]+currRadius){

                r++;

                ok = true;

                rmoved = true;

            }

            //!It can be false and can come back here and become true so no real point. 

            //*Reverse it since just easier that way. 

            if (lmoved==0){

                moveL = 0;

            }

            if (rmoved==0){

                moveR = 0;

            }

            currRadius++;

        }

        /*

        if (r-l-1==6){

            cout << "";

        }

        */

        result = max(result, r-l-1);

    }

    cout << result << endl;

}
1 Like