msg555's blog

By msg555, 7 years ago, ,

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

• +42

 » 7 years ago, # |   0 Is it just for gold competetors?
•  » » 7 years ago, # ^ |   +14 It's open to all.
 » 7 years ago, # |   +6 Interesting Gold problems this time!
 » 7 years ago, # |   0 Bronze was interesting, but the problems were rather mean...
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   0 I can't believe those problems was for Silver. Silver's problems was really easy. Hope to get full mark. :D
 » 7 years ago, # |   +3 how can I ask for clarification ?
•  » » 7 years ago, # ^ |   0 You can email Brian Dean, the contest administrator, for clarification requests.Email: bcdean@clemson.edu
•  » » » 7 years ago, # ^ |   +6 not useful, because one will not receive the answer before the time end
•  » » » » 7 years ago, # ^ |   +2 I had received an answer before time ended once (there was corrupted html in one task)
 » 7 years ago, # |   -16 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...
•  » » 7 years ago, # ^ |   0 I have the same problem!
•  » » 7 years ago, # ^ |   +22 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
 » 7 years ago, # |   0 What is the memory limits for problems from Gold?
•  » » 7 years ago, # ^ |   +11 "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. " :)
 » 7 years ago, # |   +3 Could I ask questions about tasks now? If I can, how to solve A,B,C Gold :)
•  » » 7 years ago, # ^ | ← Rev. 2 →   +11 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 EightThe 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 YangFor 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.PhotoBelieve 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).
•  » » » 7 years ago, # ^ |   0 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.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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).
•  » » » » » 7 years ago, # ^ |   0 And you can solve the whole problem in O(N) time if you use just the right data structures.
•  » » » » » » 7 years ago, # ^ |   0 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/Pr7hYj2SI 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.
•  » » » 7 years ago, # ^ |   +6 What about MLE in Figure Eight? N^3 is too much more than 64 MB
•  » » » 7 years ago, # ^ |   +16 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?
•  » » » » 7 years ago, # ^ |   0 Empirically I've found that reporting -1 when a vertex gets popped more than twice is sufficient. I don't have a proof, however.
•  » » » » 7 years ago, # ^ |   0 Could you give more details about your Yin and Yang solution?
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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.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).
•  » » » » » 7 years ago, # ^ |   +10 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 have O(logN) levels of recursion and on each of them we perform O(N) operations.
•  » » » 7 years ago, # ^ |   0 It would be interesting if you shared the Dijkstra's solution for photo...
•  » » » 7 years ago, # ^ |   0 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!
 » 7 years ago, # |   0 If the contest is over. can anyone give any ideas on Silver division 3rd task (Luxury River Cruise) ?
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 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))
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 K<=1000000000 ...UPD: ok, thanks for explanation. Did you solve 2?
•  » » » » 7 years ago, # ^ |   0 Nope, you?
•  » » » » » 7 years ago, # ^ |   0 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.
•  » » » » » » 7 years ago, # ^ | ← Rev. 4 →   0 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 5100 760 10If 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.
•  » » » » » » » 7 years ago, # ^ |   0 yes, my solution failed :/
•  » » » » » » » » 7 years ago, # ^ |   0 Did anyone solve it correctly?
•  » » » » » » » » » 7 years ago, # ^ | ← Rev. 4 →   0 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 :(
•  » » » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 7 years ago, # ^ | ← Rev. 11 →   0 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 ith simulation and we end up at the same node we ended up on the jth simulation. Then, if Node[x] is the node we end up on the xth simulation, our answer will beNode[j + (K - i) mod (i - j)].Complexity:
 » 7 years ago, # |   0 Bronze power <3Seriously you guys need to be more bronze.
 » 7 years ago, # |   0 Do you know when results will come out?
•  » » 7 years ago, # ^ |   +16 usaco needs some time, please give him some time and you will get the result
 » 7 years ago, # |   +6 Results are out: 2013 US Open Results. Congrats to those who did well.
 » 7 years ago, # |   +6 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.
•  » » 7 years ago, # ^ |   +8 That issue has been fixed. My apologies about that :-(.
•  » » » 7 years ago, # ^ |   +5 Thanks for fixing it.