USACO Bronze 2016 Problem 2: Angry Cows

#1

I need help with http://www.usaco.org/index.php?page=viewproblem2&cpid=592. My code is outputting 0 right now, and I’ve tried debugging for the past hour already.

My code right now:

// 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(100);

int leftBale(int start){
	int bales = 0;
	int dist = 0;
	int iterations = 0;
	int prevBales = 0;
	while(bales < start+1){
		dist+=iterations;	
		For(i, 0, start+1){
			if(X[start] - X[i] <= dist){
				bales++;
			}
		}
		if(prevBales == bales){
			return bales;
		} else {
			prevBales = bales;
		}
		iterations++;
	}
	return 0;
}

int rightBale(int start){
	int bales = 0;
	int dist = 0;
	int iterations = 0;
	int prevBales = 0;
	while(bales < start+1){
		dist+=iterations;
		For(i, start, sz(X)){
			if(X[i] - X[start] <= dist){
				bales++;
			}
		}
		if(prevBales == bales){
			return bales;
		} else {
			prevBales = bales;
		}
		iterations++;
	}
	return 0;
}

int totBale(int start){
	return rightBale(start) + leftBale(start) - 1;
}

int main(){

//setIO("Put the name of the file here."); 

int N; cin >> N;

For(i, 0, N){
	cin >> x[i];
}

sor(x);

int ans = 0;

For(i, 0, N){
	ans = max(ans, totBale(i));
}

cout << ans << endl;

}
#3

As is, the code doesn’t even compile. :wink:

4 Likes
#4

Hello Everyone,

I had a question regarding the solution provided on the USACO Website for this problem.

Link to USACO Solution

For an input, let’s say:
4
1
2
4
6

The provided solution on USACO outputs 2. Yet, by performing the problem, you get 4. The C++ solution provided by USACOGuide outputs this as well.

I believe the solution provided by USACO is incorrect. Can anyone verify?

Thanks.

1 Like
#5

Update:

The USACO provided solution works on the test cases for the contest problem.

However, I am still not sure why the output for this input would not be 4. Both the C++ solution and using logic would warrant it being four I believe.

I would appreciate if someone could clarify.

#6

I think you’re right.

1 Like
#7

By the way, can we use the upper_bound and lower_bound functions for this problem? If so, let me know how we can do this.