Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Errichto's blog

By Errichto, 3 weeks ago, In English,

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?

Bad comparators

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.
    Bonus: https://www.hackerearth.com/challenge/competitive/algorithms-india-hacks-2016/approximate/h-bear-and-cookies-2/.

  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.

 
 
 
 
  • Vote: I like it  
  • +470
  • Vote: I do not like it  

»
3 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

Isn't it called "exchange argument"?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    ?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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"

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Oh, ok. I've never heard this name and I'm perfectly fine with changing the title if someone confirms this. Thanks!

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          Yeah, I think many people call it "Exchange Arguments" like this video of Algorithms Live looking forward to your next video.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +42 Vote: I do not like it

          “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.

»
3 weeks ago, # |
Rev. 3   Vote: I like it +35 Vote: I do not like it

I can add some problems:
100113K - The Merry Student Life During the Term...
101149B - No Time for Dragons
100971I - Deadline — harder than two previous
100026J - 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a judge where we can submit the problems?

»
2 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

If you want to submit problems from points 1 and 2 to archive with English statements, here they are:

  1. CODEFESTIVAL 2017 D

  2. ICPC Finals 2016 L

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you share a hint on how to solve that bonus problem for point 1?

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Useful observation: DP is convex (dpi - dpi - 1 ≥ dpi + 1 - dpi)

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 weeks ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        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 weeks ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          You can check this problem for Point 1 (Bonus) 101806T - Touch The Sky

        • »
          »
          »
          »
          »
          42 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Can you please elaborate on how we arrived at this conclusion? Thanks :D

        Edit: Got it

»
2 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

I can add this problem also 277D.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it delayed by an hour?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No. Why do you ask? It's supposed to be at 2pm CEST, so it starts in 20 minutes.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It seems to be "Central European Standard Time", your time, and "Central European Summer Time", what google shows to "CEST".

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          '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 weeks ago, # |
Rev. 3   Vote: I like it +17 Vote: I do not like it

Altruistic Amphibians.

Escape. (Problem 2 on a tree.)

»
2 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

I think this problem from NWERC 2017 uses this technique: Installing Apps

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it
»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Being a Newbie is Killing you day after day

Who cares about that ?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

2018-2019 ICPC, NEERC, Northern Eurasia Finals rated or not?

»
2 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Thank you so much, i found it was really nice cuz i was so confuse with the skill of solving dynamic problem :D

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please tell me an effective way to obtain a rating

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
13 days ago, # |
  Vote: I like it +4 Vote: I do not like it

When is the next stream scheduled? Can't wait to see it!

»
10 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Part 2 starts in four minutes.