### Errichto's blog

By Errichto, 2 years ago,

Hi. I'm back from USA!

I will do a new lecture tomorrow (Thursday) at 2pm CEST on my Youtube channel: https://www.youtube.com/watch?v=7hFWrKa6yRM. Watch me live (and ask questions), or just watch the video later. This will be part 1, and I will do part 2 in a few days (maybe Tuesday).

UPDATE — part 2 is coming on Thursday, same time. Link: https://www.youtube.com/watch?v=gXxu-Cr4b4c.

There are no prerequisites this time. I recommend reading the materials below in advance, and trying to solve problems 1 and 5. If you are strong, just read problems and see if you can't solve something (maybe problem 8?).

### Technique "Exchange Arguments"

If we're given n items and we should choose some of them and choose their order, we should sort them with some strange/tricky comparator, and then do O(N2) dynamic programming. The dp should be dp[pref][used] — best possible result (balance) if we chose used items so far (in the prefix pref).

"Strange/tricky comparator" checks which of the two elements should be earlier, usually just solving the problem for N = 2. Alternatively: given two adjacent elements, when is it good to swap them?

Not every comparator is valid, e.g. return A.first < B.second is not. A comparator is fine if it defines the order.

### Warning

Not all problems use the described technique. I think it's a good lesson to see some similar problems and understand when it's possible to use some algo/technique.

### Problems

1. Boxes (link to Polish judge) There are n (n ≤ 2000) boxes, i-th with weight wi and strength/durability si. You can choose some subset of boxes and rearrange them in any order you like. Find the maximum possible number of boxes in a tower where the strength of a box must be not smaller than the sum of weights of boxes above.
Bonus: n ≤ 105.

2. Hero (Potyczki 2014) Bitor has H health points and he must defeat n (n ≤ 105) monsters. The i-th monster deals di damage, but after death it drops a potion that restores ai hp (hp can be above the initial value). Can Bitor choose the order of fights in such a way that his hp never drops below 0? Print "NO" or "YES" with the order of monsters.
Bonus: n ≤ 2000 and maximize the number of defeated monsters.

3. Farmcraft (POI) You are given a rooted tree with n (n ≤ 105) vertices. You are in the root. Moving along an edge takes 1 minute. You want to visit all vertices and get back to the root as fast as possible, what takes exactly 2·(n - 1) minutes. When we visit vertex v for the first time, the countdown is started there and after av minutes that vertex will be "ready". We want to minimize the moment when all vertices are ready. When will it happen?

4. Pretty Good Proportion (GCJ 2015 Finals) You are given a binary string of length n (n ≤ 105) and a real value r (0 ≤ r ≤ 1). Find a substring where the ratio of ones is as close to r as possible.

5. Different taste There are n (n ≤ 105) cookies. The i-th of them gives you ai points if you have it, and bi to your opponent if he has it. Players take a cookie in turns, you start.
Each player maximizes the difference: his_score — opponent_score.
What will be your and opponent's scores if you both play optimally?

6. BearEats (TCO 2015, 3B) Same problem, but your opponent is greedy and he always eats a cookie with the biggest value bi.

7. Coins (Polish Junior Olympiad) There are n (n ≤ 105) stacks of coins, each with two coins. You are given the value of each of n coins (positive values).
You are also given an integer k (k ≤ 2·n). What is the maximum possible value of k coins taken from the top? (If you want to take the bottom of two coins, you must also take the top one.)

8. Parentheses You are given a sequence of strings, each consisting of characters '(' and ')' only. The total length doesn't exceed 105.
You can reorder the strings and remove some characters. The remaining concatenated string must be a balanced parentheses string (TODO, how is this called?) correct bracket sequence. What is its maximum possible length?

9. Concatenation You are given a sequence of n (n ≤ 105) numbers (ti ≤ 109). Order them in such a way that their concatenation is maximized.
Bonus: SumCards from TCO 2018, Poland round.

See my Youtube channel (link) for more videos on algos and CP, and my Facebook page https://fb.com/errichto for some shorter posts, news, problems.

• +478

 » 2 years ago, # |   +37 Isn't it called "exchange argument"?
•  » » 2 years ago, # ^ |   +6 ?
•  » » » 2 years ago, # ^ |   +5 It is the name of the technique "sort by a comparator which says if it's good to swap two elements if the others remain on their places"
•  » » » » 2 years ago, # ^ |   +6 Oh, ok. I've never heard this name and I'm perfectly fine with changing the title if someone confirms this. Thanks!
•  » » » » » 2 years ago, # ^ |   +11 Yeah, I think many people call it "Exchange Arguments" like this video of Algorithms Live looking forward to your next video.
•  » » » » » » 2 years ago, # ^ |   +25 Ok, I've changed the titles. Thank you both!
•  » » » » » » » 2 years ago, # ^ |   0 What is the original title of this post?
•  » » » » » 2 years ago, # ^ |   +42 “Exchange argument” refers to the way correctness is usually proved for this type of approach. Suppose for contradiction that an optimal selection A of items a1, a2, ..., ak is not ordered according to the comparator. Then there exists i such that item ai compares greater than item ai + 1. If we can prove that two such elements may be exchanged without worsening the selection, we can repeatedly exchange adjacent misordered elements until we construct (and therefore prove the existence of) an optimal selection in which all of the items are sorted according to the comparator.
 » 2 years ago, # | ← Rev. 3 →   +35 I can add some problems:100113K - The Merry Student Life During the Term...101149B - No Time for Dragons100971I - Deadline — harder than two previous100026J - Annihilate the Beetles — one more LOL, there are Russian names in the English version of the site. Looks like a CF bug. Problems have English statements, don't worry.
•  » » 2 years ago, # ^ |   0 Could you share a hint on how to sort 2 subtrees on Annihilate the Beetles problem?
•  » » 23 months ago, # ^ |   0 In problem 100971I — Deadline, my solution: Do topological sort on segments If no conflict in topSort, my comparator sorts by deadline and trying to maximize starting point (checking if there is no conflict with previous topSort too) Iterate sorted segments and check if no conflicts I can't find any editorial on the problem; can you give me some hints or check my solution. Thanks
•  » » 17 months ago, # ^ |   0 On problem 100113K - The Merry Student Life During the Term..., How can we choose the optimal subjects?
•  » » » 17 months ago, # ^ |   0 Use exchange argument.Let's say we swap two elements. Calculate the cost c12 for order ...,1,2,... and the cost c21 for order ...,2,1,... Sort by c12 — c21.You need to write c12 and c21 on the paper to simplify the difference (eliminate the same terms in the sum).
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   0 I tried to solve the problem using exchange argument exactly as you say. But my code got Wrong Answer on tc 6. Are there anything wrong with my approach?
•  » » » » » 17 months ago, # ^ |   0 Why can't you stress?
•  » » » » » 17 months ago, # ^ | ← Rev. 4 →   0 Suppose there are two labs needed to be swap. Let say it is A and B. The optimal order for the A and B (with A as the first occurence) is A.p * B.w < A.w * B.pAfter knowing it, just use sorting with that comparator for each subjects. And for each subjects, suppose it is subjects1 and subjects2 we can do sorting for which subjects should be taken first and it has similar approach from the above. It is (sum of subjects1.p) * (sum of subjects2.w) < (sum of subjects1.w) * (sum of subjects2.p)
 » 2 years ago, # |   0 Is there a judge where we can submit the problems?
 » 2 years ago, # |   +16 If you want to submit problems from points 1 and 2 to archive with English statements, here they are: Btw, does anybody have a link to English version of the bonus problem for point 1 (maximize the number of items, n ≤ 105)? I know only one such problem, with statements in Russian only: 100908H - Пицца для вечеринки.
•  » » 2 years ago, # ^ |   0 Can you share a hint on how to solve that bonus problem for point 1?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Useful observation: DP is convex (dpi - dpi - 1 ≥ dpi + 1 - dpi)
•  » » » » 2 years ago, # ^ |   0 Oh thanks. If someone is curious, after that it can be done with a treap that saves differences between consequtive answers. Then because of the above inequality the differences we need to change will be a consequtive part of our treap — bounded above by si (the sum of the differences) and bounded below by wi.Also I think it should be dpi - dpi - 1 ≤ dpi + 1 - dpi.
•  » » » » 2 years ago, # ^ |   +16 There is also a very easy solution to implement (literally 10 lines of code) using a greedy approach: order the pizzas by a[i] + b[i], then iterate in that order, and maintain the optimal answer. When considering a new pizza, always try to add it to the optimal answer. In case you can't add it to the answer (there is a pizza that becomes cold) — discard the pizza with the greatest a[i] from the current answer.There is a presentation with the analysis (in Russian), last problem. It also describes in detail the solution which uses a treap.
•  » » » » » 2 years ago, # ^ |   +10 You can check this problem for Point 1 (Bonus) 101806T - Touch The Sky
•  » » » » » 2 years ago, # ^ |   0 Quick note: You can actually prove the correctness of the algorithm that meshanya mentioned above by not thinking about it necessarily in a "greedy" way, but by drawing the graph of the convex DP array. The graph consists of a bunch of line segments, so you can store the differences (lengths of the segments) in a set. When you do a DP update, the overall effect is equivalent to adding a line segment to the DP in sorted order and removing the last line segment if it exceeds the maximum box, which turns out to be exactly the "greedy" solution above.
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   0 Can you please elaborate on how we arrived at this conclusion? Thanks :DEdit: Got it
•  » » » » 12 months ago, # ^ |   0 30iq0god
 » 2 years ago, # |   +2 I can add this problem also 277D.
 » 2 years ago, # |   0 Is it delayed by an hour?
•  » » 2 years ago, # ^ |   0 No. Why do you ask? It's supposed to be at 2pm CEST, so it starts in 20 minutes.
•  » » » 2 years ago, # ^ |   0 I don't know I saw here and this says it should start at 5.30PM IST which it didn't and youtube showed 60 minutes to go.
•  » » » » 2 years ago, # ^ |   0 Strange. Googling "Poland time zone" gives me "Central European Standard Time (GMT+1)", while googling "CEST time" gives me 2:47pm what certainly is not the current time in Poland. So apparently there are two different CEST's...
•  » » » » » 2 years ago, # ^ |   0 It seems to be "Central European Standard Time", your time, and "Central European Summer Time", what google shows to "CEST".
•  » » » » » 2 years ago, # ^ |   0 'S' in CEST stands for "Summer", if I'm not mistaken. That's why it's one hour off from your local CET time.
 » 2 years ago, # | ← Rev. 3 →   +17 Escape. (Problem 2 on a tree.)
•  » » 2 years ago, # ^ |   0 Can you explain or give approach of how to solve first problem?
 » 2 years ago, # |   +24 I think this problem from NWERC 2017 uses this technique: Installing Apps
•  » » 2 years ago, # ^ |   0 Solution slides here: http://staff.bath.ac.uk/masjhd/NWERC/news/nwerc2017slides.pdfCan someone explain why the sort given works?
 » 2 years ago, # |   +11
 » 2 years ago, # | ← Rev. 2 →   0 Being a Newbie is Killing you day after day Who cares about that ?
 » 2 years ago, # |   0 2018-2019 ICPC, NEERC, Northern Eurasia Finals rated or not?
•  » » 2 years ago, # ^ |   +8 No, but why do you ask here? :P
 » 2 years ago, # | ← Rev. 3 →   0 Thank you so much, i found it was really nice cuz i was so confuse with the skill of solving dynamic problem :D
 » 2 years ago, # |   0 please tell me an effective way to obtain a rating
•  » » 2 years ago, # ^ |   +51 do well in a contest
 » 2 years ago, # |   0 Could you tell if there is a link to submit task 7. And the other tasks (except 1,2 and 4, it is not very hard to find them)
•  » » 2 years ago, # ^ |   0 Our junior olympiad doesn't make things easy to find. The author is johnasselta and he says "who knows where you can find it".I think you should write a brute force and stress test your solution against it.
 » 2 years ago, # |   +4 When is the next stream scheduled? Can't wait to see it!
•  » » 2 years ago, # ^ |   +8 Thursday, same time (2pm Polish time). As usually, see the countdown in a scheduled video: https://www.youtube.com/watch?v=gXxu-Cr4b4c.
 » 2 years ago, # |   +10 Part 2 starts in four minutes.
 » 2 years ago, # | ← Rev. 4 →   0 I am getting wrong answer in 3rd problem. Can anyone help in finding mistake? [Question link] [Code link]
•  » » 2 years ago, # ^ |   +1 You don't count sizes of subtrees correctly. I think you only count the number of children.
•  » » » 2 years ago, # ^ |   0 I corrected it and it passed few more testcase but still not correct fully. Am I missing something? In the subtree size, I am only considering number of edges as it will only be the factor to be dependent on and not the number of nodes. I think this logic is correct.
•  » » » » 2 years ago, # ^ |   +1 Write a brute force and compare results on small random tests.
•  » » » » 17 months ago, # ^ |   0 Incase you are still stuck on this question, i found a bug in your code.Yes your logic is coreect but on line 60 you forgot to add the time to traverse from from u to v. you are only adding the time that will take in subtree v but you need to add the time u->v + v->u time as well
 » 2 years ago, # |   +1 A big fan of your lectures. Thanks for the lectures with such high quality! BTW, when's the next lecture scheduled?
 » 21 month(s) ago, # |   0 Okay, I solved the first problem by first sorting the boxes according to the sum of their weight and strength (wi + si), and then applying 2D dp. It got AC, but I'm still not sure as why this sorting technique works. The only thing I have in my mind is the greedy fact that the boxes having more strength and more weight should be placed at the bottom. But this seems greedy to me. Can someone provide some kind of proof?
•  » » 21 month(s) ago, # ^ |   +3 If there's a solution with bad order, you can take two consecutive boxes of bad order and swap them.
•  » » » 21 month(s) ago, # ^ | ← Rev. 3 →   +10 Thanks! I got it. :)For someone who is still curious, I hope this is useful:The optimal approach is to sort the boxes according to the sum of their weight and strength (Boxes having smaller value of $S_i + W_i$ will be placed on top of other boxes having greater value of $S_i + W_i$. We'll call this order as good order), and then use the approach similar to knapsack dp.Now the question is that whether it is possible to obtain a better answer by not ordering the boxes in good order.Suppose a better answer exists in which the boxes are not ordered in good order. Then at least two boxes $A$ and $B$ will exist in this solution such that $B$ is placed just on top of $A$, and they are in bad order (i.e., $S_b + W_b > S_a + W_a$). Now we'll prove that it is possible to swap these two boxes so that they are in good order and the answer still remains the same. Suppose the sum of weights of all the boxes placed on top of $B$ is $x$ (it is okay to not consider the boxes which are below $A$). Then clearly, $S_b \ge x$ and $S_a \ge W_b + x$. Now adding $W_a$ on both sides in the second equation gives $S_a + W_a \ge W_b + x + W_a$. Combining this with the above equation gives $S_b + W_b > S_a + W_a \ge W_b + x + W_a$, which gives $S_b + W_b > W_b + x + W_a$, which in turn gives $S_b > x + W_a$. Thus we proved that it is possible to swap boxes $A$ and $B$ so that $A$ is placed just on top of $B$ so that they are in good order and the answer still remains the same.Conclusion: The optimal answer that we can get by sorting the boxes in good order, is indeed the optimal answer overall.P.S. : Let me know if I'm still missing something.
•  » » » » 20 months ago, # ^ |   0 How did you get the intuition to sort by (Si + Wi) ?
•  » » » » » 20 months ago, # ^ |   0 A box having more strength than any other box will definitely be able to carry more weight on top of it, so it's better to place it below. At the same time it's wise to put the boxes having less weight at a greater height.
•  » » » » » » 19 months ago, # ^ |   0 Why is it only equal to (Si + Wi) ? Why can't it be equal to (Si * Wi) as well?
•  » » » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Intuition: if Sb + Wb > Sa + Wa,then (Sb — Wa) > (Sa — Wb), or more specifically (Sb — Wa — x) > (Sa — Wb — x) which means that if both can be placed in their current positions, the one in which B is down is better because it allows more weight to come IN-BETWEEN them
•  » » 17 months ago, # ^ |   0 I'm still not clear on the DP part, could you please post your solution?
 » 20 months ago, # | ← Rev. 2 →   0 I tried to solve the problem 6 (bonus) but didn't manage to come up with the idea once the sorting is done.I was reading solutions to the problem and found tourist's code (must be logged in to be able to see it) but I still don't get it. Any idea on what he did or hint to solve the problem?
•  » » 19 months ago, # ^ |   +5 I don't remember the solution perfectly but I think you need these two things:1) When moving from one group of cookies (i.e. those with the same value b[i]), it's only important how many moves your opponent will still spend in previous group(s). You need dp for that. It's $last[k]$ in tourist's code, I think.2) Then, think about what happens even if there is only one group of cookies. You try taking them from biggest a[i] and there is some probability that it's already eaten. What is that probability?
 » 17 months ago, # |   +3 I cannot quite understand why exactly do we need to simplify the equations for comparator functions. Like in 2nd problem, is it wrong if we wrote comparator function as:return (d1+max(0,d2-a1))<(d2+max(0,d1-a2));
•  » » 17 months ago, # ^ |   +11 It will work in this problem but might fail somewhere else. How do you know it's correctly defined order? If it isn't then you'll get rte or wa.
•  » » » 17 months ago, # ^ |   0 Sorry, I couldn't understand it. Like if the original equation doesn't correctly defines order, then how can the simplified version of that work for the purpose?So do you mean, that we need to simplify it only for the purpose of checking if it defines the order?Also can you provide any problem where this logic(of directly coming with condition) fails?
•  » » » » 17 months ago, # ^ |   +8 Simplification is only to convince yourself that it's correct, it isn't required.I'm sure that one of problems is this blog will be your counterexample because some easy comparator would be enough for n=2 but we need a more complicated one.
•  » » » » » 17 months ago, # ^ |   0 Thank you!!
 » 15 months ago, # |   0 Problem 5. Is my solution correct?Sort the cookies by $a_i - b_i$ , lets call it $c_i$ ( and $c_i \leq c_{i+1}$ ), then if $x = c_n - c_{n-1} + c_{ n-2 } - c_{ n-3 } + ....$ then my score is $x$ and my opponent's is $-x$?
 » 15 months ago, # |   0
 » 12 months ago, # | ← Rev. 2 →   0 This is very similar to problem 2. Complete The Projects (Hard Version)EDIT : This problem uses the same ideas as problem 1.
 » 9 months ago, # | ← Rev. 3 →   0 in the 4th problem. if we write (a[i]-a[j])/(i-j) = r + d then we finally get, ((a[i]-a[j])-r*(i-j))/(i-j) = d. if we minimise the numerator only, (by making an array of a[i]-r*i and sorting them),can we be able to minimise the whole LHS ratio? how can it be proved? UPT:done!
 » 6 weeks ago, # |   0 Where I can submit these problems solution?