Блог пользователя _the_beginner_

Автор _the_beginner_, история, 3 года назад, По-английски

I have a question. Does anyone knows what name of this proof technique? Similar approach is very often used in proofs of correctness of algorithms. I'll start from simplest case which isn't well representative .

All proofs below is how I would proof correctness of solutions for those tasks.

1110B - Tape

Proof

A bit more representative example of this proof technique.

1408B - Arrays Sum

Proof

Much more representative example:

1539D - PriceFixed

Proof

More representative example:

925B - Resource Distribution

Proof

Last example. Most representative.

1249D2 - Too Many Segments (hard version)

Proof

So, usual steps of this technique are following:

  • say: "Suppose we have optimal answer"
  • compare our answer with optimal answer
  • make single change to make optimal answer less different to our answer
  • say: "we can repeat steps until optimal answer become ours"

This way we prove greedy strategy is optimal or among optimal answers there has to be answer of some particular form.

Does anyone know correct name of this technique? Is it even have a name?

  • Проголосовать: нравится
  • +35
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Exchange Argument. Pretty standard way to prove optimality of greedy strategies.

»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

I think your post can be used as a very nice tutorial on exchange arguments for beginners