USACO's US Open contest is now live at http://www.usaco.org/ through April 8. As USACO's signature end of season contest, playing a significant role in finalist selection, you will have 5 hours from when you start to solve 3 or 4 problems.

Good luck and enjoy the problems!

-Mark

Is it just for gold competetors?

It's open to all.

Interesting Gold problems this time!

Bronze was interesting, but the problems were rather mean...

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.

I used a similar method to do Bovine Ballet. Took me quite a while to code and debug. I agree with you that this problem should have a shorter solution, as most USACO problems do.

I can't believe those problems was for Silver. Silver's problems was really easy. Hope to get full mark. :D

how can I ask for clarification ?

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

Email: bcdean@clemson.edu

not useful, because one will not receive the answer before the time end

I had received an answer before time ended once (there was corrupted html in one task)

the first problem in the silver division was so ambiguous.i didn't know whether it's possible to catch the other captain while we are still falling or not...

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 bcdean@clemson.edu

What is the memory limits for problems from Gold?

"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. " :)

Could I ask questions about tasks now? If I can, how to solve A,B,C Gold :)

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 came up with that solution to Photo, but I didn't do it because there's no way it'll work, even with intermediate cases of N = 15000~20000. Let alone for N = 200000...

Even if you compute the ranges efficiently and you code it so that the constant factors are low, you will still have an O(N^2) algorithm for a problem where N <= 200.000.

You can calculate the ranges, with O(N) precomputation, in O(1). Computing the maximum valued state in that range can be done in O(log N) (a Fenwick tree suffices). Overall the algorithm is O(N log N).

And you can solve the whole problem in O(N) time if you use just the right data structures.

I think you can also implement the dp without range query structures if you relax the state to just be a prefix of the cows (not requiring a cow to be placed right at the end). You can then just track the set of intervals containing your current position, querying it for the earliest starting point when you try placing a cow at your current position.

http://pastebin.com/Pr7hYj2S

I haven't really tested this, but it seems to work, and seems somewhat simpler to implement if you have access to heap or BST, such as that from the STL.

What about MLE in Figure Eight? N^3 is too much more than 64 MB

Yin and Yang can be solved in

O(NlogN) without any data structures. We can use divide-and-conquer technique on a tree and on each iteration we only need to run DFS several times.I'm wondering how to detect negative cycles with Dijkstra algorithm quickly. I used some heuristics to do this, but the main one is to output "-1" if the program is already running for 1.8 seconds. Are there any test cases against this?

Empirically I've found that reporting -1 when a vertex gets popped more than twice is sufficient. I don't have a proof, however.

Could you give more details about your Yin and Yang solution?

Edit: Wow, I answered something completely different then what you asked, sorry. I'll have more details in the editorial.

The solution is based on the dual form of the shortest path linear program.

See http://en.wikipedia.org/wiki/Shortest_path_problem#Linear_programming_formulation

Still, since there are negative edges, it's not obvious that Dijkstra's applies (and I don't have any proof of its efficiency, sorry).

Suppose that our tree is rooted and we are only interested in those balanced paths which contain the root. In this case we can solve a problem with DFS that counts the number of paths starting from the root with each possible balance between 0-edges and 1-edges. Note that we need to store these values for each subtree of the root separately. After that it's quite obvious how to calculate the total number of balanced paths passing through the root.

We can solve the initial problem in the following way. Let's fix some node and call it a root. After counting all balanced paths passing through it we can remove this node from the tree and calculate the answer for each remaining connected component separately. This is where divide-and-conquer approach comes into play. However, we can't simply choose an arbitrary node as a root, because the tree can be split into uneven connected components after its removal. One can prove that there always exists a node that at least halves the size of the largest connected component remaining after its removal.

The overall complexity is

O(NlogN), because we haveO(logN) levels of recursion and on each of them we performO(N) operations.It would be interesting if you shared the Dijkstra's solution for photo...

Hi, do you have some link/reference where I could learn more about the merging of the data structures (balanced trees?) fast in a "heavy light" fashion? (merging the smaller structure into the larger). I once faced it here in this problem: Safe Travel and I could not understand much the details about it (because the editorial didn't explain much how to do it and how to reach the right final complexity). Thank you!

If the contest is over. can anyone give any ideas on Silver division 3rd task (Luxury River Cruise) ?

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 :

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 :

Total complexity O (NM + log(K))

K<=1000000000 ...

UPD: ok, thanks for explanation. Did you solve 2?

Nope, you?

Yes, I've used dynamic programming to solve it, I didn't prove that my solution is right, but it works for the sample case.

On each station I fill the tank up to G units of fuel, for example, for the sample case, on the first station we will have 1 unit of fuel, and we can buy 9 units of fuel to fill the tank, the cost will be 9*40=360. then, for the next station, we see that the cost is lower, and we could buy less fuel on the previous station, we needed fuel only to reach the current station. so, we could buy only 2 units of fuel to reach the second station, cost=cost-7*40; cost= 80. then we fill the tank in the second station and so on. I would appreciate if someone suggested a case where my solution fails.

What if your capacity is 10, you start with 5 units and the destination is at distance 16. The prices and positions of the stations are as follows...

80 5

100 7

60 10

If I understood correctly, your program would fill the tank in every station, when actually the optimal solution is to get 5 units from station 1 and 6 units from station 3 for a total cost of 80*5 + 60*6 = 760.

yes, my solution failed :/

Did anyone solve it correctly?

This was a DP problem. Note that the minimum to reach a certain location would result in that location having 0 gallons left that way we don't use any extra payment. So the min[i] = min[i — 1] + distanceAtMinimumCost(i, i — 1). Now the trouble is Distance at Minimum cost. So we notice that our tank can only hold D gallons so we only have to search the stations within D of the i — 1 th station and take out gallons at minimum cost keeping a deltas array to keep track of how much we can take out from each station. You can keep a dummy station for your start location and end location.

I forgot to use a 64-bit int :(

Hmm. I dunno. I used a greedy solution, but after thinking over it, neither me or my friend(who is in gold), found a counterexample. There may be one. Basically, you look at all the gas stations within range. If the price of the gas there is less than the price of the gas at your current station, you fill up just enough to reach that station. However, if none of the gas stations within range has a price less than your current gas station, you fill your tank up to full and drive to the gas station with the lowest price within range.

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 thej_{th}simulation. Then, ifNode[x] is the node we end up on thex_{th}simulation, our answer will beNode[j+ (K-i)mod(i-j)].Complexity:

Bronze power <3

Seriously you guys need to be more bronze.

Do you know when results will come out?

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

Results are out: 2013 US Open Results. Congrats to those who did well.

In silver division problem fuel:I saw the test cases and i think some of them weren't logical.because Farmer John starting fuel was more than his truck can hold.

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

Thanks for fixing it.