Please subscribe to the official Codeforces channel in Telegram via the link ×

Does this cost function satisfy quadrangle inequality?

Revision en1, by rhezo, 2017-05-10 01:48:40

Suppose I have a cost function w(i, j) whose value depends on some f(j) and value of w(i, j) increases as |j — i + 1| increases. Also we can't compare between w(i, j) and w(p, q) even when |j — i| = |q — p| since that depends upon f(j) and f(q).

The cost function of land aquisition problem from USACO is similar and in the below link it claims that it satisfies quadrangle inequality. Check problem link from example 2 in below link.

So, does my original cost function satisfy quadrangle inequality? I'm confused!


  Rev. Lang. By When Δ Comment
en1 English rhezo 2017-05-10 01:48:40 690 Initial revision (published)