### chrome's blog

By chrome, 2 years ago, translation, ,

Hi there!

Tomorrow at 14:00 MSK will be held Topcoder SRM 687.

Let's discuss problems after contest.

•
• +129
•

 » 2 years ago, # |   +13 Starts in less than an hour.
 » 2 years ago, # |   +10 I forgot about it :-(
 » 2 years ago, # |   +14 Spend half an hour trying to compile my code using Arena.Now I can't even try to challenge anyone. 'Your request timed out'.
 » 2 years ago, # |   +6 How to solve the Div-1 500?
•  » » 2 years ago, # ^ |   +17 Maybe cgy4ever has one of his crazy simple solutions, but notice that if a graph exists, then a tree exists. min-cut from u to v in a tree is simply smallest edge in the path from u to v, so you can greedily add the edges in the matrix from largest to smallest weight as long as the graph remains a tree (no cycles are formed).
•  » » » 2 years ago, # ^ |   +27 This tree is called Gomory-Hu tree :)
•  » » » » 2 years ago, # ^ |   +27 And the algorithm he described is called Kruskal.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 I did exactly like that (kruskal for max spanning tree), but failed systest. Just noticed that the problem need connected graph, (we can add edge with weight = 0), at first I think the problem only reject empty vector (if the flow matches the given input). Next time I should to read problem more carefully :X
•  » » » » 2 years ago, # ^ |   0 Yup. Figured that out with 2 minutes to spare, sadly couldn't code it up in a way that accounts for the possibility of no solution (if a solution were guaranteed, you just return a copy of the row containing the largest element, with a single zero removed).Basically I'm pretty sure the answer is look for the largest element (or rather any one of them), construct a bidirectional edge from the row index to the column index (it is evident that the largest edge must be on the very end). Then from now on look only in that row. Look for the largest element (remember, only in the chosen row) whose index hasn't been added yet (you can do this very naively). Now add an edge from the last added index to that index, with the given weight. Continue until every vertex is accounted for. Do a modified Floyd-Warshall (with max instead of min, and min instead of add) on the resulting graph. Change all i,i values to zero because the problem says so. If the result is the exact same as your input matrix, return a copy of the row, minus the i,i element. If it's not, then return -1 since this means there is no solution.Does that sound right?
•  » » » » » 2 years ago, # ^ |   0 Just found a counterexample... so I guess instead you could do the following. Find the largest value... that edge is still in the tree. After that, find the largest value in the whole matrix that contains at least one vertex that hasn't been added yet. Add that edge. Continue until you've added n-1 edges. Now do the modified Floyd-Warshall check I mentioned above, but instead of a row, return the added weights.
•  » » » 2 years ago, # ^ |   +13 What is the proof that if a graph exists, then a tree exists?
•  » » » » 2 years ago, # ^ |   +5 the proof is Gomory-Hu tree. As mentioned before.
 » 2 years ago, # |   +3
•  » » 2 years ago, # ^ |   +8 Original contest — http://codeforces.com/gym/100153.
•  » » » 2 years ago, # ^ |   0 Oh, we even got a "first to solve" on this task during that contest :D. I came up with solution (since it's trivial if somebody knows about Gomory-Hu tree) and Smu coded it :).
 » 2 years ago, # |   +10 Why every sample in medium that results in a graph results in a star graph with center at zero? Was that intended?
•  » » 2 years ago, # ^ |   0 Wasn't answer to pretest 2 a triangle? (Although it could be also a chain of length 2, which is indeed a star graph)
 » 2 years ago, # |   +4 How to solve div2-1000 ?
 » 2 years ago, # |   0 How to prove that greedy strategy works for Div 1 250?
•  » » 2 years ago, # ^ |   +21 Let's assume greedy works for every number between 2 and N - 1.Let's define Ai as the biggest number in the sequence s.t. Ai = N or Ai < N - 1. The number N - Ai is smaller than N and is not 1, so for it a greedy strategy works.The only thing left to show is that the greedy solution for N - Ai does not contain Ai and therefore no number is duplicated. (Obviously, it will not contain numbers bigger than Ai). Let's assume the opposite. Then N - Ai ≥ Ai, then N ≥ 2 * Ai ≥ Ai + Ai - 1 - 1 = Ai + 1, which contradicts our definition of Ai.
•  » » » 2 years ago, # ^ |   0 Thanks!
•  » » » 2 years ago, # ^ |   0 Hey , I think you missed out Ai = N - 1.We can still show in this case too, there always exists an answer:Ai - 1 + Ai - 2 - 1 = N - 1. that implies:Ai - 1 + Ai - 2 = N ( For all i > 2)
•  » » » » 2 years ago, # ^ |   +3 It is a question of definition of Ai. Look again at mine — I don't define it as a largest element of sequence not exceeding N, I say that Ai is never N - 1, which implies that when largest element of sequence Fx not exceeding N is N - 1, I instead use Ai = Fx - 1, and so N = Fx - 1 + Fx - 2.
•  » » » 2 years ago, # ^ |   +1 2, 3, 4, 6, 9, 14, 22, 35 Let's say N = 10According to your definition of Ai, Ai = 6. Here N is in fact >= Ai+1 which is 9, so how does it contradict your definition of Ai?I don't think I got that proof properly
•  » » » » 2 years ago, # ^ |   +3 Yes, according to my definition, Ai = 6. Which is exactly why according to the strategy I described we will choose the solution (6, 4), instead of trying (9, ???) which won't work.
•  » » 2 years ago, # ^ |   0 Using induction method
 » 2 years ago, # |   0 Now the hard question comes: How to solve div1Hard? The only thing I noticed was that the negative difference was not a problem, because if we have an answer a0, a1, .., a(N-1) we can substract the minimum, obtaining at least one 0, guaranteeing the existence ofpozitive maximum difference for each allien, but I'm not even sure if this observation is usefull.
•  » » 2 years ago, # ^ |   0 There was a thread in Russian UI about it already. The solution is as follows. Let's solve weighted-matching problem (in graph with weights  - wij) together with its dual (most algorithms provide dual solution — potentials in Hungarian algorithm, potentials for Dijkstra inside min-cost-max-flow). Then just take  - πi where i is a destination, and possibly adjust all of them so that they're non-negative.Proof. Dual problem for weighted matching is as follows:find weights ws, wt for all vertices, so that: For each edge s - t, ws + wt ≤ ws, t, One can notice that for an optimal solution of dual problem, every optimal solution of weighted-matching problem uses edges with ws + wt = ws, t. I.e. if we can adjust both skiers and destinations, we can adjust them with πi, and get a graph where there is a full matching on edges with adjusted weight 0, and all other edges have adjusted weight  ≤ 0. This would be enough for us, but we cannot touch skiers. Fortunately, if we just ignore them, relative order of their edges preserves, and potentials of destinations still give us a solution.