It's open to all.

How did you do Bovine Ballet? I used a bunch of casework to do it, but I don't feel as though that was the best solution since it took way too long to code and it didn't seem characteristic of USACO to have such a solution for a problem.

You can email Brian Dean, the contest administrator, for clarification requests.

Email: [email protected]

I have the same problem!

Please don't discuss the problems while the contest is still running. If you have a clarification request you can email the contest administrator, Brian Dean, at [email protected]

"Your program must be less than 1,000,000 bytes in size and must compile in 30 seconds or less. Unless otherwise stated, your programs will be limited to about 64MB of total memory use. " :)

Yep :) We're working on analysis but I'll give you a brief overview of the solutions. (and of course, anyone else can write about their own solution)

Figure Eight

The implementation of this problem is a bit tricky. Basically you try all O(N^3) possibilities for the middle line of the eight (connecting the top and bottom loops) and use some clever accounting so you can find the maximum area bottom and top loop coming from it.

Yin and Yang

For each subtree you maintain two data structures that indicate the number of nodes that have a given difference of cow types on the path to the root of the subtree. One data structure counts this for nodes with no intermediate nodes with equal types and the other counts nodes that do. To make this efficient merging results from subtrees should be done in a "heavy light" fashion; merging the smaller structure into the larger.

Photo

Believe it or not this problem can be solved with Dijkstra's. However that's not the intended solution. Instead you formulate an O(N^2) DP where the state is where the last spotted cow was located. The maximum extent of ranges that start before this cow give the earliest you could place the next cow. The minimum extent of ranges that start after this cow give you the latest you could place the next cow. To make this all efficient you need to quickly compute the ends of this range and then quickly compute the maximum valued state in this range. (or if the range is empty a cow cannot be placed here).

I've solved it this way: Let's precalculate for each vertex v — go[v] = u, where u is the vertex, where we finish our route, if we start to simulate M steps from v. Now we can solve the problem in O (K) time this way :

v = 1

while (k--)
{
    v = go[v];
}

print (v)

But for k <= 10 ^ 9 it will be too slow. Now we can precalculate next[v][i] = u, where u is the vertex, where we finish our route, if we start to similate M steps from v for 2 ^ i times. Now we can just find all the '1' bits in binary representaion of K and for each bit do this way :

v = 1

for each bit '1' in K :
    v = next[v][deg[i]], where deg[i], is degree of 2 of i'th bit in K

print (v)

Total complexity O (NM + log(K))

I came up with a different solution, which should be able to run within the time limit of 2 seconds, I believe...

The solution is to simulate the moves, until either all K moves have been simulated or we end up at a node we've ended up before. Let's say we're on the i_th simulation and we end up at the same node we ended up on the j_th simulation. Then, if Node[x] is the node we end up on the x_th simulation, our answer will be

Node[j + (K - i) mod (i - j)].

Complexity:

usaco needs some time, please give him some time and you will get the result

That issue has been fixed. My apologies about that :-(.