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(N 2) 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.
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.
Boxes (link to Polish judge) There are n ( n ≤ 2000) boxes, i-th with weight w i and strength/durability s i. 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.
Hero (Potyczki 2014) Bitor has H health points and he must defeat n ( n ≤ 105) monsters. The i-th monster deals d i damage, but after death it drops a potion that restores a i 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.
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 a v minutes that vertex will be "ready". We want to minimize the moment when all vertices are ready. When will it happen?
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.
Different taste There are n ( n ≤ 105) cookies. The i-th of them gives you a i points if you have it, and b i 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?
BearEats (TCO 2015, 3B) Same problem, but your opponent is greedy and he always eats a cookie with the biggest value b i.
Coins (Polish Junior Olympiad) There are n ( n ≤ 105) stacks of coins, each with two coins. You are given the value of each of 2·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.)
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?
Concatenation You are given a sequence of n ( n ≤ 105) numbers ( t i ≤ 109). Order them in such a way that their concatenation is maximized.
Bonus: SumCards from TCO 2018, Poland round.