Taming The Herd Problem

Problems and Contests
#1

http://www.usaco.org/index.php?page=viewproblem2&cpid=809. I think I have the right idea, but for some reason, I’m only able to AC 4/10 test cases.

A brief explanation of my code:

When breakouts[i] is 1, it means that we know for sure that there was a breakout. When breakouts[i] is 2, then we know that this day could’ve been a breakout day. When breakouts[i] is 0, it means that there were no breakouts.

My code:

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

const int MOD = 1e9+7;
const int MAX_INT = 2147483647;
const int MIN_INT = -2147483647;

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

// For Rectange Geometry problems

struct Rectangle{
	int x1, y1, x2, y2;
};

int area(Rectangle r1){
	return (r1.x2 - r1.x1) * (r1.y2 - r1.y1);
}

int intersection(Rectangle b, Rectangle t){
	int horizontalLength = max(0, min(b.x2, t.x2) - max(b.x1, t.x1)); 
	int verticalLength = max(0, min(b.y2, t.y2) - max(b.y1, t.y1));
	return horizontalLength * verticalLength; 
}

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

void setIO(string name = "") { // name is nonempty for USACO file I/O
    ios_base::sync_with_stdio(0); cin.tie(0); 
    if(sz(name)){
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}

int main(){

setIO("taming"); 

int N; cin >> N;

vi a(N);

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

vector<int> breakouts(N);

For(i, 0, N){
	// index out of bounds
	if(a[i] > i){
		cout << -1 << endl; return 0;
	}
	else if(a[i] >= 0){
		// we know for sure that if a[i-a[i]] > 0, then FJ's claim's wouldnt be valid;
		if(a[i-a[i]] > 0){
			cout << -1 << endl; return 0;
		} else {
			breakouts[i] = 0;
			breakouts[i-a[i]] = 1;
		}
	} else {
		breakouts[i] = 2;
	}
	
}

breakouts[0] = 1;

int m = 0, M = 0;


int firstOne = 0, lastOne = 0;

For(i, 0, N){
	if(breakouts[i] == 1){
		lastOne = i;
	}
}

for(int i=N-1; i>=0; i--){
	if(breakouts[i] == 1){
		firstOne = i;
	}
}

For(i, 0, firstOne){
	if(breakouts[i] == 2){
		breakouts[i] = 0;
	}
}

For(i, lastOne, N){
	if(breakouts[i] == 2){
		breakouts[i] = 0;
	}
}

For(i, 0, N){
	m+=(breakouts[i] == 1);
	M+=(breakouts[i] > 0);
}

cout << m << " " << M << endl;

}
#2

You should download the test data and figure it out yourself (5.in is not very large).

1 Like