Div2-Easy: http://ideone.com/uzGzxa
Div2-Medium: http://ideone.com/EXVZ7f
Div2-Hard: http://ideone.com/04H4H8 (This solution can solve n <= 50 instead of 3)
Div1-Easy: http://ideone.com/HMjObD
Suppose the heights are sorted: h[0] <= h[1] <= h[2] ...
In one hand, we know the answer can't be smaller than max{x[i+2] — x[i]}. We can proof this in the following way: If abs(x[i]-x[j]) >= ans, we add an edge between i and j. We assume there is an i and ans < x[i+2]-x[i]. Then if the graph is connected, edges (i, i+1) and (i+1, i+2) will be bridege (since if x < i and y > i+2 then there is no edge between x and y.) It means this graph don't have a hamiltonian cycle, so we can't arrange these foxes around a round table.
In another hand, we know that we have a solution that ans = max{x[i+2]-x[i]}: x[0]-x[2]-x[4]-x[6]-...-n-...x[5]-x[3]-x[1]-x[0].
So we know this solution is optimal.
Div1-Medium: http://ideone.com/pQhKaG
We can compute S in the following way: For each edge, let s1 be the number of nodes in one side, we know there are s1*(n-s1) paths use this edge. So S = sum{s1 * (n-s1)}.
So we can solve it by dp: let dp[i][j] = minimal number of S such that we have a tree with i nodes and sum{s1 * (n-s1) among all edges it have} % m = j. Each time we pick 2 rooted trees, merge them: root1 becomes a son of root2. We can compute the new sum{s1 * (n-s1)} in O(1). So our algorithm can run in O(n^2 m^2).
Div1-Hard: http://ideone.com/b4v3nY (rng_58's code)
The given input is a mapping from {0,..,n-1} to itself, it is x=>(0*x), we call it f. Suppose 0*0 = 3, then what can we get? We know that 3*x = (0*0)*x = 0*(0*x) = f(f(x)) = f^2 x. So it means x=>(3*x) is f^2. And if we know 0*3 = 5, then we should get x=>(5*x) is f^3..
We construct this graph: for each i, we add directed edge from i to firstRow[i]. Then there must be some connected component, each one is a cycle with some tree towards the cycle. Suppose we have path: 0->1->2->3->4->2. (it means the component of 0 have a cycle length = 3, and the distance from 0 to cycle is 2). Then we have: f^6 = f^3. Then we know in the following cases there is no solution.
- There is a cycle, its length is not a divisor of 3: For example, if there is a cycle 5->6->5. Then f^6 (5) = 5, but f^3 (5) = 6, they are not equal.
- There is a node, the distance to cycle is larger than 2 + 1 = 3:
For example, if there is a path: 7->8->9->10->11->11, then we have: f^6 (7) = 11 (something on the cycle), but f^3 (7) = 10 (something not on the cycle). Beside these 2 cases, the solution always exist:
- Let e[0] = 1, if there is an edge(i->j), then we set e[i] = e[j] — 1. By this we can get e[i] for all nodes in 0's component. We set i*j = f^(e[i]) (j).
- For all element in other component, we set: i*j = i.
We could verify it is a valid solution.
Thanks for an interesting problemset :)
Solutions to all 3 problems are so short&simple — I think it happens not very often:)
Can you please explain how to solve C , Div — 2 .
If n = 3, and O is in the triangle, the answer is: min(min{|O — P[i]|}, max{|P[i]-P[j]|/2, i!=j}).
Otherwise the answer is min{|O — P[i]|}
If n is large, we can do it by: binary search the answer, then if the distance between P[i] and P[j] is less than 2*ans, we draw an edge between them. There is a solution if and only if O is in some polygon.
Less obscure solution for div1 250:
We can binsearch the min-max difference, or just iterate over all possible ones from 0 to 1000 and choose the first one for which we find a solution.
We know that if there's a solution, then the heights from the min. to max. height are non-decreasing on each side. If there's another solution, we can sort the foxes on each side between the min. and max. height without worsening the max. difference.
So let's build the optimal line of foxes on one side between the foxes with min. and max. heights. In this case, optimal means that we start with the fox with min. height and always choose the fox with max. height that's <= our chosen max. difference + height of the last fox we chose. In the end, we choose the fox with the max. height.
All the foxes we chose go on the row between min. and max. heights on one side of the circle, the rest goes on the other side. All we need to do now is check if doesn't give a max. difference bigger than the one we're expecting (chosen in binsearch or current iteration) and if it doesn't, then print the solution we constructed this way. Tada!
I did the same; I was thinking either other people are much better in coding or there exists simpler solution while looking at 245+ scores in standings :)
I also did a binary search at first and was thinking the same thing when I saw the scoreboard.
Medium was really nice. Solution is so simple, but it took me more than half of SRM to come up with it (unfortunately made a bug, as always :P), I tried to do some dp without fixing n, but I needed one more parameter (sum of depths) which was too much. Observation that we should proceed in our dp knowing that in future our tree will have n nodes makes this problem nice :).
I actually had the sum of depths in my dp, too. It was obviously too slow so 3 minutes before the end of the contest I added one more constraint to it: every time we are either growing a new root and connecting it to the old one or we are merging the current tree with another one of size at most 8. This appeared to be enough to pass system tests :) Not sure if it's correct, though.
For the Div1 250 problem,either I haven't understood the solution or in this statement, "If abs(x[i]-x[j]) >= ans, we add an edge between i and j." There should be a less than equal to symbol "abs(x[i]-x[j]) <= ans".
In Div1 Medium, "For each edge, let s1 be the number of nodes in one side, we know there are s1*(n-s1) paths use this edge. So S = sum{s1 * (n-s1)}."
But when we merge 2 subtrees, we are only considering the edge which joins the 2 of them. For example, if we merge t1=0-2-1 and t2=3-4-5. Here 0,1,2,3,4,5 are vertices and — represent edges. Then here s1=4 and s2= 4. Total (by editorial) if 3 is made child of 2 should be s1+s2+3*3. But actual total is coming out to be s1+s2+24.
24 = 9,distance from 0 to all of t2 + 9,distance from 1 to all of t2 + 6,distance from 2 to all of t2.
You need to carefully re-read and understand what exactly dp[i][j] is. While i is the number of vertices in current tree dp[i][j] is the the sum s1(n - s1) over all edges of this current tree. See? Not s1(i - s1) but s1(n - s1). For each edge we calculate its impact in the resulting n-vertex tree but not in the current one.
You forgot to use j when explaining what your dp[i][j] is. I believe there should be j instead of r.
Yes, you are right. Fixed. Thanks for finding that! :)
I'll add that in the construction for div1 1100, we really need to apply the rules e[i] = e[j] - 1 both if we know only e[i] and if we know only e[j]. Also, we need to define f0 and fm for negative m; for me, defining them as identity worked.
For checking if a solution exists, I simply filled rows reachable along edges from 0 and when I reached the cycle, I checked if the values the next row should be filled coincide with the ones it was filled with before.
Thanks for your editorial. On the other side, I am a bit confused since I find you are the author of this round, why do you post srm editorial on codeforces, instead of topcoder: http://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis ?
I am just curious about the reason, no blame at all. On the contrary, thanks for the editorial and problems.