What algorithm can I use in this liner function question?

Question

Firstly, I would like to apologise for my bad English. when I submit the code below to DomJudge I got TimeLimit ERROR. I can't think of ways to solve this question albeit I searched all over the internet and still couldn't find a solution. Can someone give me a hint?

Question:

Here are N linear function fi(x) = aix + bi, where 1 ≤ i ≤ N。Define F(x) = maxifi(x). Please compute
the following equation for the input c[i], where 1 ≤ i ≤ m.   
**Σ(i=1 to m) F(c[i])**  
For example, given 4 linear function as follows. f1(x) = –x, f2 = x, f3 = –2x – 3, f4 = 2x – 3. And the
input is c[1] = 4, c[2] = –5, c[3] = –1, c[4] = 0, c[5] = 2. We have F(c[1]) = 5, F(c[2]) = 7, F(c[3])
= 1, F(c[4]) = 0, F(c[5]) = 2. Then,  
**Σ(i=1 to 5)𝐹(𝑐[𝑖])
= 𝐹(𝑐[1]) + 𝐹(𝑐[2]) + 𝐹(𝑐[3]) + 𝐹(𝑐[4]) + 𝐹([5]) = 5 + 7 + 1 + 0 + 2 = 15** 

Input Format:

The first line contains two positive integers N and m. The next N lines will contain two integers ai
and bi, and the last line will contain m integers c[1], c[2], c[3],…, c[m]. Each element separated by
a space.  

Output Format:
Please output the value of the above function.

question image:https://i.sstatic.net/6HeaA.png

Sample Input:

4 5  
 -1 0  
 1 0  
 -2 -3  
 2 -3  
 4 -5 -1 0 2  

Sample Output:

 15

My Program

 #include <iostream>
    #include <vector>

struct L
{
    int a;
    int b;
};

int main()
{
    int n{ 0 };
    int m{ 0 };
    while (std::cin >> n >> m)
    {
        //input
        std::vector<L> arrL(n);
        for (int iii{ 0 }; iii < n; ++iii)
        {
            std::cin >> arrL[iii].a >> arrL[iii].b;
        }
        //find max in every linear polymore
        int answer{ 0 };
        for (int iii{ 0 }; iii < m; ++iii)
        {
            int input{ 0 };
            int max{ 0 };
            std::cin >> input;
            max = arrL[0].a * input + arrL[0].b;
            for (int jjj{ 1 }; jjj < n; ++jjj)
            {
                int tmp{arrL[jjj].a * input + arrL[jjj].b };
                if (tmp > max)max = tmp;
            }
            answer += max;
        }
        //output
        std::cout << answer << '\n';
    }
    return 0;
}

Answer 1

Your solution is O(n*m).

A faster solution is obtained by iteratively determinating the "dominating segments", and the correspong crossing points, called "anchors" in the following.

Each anchor is linked to two segments, on its left and on its right.

The first step consists in sorting the lines according to the a values, and then adding each new line iteratively.
When adding line i, we know that this line is dominant for large input values, and must be added (even if it will be removed in the following steps). We calculate the intersection of this line with the previous added line:

• if the intersection value is higher than the rightmost anchor, then we add a new anchor corresponding to this new line
• if the intersection value is lower than the rightmost anchor, then we know that we have to suppress this last anchor value. In this case, we iterate the process, calculating now the intersection with the right segment of the previous anchor.

Complexity is dominated by sorting: O(nlogn + mlogm). The anchor determination process is O(n).

When we have the anchors, then determining the rigtht segment for each input x value is O(n+ m). If needed, this last value could be further reduced with a binary search (not implemented).

Compared to first version of the code, a few errors have been corrected. These errors were concerning some corner cases, with some identical lines at the extreme left (i.e. lowest values of a). Besides, random sequences have been generated (more than 10^7), for comparaison of the results with those obtained by OP's code. No differences were found. It is likely that if some errors remain, they correspond to other unknown corner cases. The algorithm by itself looks quite valid.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

//  lines of equation `y = ax + b`
struct line {
    int a;
    int b;
    friend std::ostream& operator << (std::ostream& os, const line& coef) {
        os << "(" << coef.a << ", " << coef.b << ")";
        return os;
    }
};

struct anchor {
    double x;
    int segment_left;
    int segment_right;
    friend std::ostream& operator << (std::ostream& os, const anchor& anc) {
        os << "(" << anc.x << ", " << anc.segment_left << ", " << anc.segment_right << ")";
        return os;
    }
};

//  intersection of two lines
double intersect (line& seg1, line& seg2) {
    double x;
    x = double (seg1.b - seg2.b) / (seg2.a - seg1.a);
    return x;
}

long long int max_funct (std::vector<line>& lines, std::vector<int> absc) {
    long long int sum = 0;
    auto comp = [&] (line& x, line& y) {
        if (x.a == y.a) return x.b < y.b;
        return x.a < y.a;
    };
    std::sort (lines.begin(), lines.end(), comp);
    std::sort (absc.begin(), absc.end());

    // anchors and dominating segments determination
    
    int n = lines.size();
    std::vector<anchor> anchors (n+1);
    int n_anchor = 1;
    
    int l0 = 0;
    while ((l0 < n-1) && (lines[l0].a == lines[l0+1].a)) l0++;
    int l1 = l0 + 1;

    if (l0 == n-1) {
        anchors[0] = {0.0, l0, l0};
    } else {
        while ((l1 < n-1) && (lines[l1].a == lines[l1+1].a)) l1++;
        double x = intersect(lines[l0], lines[l1]);
        anchors[0] = {x, l0, l1};
        
        for (int i = l1 + 1; i < n; ++i) {
            if ((i != (n-1)) && lines[i].a == lines[i+1].a) continue;
            double x = intersect(lines[anchors[n_anchor-1].segment_right], lines[i]);
            if (x > anchors[n_anchor-1].x) {
                anchors[n_anchor].x = x;
                anchors[n_anchor].segment_left = anchors[n_anchor - 1].segment_right;
                anchors[n_anchor].segment_right = i;
                n_anchor++;
            } else {
                n_anchor--;
                if (n_anchor == 0) {
                    x = intersect(lines[anchors[0].segment_left], lines[i]);
                    anchors[0] = {x, anchors[0].segment_left, i};
                    n_anchor = 1;
                } else {
                    i--;
                }
            }
        }
    }
    
    // sum calculation
    
    int j = 0;      // segment index (always increasing)
    for (int x: absc) {
        while (j < n_anchor && anchors[j].x < x) j++;
        line seg;
        if (j == 0) {
            seg = lines[anchors[0].segment_left];
        } else {
            if (j == n_anchor) {
                if (anchors[n_anchor-1].x < x) {
                    seg = lines[anchors[n_anchor-1].segment_right];
                } else {
                    seg = lines[anchors[n_anchor-1].segment_left];
                }
            } else {                
                seg = lines[anchors[j-1].segment_right];
            }
        }
        sum += seg.a * x + seg.b;
    }
    
    return sum;
}

int main() {
    std::vector<line> lines = {{-1, 0}, {1, 0}, {-2, -3}, {2, -3}};
    std::vector<int> x = {4, -5, -1, 0, 2};
    long long int sum = max_funct (lines, x);
    std::cout << "sum = " << sum << "\n";
    
    lines = {{1,0}, {2, -12}, {3, 1}};
    x = {-3, -1, 1, 5};
    sum = max_funct (lines, x);
    std::cout << "sum = " << sum << "\n";
}   

One possible issue is the loss of information when calculating the double x corresponding to line intersections, and therefoe to anchors. Here is a version using Rational to avoid such loss.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
    
struct Rational {
    int p, q;
    Rational () {p = 0; q = 1;}
    Rational (int x, int y) {
        p = x;
        q = y;
        if (q < 0) {
            q -= q;
            p -= p;
        }
    }
    Rational (int x) {
        p = x;
        q = 1;
    }
    friend std::ostream& operator << (std::ostream& os, const Rational& x) {
        os << x.p << "/" << x.q;
        return os;
    }
    friend bool operator< (const Rational& x1, const Rational& x2) {return x1.p*x2.q < x1.q*x2.p;}
    friend bool operator> (const Rational& x1, const Rational& x2) {return x2 < x1;}
    friend bool operator<= (const Rational& x1, const Rational& x2) {return !(x1 > x2);}
    friend bool operator>= (const Rational& x1, const Rational& x2) {return !(x1 < x2);}
    friend bool operator== (const Rational& x1, const Rational& x2) {return x1.p*x2.q == x1.q*x2.p;}
    friend bool operator!= (const Rational& x1, const Rational& x2) {return !(x1 == x2);}
};

//  lines of equation `y = ax + b`
struct line {
    int a;
    int b;
    friend std::ostream& operator << (std::ostream& os, const line& coef) {
        os << "(" << coef.a << ", " << coef.b << ")";
        return os;
    }
};

struct anchor {
    Rational x;
    int segment_left;
    int segment_right;
    friend std::ostream& operator << (std::ostream& os, const anchor& anc) {
        os << "(" << anc.x << ", " << anc.segment_left << ", " << anc.segment_right << ")";
        return os;
    }
};

//  intersection of two lines
Rational intersect (line& seg1, line& seg2) {
    assert (seg2.a != seg1.a);
    Rational x = {seg1.b - seg2.b, seg2.a - seg1.a};
    return x;
}

long long int max_funct (std::vector<line>& lines, std::vector<int> absc) {
    long long int sum = 0;
    auto comp = [&] (line& x, line& y) {
        if (x.a == y.a) return x.b < y.b;
        return x.a < y.a;
    };
    std::sort (lines.begin(), lines.end(), comp);
    std::sort (absc.begin(), absc.end());
    
    // anchors and dominating segments determination
    
    int n = lines.size();
    std::vector<anchor> anchors (n+1);
    int n_anchor = 1;
    
    int l0 = 0;
    while ((l0 < n-1) && (lines[l0].a == lines[l0+1].a)) l0++;
    int l1 = l0 + 1;

    if (l0 == n-1) {
        anchors[0] = {0.0, l0, l0};
    } else {
        while ((l1 < n-1) && (lines[l1].a == lines[l1+1].a)) l1++;
        Rational x = intersect(lines[l0], lines[l1]);
        anchors[0] = {x, l0, l1};
        
        for (int i = l1 + 1; i < n; ++i) {
            if ((i != (n-1)) && lines[i].a == lines[i+1].a) continue;
            Rational x = intersect(lines[anchors[n_anchor-1].segment_right], lines[i]);
            if (x > anchors[n_anchor-1].x) {
                anchors[n_anchor].x = x;
                anchors[n_anchor].segment_left = anchors[n_anchor - 1].segment_right;
                anchors[n_anchor].segment_right = i;
                n_anchor++;
            } else {
                n_anchor--;
                if (n_anchor == 0) {
                    x = intersect(lines[anchors[0].segment_left], lines[i]);
                    anchors[0] = {x, anchors[0].segment_left, i};
                    n_anchor = 1;
                } else {
                    i--;
                }
            }
        }
    }
    
    
    // sum calculation
    
    int j = 0;      // segment index (always increasing)
    for (int x: absc) {
        while (j < n_anchor && anchors[j].x < x) j++;
        line seg;
        if (j == 0) {
            seg = lines[anchors[0].segment_left];
        } else {
            if (j == n_anchor) {
                if (anchors[n_anchor-1].x < x) {
                    seg = lines[anchors[n_anchor-1].segment_right];
                } else {
                    seg = lines[anchors[n_anchor-1].segment_left];
                }
            } else {                
                seg = lines[anchors[j-1].segment_right];
            }
        }
        sum += seg.a * x + seg.b;
    }
    
    return sum;
}

long long int max_funct_op (const std::vector<line> &arrL, const std::vector<int> &x) {
    long long int answer = 0;
    int n = arrL.size();
    int m = x.size();
    for (int i = 0; i < m; ++i) {
        int input = x[i];
        int vmax = arrL[0].a * input + arrL[0].b;
        for (int jjj = 1; jjj < n; ++jjj) {
            int tmp = arrL[jjj].a * input + arrL[jjj].b;
            if (tmp > vmax) vmax = tmp;
        }
        answer += vmax;
    }   
    return answer;
}

int main() {
    long long int sum, sum_op;
    std::vector<line> lines = {{-1, 0}, {1, 0}, {-2, -3}, {2, -3}};
    std::vector<int> x = {4, -5, -1, 0, 2};
    sum_op = max_funct_op (lines, x);
    sum = max_funct (lines, x);
    std::cout << "sum = " << sum << "  sum_op = " << sum_op << "\n";
}

Answer 2

To reduce the time complexity from O(n*m) to something near O(nlogn), we need to order the input data in some way.

The m points where the target function is sampled can be easily sorted using std::sort, which has an O(mlogm) complexity in terms of comparisons.

Then, instead of searching the max between all the lines for each point, we can take advantage of a divide-and-conquer technique.

Some considerations can be made in order to create such an algorithm.

• If there are no lines or no sample points, the answer is 0.

• If there is only one line, we can evaluate it at each point, accumulating the values and return the result. In case of two lines we could easily accumulate the max between two values. Searching for the intersection and then separating the intervals to accumulate only the correct value may be more complicated, with multiple corner cases and overflow issues.

• A recursive function accepting a list of lines, points and two special lines left and right, may start by calculating the middle point in the set of points. Then it could find the two lines (or the only one) that have the greater value at that point. One of them also have the greatest slope between all the ones passing for that maximum point, that would be the top "right". The other one, the top "left" (which may be the same one), have the least slope.

• We can partition all the remaining lines in three sets.

  1. All the lines having a greater slope than the "top right" one (but lower intercept). Those are the ones that we need to evaluate the sum for the subset of points at the right of the middle point.
  2. All the lines having a lower slope than the "top left" one (but lower intercept). Those are the ones that we need to evaluate the sum for the subset of points at the left of the middle point.
  3. The remaining lines, that won't partecipate anymore and can be removed. Note this includes both "top right" and "top left".

• Having splitted both the points and the lines, we can recurively call the same function passing those subsets, along with the previous left line and "top left" as left and right to the left, and the "top right" line with the previous right as left and right to the right.

• The return value of this function is the sum of the value at the middle point plus the return values of the two recursive calls.

• To start the procedure, we don't need to evaluate the correct left and right at the extreme points, we can use an helper function as entry point which sorts the points and calls the recursive function passing all the lines, the points and two dummy values (the lowest possible line, y = 0 + std::numeric_limits<T>::min()).

The following is a possible implementation:

#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric>
#include <limits>

struct Line
{
    using value_type = long;
    using result_type = long long;
    value_type slope;
    value_type intercept;
    auto operator() (value_type x) const noexcept {
        return static_cast<result_type>(x) * slope + intercept;
    }
    static constexpr Line min() noexcept { 
        return { 0, std::numeric_limits<value_type>::min()};
    }
};

auto result_less_at(Line::value_type x)
{
    return [x] (Line const& a, Line const& b) { return a(x) < b(x); };
} 

auto slope_less_than(Line::value_type slope)
{
    return [slope] (Line const& line) { return line.slope < slope; };
}

auto slope_greater_than(Line::value_type slope)
{
    return [slope] (Line const& line) { return slope < line.slope; };
} 

auto accumulate_results(Line const& line)
{
    return [line] (Line::result_type acc, Line::value_type x) {
        return acc + line(x);
    };
}

struct find_max_lines_result_t
{
    Line::result_type y_max;
    Line left, right;
};

template< class LineIt, class XType > 
auto find_max_lines( LineIt first_line, LineIt last_line
                   , Line left, Line right
                   , XType x )
{
    auto result{ [left, right] (const auto max_left, const auto max_right)
        -> find_max_lines_result_t {
            if ( max_left < max_right ) 
                return { max_right, right, right };
            else if ( max_right < max_left )
                return { max_left, left, left };
            else
                return { max_left, left, right };
        }(left(x), right(x))
    };
    
    std::for_each( first_line, last_line
                 , [x, &result] (Line const& line) mutable {
                        auto const y{ line(x) };
                        if ( y == result.y_max ) {
                            if ( result.right.slope < line.slope )
                                result.right = line;
                            if ( line.slope < result.left.slope )
                                result.left = line;
                        }
                        else if ( result.y_max < y ) {
                            result = {y, line, line};
                        }
                   } );

    return result; 
}

template< class SampleIt > 
auto sum_left_right_values( SampleIt const first_x, SampleIt const last_x
                          , Line const left, Line const right )
{     
    return std::accumulate( first_x, last_x, Line::result_type{},
        [left, right] (Line::result_type acc, Line::value_type x) {
            return acc + std::max(left(x), right(x)); } );
}

template< class LineIt, class XType > 
auto find_max_result( LineIt const first_line, LineIt const last_line
                    , Line const left, Line const right
                    , XType const x )
{
    auto const y_max{ std::max(left(x), right(x)) };
    LineIt const max_line{ std::max_element(first_line, last_line, result_less_at(x)) };
    return max_line == last_line ? y_max : std::max(y_max, (*max_line)(x));  
}

template <class LineIt, class SampleIt> 
auto sum_lines_max_impl( LineIt const first_line, LineIt const last_line, 
                         SampleIt const first_x, SampleIt const last_x,
                         Line const left, Line const right )
{
    if ( first_x == last_x ) { 
        return Line::result_type{};
    }

    if ( first_x + 1 == last_x ) {
        return find_max_result(first_line, last_line, left, right, *first_x);
    }

    if ( first_line == last_line ) {
        return sum_left_right_values(first_x, last_x, left, right);
    }

    auto const mid_x{ first_x + (last_x - first_x - 1) / 2 };

    auto const top{ find_max_lines(first_line, last_line, left, right, *mid_x) };

    auto const right_begin{ std::partition( first_line, last_line
                                          , slope_less_than(top.left.slope) ) };

    auto const right_end{ std::partition( right_begin, last_line
                                        , slope_greater_than(top.right.slope) ) };

    return top.y_max + sum_lines_max_impl( first_line, right_begin
                                         , first_x, mid_x
                                         , left, top.left )
                     + sum_lines_max_impl( right_begin, right_end
                                         , mid_x + 1, last_x
                                         , top.right, right );
}

template <class LineIt, class SampleIt> 
auto sum_lines_max( LineIt first_line, LineIt last_line
                  , SampleIt first_sample, SampleIt last_sample )
{
    if ( first_line == last_line )
        return Line::result_type{};

    std::sort(first_sample, last_sample);

    return sum_lines_max_impl( first_line, last_line
                             , first_sample, last_sample
                             , Line::min(), Line::min() );
}

int main() 
{
    std::vector<Line> lines{ {-1, 0}, {1, 0}, {-2, -3}, {2, -3} };
    std::vector<long> points{ 4, -5, -1, 0, 2 };
    
    std::cout << sum_lines_max( lines.begin(), lines.end()
                              , points.begin(), points.end() ) << '\n';
}

Testable here.