Hoofball Solution (Bronze Feb 2018)

Problems and Contests
#1

Continuing the discussion from Hoofball Bronze February 2018:

I will come back to the linked thread about my approach later on. However, I want to understand why the official analysis is correct. It says that the only cases FJ has to distribute a ball is:

  1. A cow is a “source” (passes the ball away but never gets a ball back);
  2. A pair of adjacent cows who pass to each other and don’t receive from anyone else.

I don’t follow why these are the only 2 cases. If these conditions are met, why must it be possible for all cows to touch the ball?

  • What happens if a cow receives a pass from 2 cows (both neighbors) and passes back to one of them?

    What about a pair that passes to each other but does not receive passes solely from its other partner?

  • Intuitively, why will every cow who receives a pass from A and passes to B \ne A always touch the ball if the “source” and “isolated pairs” are given initial balls?

  • Why is a pair of adjacent cows who receive & pass solely b/w each other the only such “isolated component”?

  • Why are cows with indegree of 0 and pairs with isolated components the only cows we have to consider?

I can’t wrap my head, intuitively, around why those categories are the only initial players who need balls. Thank you, in advance.

#2

That’s the sample case.

Because it works on the three types of cases given below:

Case 1: Two cows who pass to each other and don’t receive from anyone else. In this case, the answer is 1.

2 
3 4

Case 2: Two cows who pass to each other and receive from one end. In this case, the answer is 1 (pass to the source on the left end).

4
1 3 6 7

Case 3: Two cows who pass to each other and receive from both ends. In this case, the answer is 2 (pass to the sources on both ends).

5
7 1 3 11 4

Every bigger case is just the union of a bunch of these smaller cases.

You can see that case 1 is the only case without a “source.”

#3

Thank you, this makes sense. I understand the solution now.