PS2.md

Greedy & Sorting Problems

These problems often require sorting the input first and then applying a greedy strategy.

• Honest Coach (1360B)
  Rating: 800
  Topic: Sorting, Min Difference

  Hint

  To minimize the difference between two numbers, they must be as close as possible. Sort the array of strengths and then find the minimum difference between any two adjacent athletes.

• Dragons (230A)
  Rating: 900
  Topic: Greedy with Sorting

  Hint

  It's always optimal to fight the weakest dragons first. Sort the dragons by their strength before simulating the battles.

• Two Arrays And Swaps (1353B)
  Rating: 800
  Topic: Greedy with Sorting

  Hint

  Sort `a` ascending and `b` descending to maximize the sum of `a` after swaps

• Vanya and Lanterns (492B)
  Rating: 1000
  Topic: Sorting, Gaps

  Hint

  Sort lantern positions. Max distance between adjacent lanterns / 2 or edges gives required radius.

• Unique Number (1462C)
  Rating: 1200
  Topic: Greedy, Constructive

  Hint

  Greedily pick the largest distinct digits to achieve the sum with the fewest digits.