CIELKARA - Editorial

editorial
, , , ,
1

PROBLEM LINKS

Practice

Contest

DIFFICULTY

MEDIUM-HARD

PREREQUISITES

Math, Ternary search

PROBLEM

There is a function f that is defined by:

  • f(t) = B0, for t < A1,
  • f(t) = Bk, for Ak ≤ t < Ak+1, 1 ≤ k ≤ N - 2,
  • f(t) = BN-1, for AN-1 ≤ t.

We have to define the function g, such that:

  • g(t) is continuous,
  • If g'(t) exists, then |g'(t)| ≤ K,
  • The value of integral of |f(t) - g(t)| over -infinity < t < infinity is minimum.

Determine the minimum value of the integral.

EXPLANATION

We can classify the values of g(t) into two types:

Type 1. When t is in the middle of segment Ai and Ai+1, we naturally want that g(t) is always equal to f(t) so that the difference is zero. Therefore we want that for some t in the middle of the segment, g(t) = f(t).

Type 2. When we are near at the end of a segment and about to move to the next segment, we naturally want that g’(t) is as large as possible so that we can jump quickly to the next segment and the difference is minimum. Since |g’(t)| must not be greater than K, we naturally want that |g’(t)| = K.

So, it can be concluded that for each t, g’(t) is either 0, K, or -K.

We can further simplify the problem. In the solution, we will be doing a lot of division by K. So we can assume K = 1 and multiply all Ai by K, and then divide the final answer by K. Also, the areas of the difference between f(t) and g(t) in the integral will almost always form triangles. We will also doing a lot of division by 2 for calculating areas of triangles. We can treat all triangles as rectangles and divide the answer again by 2.

We can split the value of the integral into segments, i.e:

integral over -infinity < t < infinity = the sum of

  • integral over -infinity < t ≤ A1
  • integral over A1 ≤ t ≤ A2
  • integral over A2 ≤ t ≤ A3
  • ...
  • integral over AN-1 ≤ t < infinity

We will calculate the value of the integral over the time segment integral over Ai ≤ t ≤ Ai+1. There are 2 cases:

Case 1: exactly one of g(Ai) or g(Ai+1) is above line y = Bi

Without loss of generality, let g(Ai) < Bi. Then the value of g(t) in this segment can be represented as below.

g(Ai+1)...................
                         /
                        /x
                       /xx
Bi...... ---===========---
         xx/
         x/
         /
g(Ai)...

where characters ‘/’ and ‘=’ denotes the graph for g(t), and the area with 'x’s denotes the area of the integral in this segment.

Case 2: Both of g(Ai) and g(Ai+1) are above line y = Bi or below line y = Bi.

Without loss of generality, let g(Ai) > Bi and g(Ai+1) > Bi. Then the value of g(t) in this segment can be represented as below:

2.1

g(Ai+1)....................
g(Ai)....                 /
         \               /x
         x\             /xx
         xx\           /xxx
Bi...... ---===========----

or

2.2

g(Ai+1).........
g(Ai)....      /
         \    /x
         x\  /xx
         xx\/xxx
         xxxxxxx
         xxxxxxx
Bi...... -------

The degenerate cases g(Ai) = Bi or g(Ai+1) = Bi can be considered as one of the above cases.

If we denote z = g(Ai) - Bi, y = g(Ai+1) - Bi, and d = Ai+1 - Ai, then:

  • The area of Case 1 and Case 2.1 is z^2 + y^2.
  • The area of Case 2.2 is ((z - y)^2 - d^2) / 2 + d × |z+y|.

(Of course, by area we mean the actual area multiplied by 2.)

Case 1 and Case 2.1 occur iff |z + y| ≤ d, while Case 2 occur iff |z + y| > d.

The value of integral over segment -infinity < t < Ai is (g(A1) - B0)^2. Similary, the value of integral over segment AN-1 ≤ t < infinity is (g(AN-1) - BN-1)^2. By doing some math, we can combine all cases in a single formula: area = x^2 + y^2 - (max(|x + y| - d, 0))^2 / 2.

Therefore, we have the value of the integral over all t:

f(x) = Area(-infinity, A1) + Area(A1, A2) + … + Area(AN-1, infinity)

where x is the vector <g(A1), g(A2), …, g(AN-1)>.

Minimizing the integral

As the problem say, we would like to minimize the value of f(x). Now, it can be seen that f(x) is a convex function. More specifically, for each i, when we fix g(Aj) for all j ≠ i and take the function to g(Ai), the function (of one variable) is a convex function.

Being a convex function, we can determine its lowest point using ternary search. However, since the input is a vector, we must do nested ternary searches, like this:

function search(i, x):
    if i == N:
        return the value of f(x)
    else:
        L = 0
        R = 20130120
        for it = 0; it < IT; it++:
            M1 = (2 × L + R) / 3
            M2 = (L + 2 × R) / 3
            x[i] = M1
            sM1 = search(i+1, x)
            x[i] = M2
            sM2 = search(i+1, x)
            if sM1 > sM2:
                L = M1
            else:
                R = M2

where IT is some constant we define to limit the number of iterations in each ternary search. The answer to the problem is search(1, <>). Unfortunately, this solution runs in O(IT^(N-1)) which is too much.

We can improve the above solution by doing the ternary search only on g(A1), g(A3), g(A5), … therefore halving the number of variables. Each of the remaining variable g(Ai) can be computed using g(Ai-1) and g(Ai+1). More precisely, we must have g(Ai) for which the value of

Area(Ai-1, Ai) + Area(Ai, Ai+1)

is minimized. Now the function has only one unknown and moreover it is a quadratic function. We can use a ternary search again to get the minimum value or since it is quadratic use some O(1) formula.

The time complexity of this solution is O(IT^(N-1)/2).

AUTHOR’S AND TESTER’S SOLUTIONS

Author’s solution can be found here.
Tester’s solution can be found here.

1 Like