Codeforces Round #712 Editorial

Codeforces Round #712 Editorial

• 2 years ago, # ^ | python: 111931953 C++: 111890876 Essentially each city must have an outgoing cost of its floor. Additionally, we're going to need to pay the cost max(a) — min(a). However, if we use a sequence of cities to go from min(a) to max(a), we can use the floors to "pay" for max(a) — min(a). In other words, we only need to pay for the parts of the segment from min(a) to max(a) that aren't already paid for by the floors of the cities along the way.

  • 2 years ago, # ^ | I mean I can understand the dijkstra one and everything before, but I can't understand why the formula in solution 2 is true.

• 2 years ago, # ^ | I think its missing the sum of c , otherwise it should be correct . the summation in the editorial is counting how much extra cost we have to pay to reach i if we can jump from any city j with j<i which is

• 2 years ago, # ^ | I didn't understand either. I think the wording is kind of confusing.

  • 2 years ago, # ^ | The formula is . There are two cases. If then must update the greatest value. Otherwise and it won't contribute to the answer.

  • 2 years ago, # ^ | ← Rev. 5 →   +75 I think we actually need a detailed analysis to justify the formula. Maybe I am just not that good for having the intuition, though. Here is the analysis, consider constructing the path from a1: Lemma 1. Consider without max(0,), it is always beneficial for us to break one step into two steps. proof: two step cost is a[3]-a[2]-c[2] + a[2]-a[1]-c[1], one step cost is a[3]-a[1]-c[1], since c[2]>0 the two step cost is better. Now add max(0,) back, so sometimes breaking steps are useless (but never worse). Lemma 2. To reach the i-th block, the one step with minimum cost is from j with max a[j]+c[j] before. proof: I am not considering the steps before j but only this step, this should be trivial. Now let's call this maximum a[j]+c[j] "premax". (prefix max) Lemma 3. If we reach some i such that a[i]>premax, than a[i]+c[i] becomes new premax in the next iteration. Let's call such i "breakpoint". Also note that when reaching a breakpoint, the cost>0 so max(0,) is useless and thus we can apply Lemma 1 later. proof: Because c[i]>0. So a[i]+c[i]>a[i]>premax. Combine these all, we would obtain the strategy. Strategy: Suppose we are standing at some certain block, then we can keep going right and update premax with zero cost until we reach a breakpoint. Then because of Lemma 1 we should make a step to the breakpoint, and because of Lemma 2 we should go from the premax we've found. Because of Lemma 3, paths like this won't happen: i -> j -> i -> k (where a[i]+c[i] is the premax for both j and k) since j would be the premax for k. So we won't need to step on a premax twice, which allows us to reconstruct a Hamiltonian Cycle later. Thallium54 Although not rigorous, hope this helps.

    • 2 years ago, # ^ | Lemma 1 is important. Thanks for the explanation.

  • 2 years ago, # ^ | ← Rev. 2 →   +24 I think this is the reasoning behind the formula: we want to get from to in a number of steps, with the minimum cost. If these steps are , with ( and ), then the path will be . So the not included in the step series will be the nodes on the path from to . In the summation, I found it a bit easier to do it backwards (from to , the final answer will remain the same): so, firstly, we want to see from which node we get the best cost from to and, as the editorial shows, it's the with the maximum . So this will be the the step . Then, when we have , we update the index for the next best and this new will be . We repeat this process until we reach , when we know for certain that we have calculated the whole step series (because then we just get that , which we already knew). So basically we construct the path from to edge by edge, the only difference between my explanation and the editorial being the order in which we construct the step series. The indexes for which we have will belong to the path from to .

  • 2 years ago, # ^ | All the proofs above are extremely cool and clear up the whole idea. Colin's stream has also a similar proof. I got it from there. Folks can see there too if they are still unsure.

• 2 years ago, # ^ | ← Rev. 3 →   +25 I guess I'll also put my proof here, since I've been thinking about it for a while. The problem is the following: you are given a weighted directed graph with vertices (numbered from to ). The th vertex has outgoing edges to all vertices with weight , and outgoing edges to all vertices with weight . What is the weight of the shortest path from vertex to , plus ? This problem is equivalent to the original problem, because any path from vertex to in this problem can be turned into a tour in the original problem with the same cost: simply follow the same cities along the shortest path from to , and then visit all unvisited cities (plus city to complete the tour), in decreasing order. Furthermore, the weight of the shortest path from vertex to is a lower bound for the answer in the original problem, since some path from city to must exist in the tour. To find the weight of the shortest path from to in the new problem, define for (same expression as in the editorial) and for . Let's prove that the weight of the shortest path from to is equal to using induction from to . Our inductive hypothesis is the following: suppose we're at step ; then for all , the weight of the shortest path from vertex to in the subgraph containing the first vertices is equal to . This is true for , because the weight of the shortest path from vertex to in the subgraph containing one lonely vertex is . Now suppose we're at step and that the inductive hypothesis is true for ; let's show that the inductive hypothesis is true for . There must exist some last directed edge in some shortest path from to . Firstly, let's show that all previous shortest paths don't change by adding vertex to the subgraph. Suppose that there exists some such that the shortest path from to decreases by adding this new vertex. Then one such new path must be a concatenation of some shortest path from to (in the subgraph containing the first vertices), plus the edge , and then the edge . If , then the previously computed shortest path from to must have been at least as good, since prefixes of are monotonically increasing. If , then the concatenation of the shortest path from to , plus the edge , is at least as good, because the weight of the edge is less than or equal to the weight of the edge . Either way, there is a contradiction. Now let's show that the weight of the shortest path from to in the subgraph containing the first vertices is equal to . Welp, my tablet pen clicked outside of the comment box, so I lost a bunch of work... Just gonna give up here... In short, the idea is the following: let be the greatest index such that , or if no such index exists. Then it must be true that . Since all prefixes past are the same, it doesn't matter from which one we transition from. So we can just choose the index with the maximum value, and transition from that. Turns out, the maximum value in general (for ) must lie in that range.

• 2 years ago, # ^ | ← Rev. 2 →   +1 After reading the explanations here, I was able to understand a bit more about the formal-"why does it work", but I still had not intuitive-"why does is work". After sleeping and thinking and trying, what finally helped me understand it, in the editorial we have this implementation: sort(ve.begin(), ve.end()); long long mx = ve[0].first + ve[0].second; for(int i = 1; i < n; i++) { ans += max(0LL, ve[i].first - mx); mx = max(mx, ve[i].first + ve[i].second); } I didn't get how this works, and why this works. I made another implementation for myself. sort(ve.begin(), ve.end()); long long mx = ve[0].first + ve[0].second; for(int i = 1; i < n; i++) { if(ve[i].first + ve[i].second >= mx) { ans += max(0LL, ve[i].first - mx); mx = ve[i].first + ve[i].second; } } It is pretty much the same... I added an if-statement and removed the max(mx, ...) from calculating mx. But it changes one thing, which helped me understand this. The summation to sum is more explicit. We only add something, if we can improve our mx. This means we check each city from the ugliest city to the most beautiful one and always enter a city if we can improve our mx. The algorithm is 100% greedy now. It's also the same as in the editorial. ve[i].first - mx > 0 implies ve[i].first + ve[i]second > mx. So we also only add when we can improve mx. I have no prove why this works, but this helped me on the "intuition"-part, why it should work.

  • 2 years ago, # ^ | You can see my comment for the proof. I agree that my explanation makes the solution not intuitive.