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]**

this is the link actually:

http://usaco.org/index.php?page=viewcontest

It's time to help FJ with his cows :)

:)

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.**

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."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-(

Same here bro. So stupid -.-

Is it something wrong with USACO? it doesn't show Remaining time...

For how long does Gold contest lasts this time? 3 or 4 hours?

4 hours.

In USACO, Is the stacksize increased by default?

Can i knew my submittion result during contest?Or only samle tests?

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.

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 atDec 18,03:59 UTC-12.We can discuss problems after that.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.

Can the last problem in Gold division be solved if cows are allowed to run not only away from the 1st barn?

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)? :)

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

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

For each subtree(say with root T) do we sort distances from C to all vertices or from T to all vertices?

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.

So do we go only one level down and not deeper?

Of course we go deeper, it's a pretty standard divide and conquer. In the top call we consider

onlypaths 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.How will it work then on a chain of 200000 vertices?

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.

But what about paths that are first up, then down?

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

But this thread is about version of the problem without this condition

Ok, I'm sorry for this.

How can i solve third problem from bronze div?

Draw field after coordinate compression, next bfs. May be it's not optimal solution.

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?

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.

Is there a way how to see the problems of the other divisions, except of waiting some days? :)

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.

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.

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.

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.

For how long we should wait for the results?

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.

Is there anyone who know when will they post the result?

I was about to post that:)

They should put more informations on the website about the true status of the contest :/

Was #3 in silver just a modified djikstra?

State: denotes the length of the shortest path to vertex

vwith capacity . Compress the capacities in the given input into at mostMranks. Then it suffices to solve the problem using Dijkstra.I used a modified Dijkstra but I have a doubt if that problem can be solved by network flow.

I solved it by DP.

Care to elaborate?

My solution is like Hachson's solution but a bit differs. My code

My approach was Binary search[ on minimum capacity ] + Dijkstra

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

At last:)

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 oftest2,test3,test7. Replaced it with :and got full points.

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?

600 points =( and

test3+test4+test7makes 100 pointsI'm sorry.Hope you better luck at January Contest!

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.

Can you go to lower division if your results are bad?

No, it's impossible, even if your result is 0.

finally the results has been published. :)