# Taming The Herd Problem

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 = 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;

}
``````

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

1 Like