Mike_Mirzayanov_Is_Pussy's blog

How to prove composition of two funtions of type min(c,max(b,x+a)) is of the same type
By Mike_Mirzayanov_Is_Pussy, 3 years ago, In English

Suppose i have functions $$$f(x)=min(c_1,max(b_1,x+a_1))$$$ and $$$g(x)=min(c_2,max(b_2,x+a_2))$$$ , how to prove that $$$g(f(x))=min(c,max(b,x+a))$$$ . Here except $$$x$$$ all other values are constants.

Motivations of the problem : I was reading editorial of atcoder ABC 196 problem here but i am not able to understand how 3rd step came from 2nd in the proof.

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

»
3 years ago, # |
← Rev. 2   Vote: I like it +56 Vote: I do not like it

If you're fine with a symbol-pushing proof, then here we go:

Your function $$$f$$$ takes a value $$$x$$$, then adds $$$a_1$$$ to it, then maximizes it with $$$b_1$$$, and then minimizes it with $$$c_1$$$. We'll denote it, maybe a bit unorthodoxically, in the form of the following "pipeline": $$$\mathrm{ADD}(a_1);\, \mathrm{MAX}(b_1);\, \mathrm{MIN}(c_1)$$$. An argument enters the pipeline from the left and evaluates all the operations from left to right.

Your $$$g(f(x))$$$ is of the form $$$\mathrm{ADD}(a_1);\, \mathrm{MAX}(b_1);\, \mathrm{MIN}(c_1);\, \mathrm{ADD}(a_2);\, \mathrm{MAX}(b_2);\, \mathrm{MIN}(c_2)$$$. We will shorten it again to three operations, however, using two observations about ADD, MAX, and MIN: two consecutive operations of the same type can be easily combined into a single operation of this type, and we can change the order of any two operations of different kinds (but this may possibly change the arguments of these operations). Formally:

  • $$$\mathrm{ADD}(x);\, \mathrm{ADD}(y)$$$ is obviously the same as $$$\mathrm{ADD}(x + y)$$$. We can write similar formulas for two MAX's and two MIN's.
  • $$$\mathrm{MIN}(x);\, \mathrm{ADD}(y)$$$ is equivalent to $$$\mathrm{ADD}(y);\, \mathrm{MIN}(x + y)$$$ (if you increase a number by $$$y$$$ first, then you have to minimize it by a number which is $$$y$$$ higher than originally).
  • $$$\mathrm{MAX}(x);\, \mathrm{ADD}(y)$$$ is equivalent to $$$\mathrm{ADD}(y);\, \mathrm{MAX}(x + y)$$$ (same as above).
  • $$$\mathrm{MIN}(x);\, \mathrm{MAX}(y)$$$ is equivalent to $$$\mathrm{MAX}(y);\, \mathrm{MIN}(\max(x, y))$$$. Why? If $$$x \geq y$$$, then both chains of operations take an input number and change it into the closest number which is in the interval $$$[y, x]$$$. If $$$x < y$$$, however, the operations always produce $$$y$$$.

With this information at hand, you can do a simple symbol pushing. Each of the following lines is equivalent to each other:

$$$\mathrm{ADD}(a_1);\, \mathrm{MAX}(b_1);\, \mathrm{MIN}(c_1);\, \mathrm{ADD}(a_2);\, \mathrm{MAX}(b_2);\, \mathrm{MIN}(c_2)$$$

$$$\mathrm{ADD}(a_1);\, \mathrm{MAX}(b_1);\, \mathrm{ADD}(a_2);\, \mathrm{MIN}(c_1 + a_2);\, \mathrm{MAX}(b_2);\, \mathrm{MIN}(c_2)$$$ (swap MIN and ADD)

$$$\mathrm{ADD}(a_1);\, \mathrm{MAX}(b_1);\, \mathrm{ADD}(a_2);\, \mathrm{MAX}(b_2);\, \mathrm{MIN}(\max(c_1 + a_2, b_2));\, \mathrm{MIN}(c_2)$$$ (swap MIN and MAX)

$$$\mathrm{ADD}(a_1);\, \mathrm{MAX}(b_1);\, \mathrm{ADD}(a_2);\, \mathrm{MAX}(b_2);\, \mathrm{MIN}(\min(\max(c_1 + a_2, b_2), c_2))$$$ (combine two adjacent MINs)

$$$\mathrm{ADD}(a_1);\, \mathrm{ADD}(a_2);\, \mathrm{MAX}(b_1 + a_2);\, \mathrm{MAX}(b_2);\, \mathrm{MIN}(\min(\max(c_1 + a_2, b_2), c_2))$$$ (swap MAX and ADD)

$$$\mathrm{ADD}(a_1 + a_2);\, \mathrm{MAX}(b_1 + a_2);\, \mathrm{MAX}(b_2);\, \mathrm{MIN}(\min(\max(c_1 + a_2, b_2), c_2))$$$ (combine two adjacent ADDs)

$$$\mathrm{ADD}(a_1 + a_2);\, \mathrm{MAX}(\max(b_1 + a_2, b_2));\, \mathrm{MIN}(\min(\max(c_1 + a_2, b_2), c_2))$$$ (combine two adjacent MAXs)

...and the last line is exactly what you want (assuming I didn't miscalculate anything, but everything in this sequence of lines is an effect of me mindlessly applying the rules above).

Note that in this argument, it's only necessary that the operations commute (possibly with a change of the arguments), and that two operations of the same kind can be combined into one. This means you can do a similar trick with e.g. functions of the form $$$f(x) = ((x\, \mathrm{xor}\, a)\, \mathrm{and}\, b)\, \mathrm{or}\, c$$$, and possibly many others.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I forgot to thank you. Thanks for this wonderful and easy to understand explanation. We need more such similar types of explanation in editorials so that people who tried can understand fast if they failed to do by themselves.

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Same solution, but with math way, then here is the solution

We have $$$g(f(x))$$$

$$$= min(c_2, max(b_2, f(x) + a_2))$$$ $$$^{[1]}$$$

$$$= min(c_2, max(b_2, min(c_1, max(b_1, x + a_1)) + a_2))$$$ $$$^{[2]}$$$

$$$= min(c_2, max(b_2, min(c_1 + a_2, max(b_1, x + a_1) + a_2)))$$$ $$$^{[3]}$$$

$$$= min(c_2, min(max(b_2, c_1 + a_2), max(b_2, max(b_1, x + a_1) + a_2)))$$$ $$$^{[4]}$$$

$$$= min(c_2, max(b_2, c_1 + a_2), max(b_2, b_1 + a_2, x + a_1 + a_2)))$$$ $$$^{[5]}$$$

$$$= min(c, max(b, x + a))$$$

where as

const $$$c = min(c_2, max(b_2, c_1 + a_2))$$$

const $$$b = max(b_2, b_1 + a_2)$$$

const $$$a = a_1 + a_2$$$

for which

$$$[1]$$$ Expand $$$g(x) = min(c_2, max(b_2, x + a_2))$$$

$$$[2]$$$ Expand $$$f(x) = min(c_1, max(b_1, x + a_1))$$$

$$$[3]$$$ Since $$$min(a, b) + x = min(a + x, b + x)$$$

$$$[3]$$$ Since $$$max(a, b) + x = max(a + x, b + x)$$$

$$$[4]$$$ Since $$$min(a, max(b, c)) = max(min(a, b), min(a, c))$$$

$$$[4]$$$ Since $$$max(a, min(b, c)) = min(max(a, b), max(a, c))$$$

$$$[5]$$$ Since $$$min(a, min(b, c)) = min(b, min(c, a)) = min(c, min(a, b)) = min(a, b, c)$$$

$$$[5]$$$ Since $$$max(a, max(b, c)) = max(b, max(c, a)) = max(c, max(a, b)) = max(a, b, c)$$$

→ Reply