_the_beginner_'s blog

By _the_beginner_, history, 3 years ago, In English

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?

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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