Hoofball Bronze February 2018

Problems and Contests
#1

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.

#2

A similar idea applies to the spaces in nondecreasing order, where the ball goes right to left instead.

I think this is false.

If you have something like 1 \ 2 \ 3 \ 4 \ 5 \ 3, there’s the nondecreasing sequence from 5 to 1. If you give the ball to the cow at the right of 5, it would just pass it over the gap of size 3 to the right instead of over the non-decreasing sequence since 3 < 4.

To proceed, it’s probably useful to read this:

Now, consider some graph where a cow has an directed edge to the cow it will give the ball to. Try to solve it from there. There might be other ways to view the problem, but this way is how I would have done it.

#3

Thank you for your response.

Space:\mathbf{\ \ \ 1 \ \ \ 2 \ \ \ 3 \ \ \ 4 \ \ \ 5 \ \ \ 3}
Cow: \ \ 0 \ \ \ \ 1 \ \ \ 2 \ \ \ \ 3 \ \ \ 4 \ \ \ \ 5 \ \ \ \ 6
The non-decreasing sequence would only be until cow 4, before space 5. Then, cows 5 and 6 would be part of the next sequence. This new sequence would go left to right, so I give a ball to cow 5, and it ends up with cow 6.

I ensure I make this distinction in my code because when I see a value that disagrees with ref (ex. at cow 5, 5>3 while previously, 4<5, I set ref=0 and increment num_chain because a new chain begins at the next cow.

Note that I set num_chain=1 at the beginning because I only count breaks in the sequence, so the very first chain must also be included. I also iterate only from cows 1 to n-2, so I exclude the first and last cows. So if I break at an endpoint, there exists another cow after that endpoint to continue the chain, so it is indeed a new chain.

Interesting. I tried to depict the problem with graphs, but I wasn’t able to make progress in my notes. I didn’t see a clear way to count the number of distinct connected components without everything being too jumbled.

If you meant coding the problem with graphs, I can traverse it to find the # of connected components. However, isn’t that the idea I tried to implement, just with a number line? What’s wrong with the logic above that each monotonic chain is a distinct CC?

#4

Okay, it seems I misunderstood your idea. I’m running short on time right now because of school, but I’ll be able to respond to this later if you still have questions.

For now, I’d recommend you stress test to find small inputs that you fail on. See this:

Pretty much, you write a brute force solution or take a solution you know works (you can take the editorial solution if you want), and then you write a way to generate small test cases. Then you run your solution against the correct solution for the small cases generated and find one where it fails. Then you can debug by hand.

Good luck!

Hoofball Solution (Bronze Feb 2018)