### phantom11's blog

By phantom11, 7 years ago, ,

This is to remind you that the USACO December 2012 Contest is going to take place from tomorrow.The duration of the contest is 4 days.You can appear in the maximum of any of the 4 hour window during the contest.

Link to Contest Page .(to be updated before the contest starts )

You can use this blog space to discuss problems NOT during the contest but ONLY after the contest is complete.

UPD -> [Results]

• +27

 » 7 years ago, # |   +2 this is the link actually:http://usaco.org/index.php?page=viewcontest
 » 7 years ago, # |   +16 It's time to help FJ with his cows :)
•  » » 7 years ago, # ^ |   +6 :)
 » 7 years ago, # | ← Rev. 3 →   -13 I am getting WA on sample case, the output is 57.5 and I am printing 57.500000. The Sample case is unique or they are testing with another sample case? Thanks. **Ok, I solved it.** **Can anybody please tell me why I got WA printing 57.500000 when answer is 57.5? I understand negative votes but I really want to know. Thanks.**
•  » » 7 years ago, # ^ |   +6 Ok, USACO's answer: "Wifi setup: If the answer is an integer, print it as an integer. If it is half-integral (a decimal ending with .5), print it as a decimal with one digit after the decimal point."
•  » » » 7 years ago, # ^ | ← Rev. 4 →   0 It's so funny ! my code always answer with one digit after the decimal point and mybe it will get WA on many tests ! the clarification didn't mention to it ! X-(
•  » » » » 7 years ago, # ^ |   0 Same here bro. So stupid -.-
 » 7 years ago, # |   0 Is it something wrong with USACO? it doesn't show Remaining time...
 » 7 years ago, # | ← Rev. 2 →   +2 For how long does Gold contest lasts this time? 3 or 4 hours?
•  » » 7 years ago, # ^ |   0 4 hours.
 » 7 years ago, # |   +8 In USACO, Is the stacksize increased by default?
 » 7 years ago, # |   0 Can i knew my submittion result during contest?Or only samle tests?
•  » » 7 years ago, # ^ |   +3 Solutions are checked only on the sample test cases during the contest . They will be evaluated later and you will know your results only when they officially declared.
 » 7 years ago, # | ← Rev. 2 →   0 According to the announcement,the contest will be over 15 minutes later(Dec 17,23:59 UTC-12).UPD:Sorry,actually it will be over at Dec 18,03:59 UTC-12.We can discuss problems after that.
•  » » 7 years ago, # ^ |   +3 As far as I understand, "starting window" will end at this time, however it's possible to start the contest at this time so we can only discuss tasks 4 hours later.
 » 7 years ago, # |   +6 Can the last problem in Gold division be solved if cows are allowed to run not only away from the 1st barn?
•  » » 7 years ago, # ^ |   +5 I originally understood it that way so I think it could. :) Here's a sketch of an O(n log^2 n) solution: First, let's find the center of the tree C and root the tree at C. Find the list of lengths from C to every other vertex and sort it. Now, for each element a of the list we can easily compute number of other elements b, such that a + b <= L. That way, we are able to find for each vertex v the number of vertices w s.t. the path v-->C-->w is of length <= L. Doing roughly the same thing for length lists limited to every single subtree of C, we can subtract for each vertex v the number of vertices w such that the shortest path from v to w does not go through C. Overally, for each vertex we will know the number of vertices located past vertex C, that are still close enough to be counted. Now all you need to do is to delete edges adjacent to C and recurse on each subtree. Every subtree is at least two times smaller, so the complexity is O(n log^2 n).Any idea how to do that in O(n log n)? :)
•  » » » 7 years ago, # ^ |   0 I don't understand your solution fully, but in a chain every subtree will be two times smaller only when you delete first vertex(i. e. center of a graph).
•  » » » » 7 years ago, # ^ |   0 Deleting edges adjacent to center C is just the same as deleting the center itself (there's no way back from the subtree to C or any other subtree after any of these).
•  » » » » » 7 years ago, # ^ |   0 For each subtree(say with root T) do we sort distances from C to all vertices or from T to all vertices?
•  » » » » » » 7 years ago, # ^ |   0 We always sort the distances from the center of the processed tree. So if out tree is 1--2--3--4--5, in the first call we will find center 3, sort the distances from 3 to 1, 2, 4, 5 and do the processing I described to compute for each vertex the number of other vertices that are past the center and at most L miles away. Once we are done, we delete vertex 3 and run our procedure independently for trees 1--2 and 4--5.
•  » » » » » » » 7 years ago, # ^ |   0 So do we go only one level down and not deeper?
•  » » » » » » » » 7 years ago, # ^ |   0 Of course we go deeper, it's a pretty standard divide and conquer. In the top call we consider only paths going through the center C. In subsequent calls we'll consider only paths not going through C, but through centers of the smaller trees ans so on.
•  » » » » » » » » » 7 years ago, # ^ |   0 How will it work then on a chain of 200000 vertices?
•  » » » 7 years ago, # ^ |   0 I think I have a solution in N*log(n) to this problem. Root the tree at node 1. Foreach node, add 1 to every node on its path to the root, if the distace <= L. The last node can be found vial logarithmic jumps(well nḱnown data structures) in O(log(n)) (binary search). How to set one to each node on that path? The answer is a techinque called heavy_light decomposition.
•  » » » » 7 years ago, # ^ |   +6 But what about paths that are first up, then down?
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Ok, that's true, but I interpreted the statement in a way, that this is not possible. It says: "FJ does know that the cows only run away from the barn". This means to me, that they go away in every step of the path.. Wrong? Maybe my english is not good enough
•  » » » » » » 7 years ago, # ^ |   +6 But this thread is about version of the problem without this condition
•  » » » » » » » 7 years ago, # ^ |   0 Ok, I'm sorry for this.
 » 7 years ago, # |   +1 How can i solve third problem from bronze div?
•  » » 7 years ago, # ^ |   0 Draw field after coordinate compression, next bfs. May be it's not optimal solution.
•  » » » 7 years ago, # ^ |   +3 How do you compresse the coordinates? Using a global pgcd on the differences between each adjacent points, and consider min_x and min_y as origin? And if so, isn't there some special cases where the compression can't be applied?
•  » » » » 7 years ago, # ^ |   +1 I just saved all x's and y's coordinates in big array and compressed. Now all numbers are less than 3000 (on contest I thought that bound is 1500:( ). Also you can make two arrays for x's and y's — bound will be 1500. Of course there is no special cases cos all holes in fence remain holes.
•  » » 7 years ago, # ^ |   0 Is there a way how to see the problems of the other divisions, except of waiting some days? :)
•  » » 7 years ago, # ^ |   0 You may also try this problem, http://uva.onlinejudge.org/external/119/11918.html, It also requires grid compression, a bit harder than the usaco's one.
 » 7 years ago, # | ← Rev. 2 →   0 Can the first problem be solved using some non greedy algorithm?I used maximum bipartite matching and I was able to find out how many cows from the first group will survive but I found no correct way to output the lexicographically earliest ordering of the cows.UPD: I'm talking about the gold division.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +8 If you need first lexicographically, you always try to set first element of the sequence the least, that there exist answer starting with this element.I did this way. Matching exists if and only if for every group it's not larger than sum of the other groups. So main idea is to choose two elements least lexicographically, and try them put in the first place and check whether you can continue.There are several different situations, so you must be accurate when solving them.
•  » » 7 years ago, # ^ |   +7 I'm not sure I see how to use bipartite matching to solve this. Care to explain?I intended for it to be solved greedily.
•  » » » 7 years ago, # ^ |   +9 For how long we should wait for the results?
•  » » » » 7 years ago, # ^ |   0 I really don't have any control over that. Usually the first time I see the results are after they are released. AFAIK everything is ready at this point.
 » 7 years ago, # |   +5 Is there anyone who know when will they post the result?
•  » » 7 years ago, # ^ |   +1 I was about to post that:)
•  » » 7 years ago, # ^ |   +2 They should put more informations on the website about the true status of the contest :/
 » 7 years ago, # |   0 Was #3 in silver just a modified djikstra?
•  » » 7 years ago, # ^ |   0 State: denotes the length of the shortest path to vertex v with capacity . Compress the capacities in the given input into at most M ranks. Then it suffices to solve the problem using Dijkstra.
•  » » 7 years ago, # ^ |   0 I used a modified Dijkstra but I have a doubt if that problem can be solved by network flow.
•  » » 7 years ago, # ^ |   0 I solved it by DP.
•  » » » 7 years ago, # ^ |   0 Care to elaborate?
•  » » » » 7 years ago, # ^ |   0 My solution is like Hachson's solution but a bit differs. My code
•  » » 7 years ago, # ^ |   0 My approach was Binary search[ on minimum capacity ] + Dijkstra
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 Well my solution was: Dijkstra returning L for any given lower bound on C (edges with capacity < C are cut off from the graph) the return value of this is non-increasing for increasing C since we're only interested in integer results, it's sufficient to consider only such C, for which (integer division) X/C isn't equal X/(C+1), because if they are equal, then the solution for X/C is obviously better EDIT: for C \ge \sqrt(X), X/C \le \sqrt(X), so there are O(\sqrt(X)) interesting C, and time complexity is therefore O(\sqrt(X)M\lg(N))... not optimal, but hopefully sufficient, haha
 » 7 years ago, # |   +2
•  » » 7 years ago, # ^ |   +3 SILVER-WIFI_SETUP : I thought that cout << res; will print what was expected. But it prints 1.65947e+06 instead of 1659471. So I lost points of test2,test3,test7. Replaced it with : printf("%d",(int)res); if (res != (int)res) printf(".5"); and got full points.
•  » » » 7 years ago, # ^ |   0 I had the same mistake as you and also got WA on those testcases.Fortunately,I got a total of 667 points,just enough to get a promotion to Gold division.What about you?
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   0 600 points =( and test3+test4+test7 makes 100 points
•  » » » » » 7 years ago, # ^ |   +1 I'm sorry.Hope you better luck at January Contest!
•  » » » 7 years ago, # ^ |   +3 Using real valued variables is often not a good idea — their behavior can get messy sometimes. Besides, since the answer is an integer or half-integer, you could've just computed 2*answer and treat both cases separately on output.
 » 7 years ago, # |   +1 Can you go to lower division if your results are bad?
•  » » 7 years ago, # ^ |   +6 No, it's impossible, even if your result is 0.
 » 7 years ago, # |   0 finally the results has been published. :)