Please read the new rule regarding the restriction on the use of AI tools. ×

oleksg's blog

Help with understanding solution for D. Handshakes
By oleksg, history, 3 years ago, In English

Here is the problem link https://codeforces.me/contest/534/problem/D Basically, the problem boils down to finding a correct rearrangement of some numbers such that each next number is the previous number + 1 — 3m where m is some non-negative integer, and you have to start with 0. The solution is to always pick the biggest number possible, (so if you are currently on x, you try x + 1, then x — 2, then x — 5, etc...). Why does the greedy method work?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It should be somewhat obvious why the next number is at most the previous number + 1 -- the number of new people to shake hands with increases by at most 1 with the arrival of the current student. The -3m term comes from the fact that any 3 people can form a team between the arrival of two consecutive students. Hope that helps!

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    As for why you pick the biggest number possible, notice that in every situation where a larger number satisfies a particular moment, a smaller number would satisfy the same moment (given that they're a multiple of 3 apart). For example, if one person could have 5 people to shake hands with, they could also have 2 people to shake hands with if you assume that 3 ppl formed a team just previously. That means you always want to pick the biggest number possible, because a smaller number is never going to be a disadvantage in the future. (sorry for missing that in the first comment lol)

    → Reply