Hi all,

I am having trouble with the Ad Hoc problem Hoofball from Bronze February 2018. Here is the link to the editorial, for convenience.

If the spaces between cows are decreasing, we can give a ball to the first cow before the start of the sequence. Any ball to a cow in the sequence will pass to the right until the end of the sequence. Greedily, we want to give it to the first cow to achieve the most encounters with that single ball.

A similar idea applies to the spaces in nondecreasing order, where the ball goes right to left instead. (The spaces can be equal since we default to going left.) We would want to give a ball to the rightmost cow of this sequence, and one ball for this entire sequence would suffice.

Note that it is not possible to give fewer balls than the # of chains. Once a ball in one chain reaches the chain’s end, it cannot continue going down the chain any further. Either it reaches an endpoint (first or last cow), or it cycles between a pair of two adjacent cows. Thus, we need a distinct ball per chain of monotonic spaces.

Following is the code:

```
const int maxn=105;
int n,ar[maxn];
int sign(int a,int b){
//1: decreasing order; ball moves left-to-right
//-1: increasing order; ball moves right-to-left
if(a>b) return 1;
else return -1;
}
int main(){
setIO("hoofball");
cin >> n;
FOR(it,0,n)
cin >> ar[it];
//sort the array increasing
sort(ar,ar+n);
//count # of chains
int num_chain=1;
int ref=0; //0 -> new chain
FOR(i,1,n-1){
//before and after i
if(ref==0){
ref=sign(ar[i]-ar[i-1],ar[i+1]-ar[i]);
}
else if(sign(ar[i]-ar[i-1],ar[i+1]-ar[i])!=ref){
ref=0;
//break; start a new chain on the next step
++num_chain;
}
}
cout << num_chain << endl;
}
```

There seem to be some severe flaws with the algorithm above, since the code only passes 2 test cases. Can you please point out those flaws and explain why it doesn’t work? Also, please nudge me in the right direction and explain why one would think of such ideas in that direction.

I am eagerly looking forward to your explanations since I’ve already spent a lot of time on this problem. Thank you.