PROBLEM LINK:
Contest
Practice
AUTHOR: hackerwizard
DIFFICULTY:
Medium
PREREQUISITES:
Convex Hul Optimization, Segment Tree
PROBLEM
You are given x and p and you need to determine the maximum value of
$reliability[i][j] * x + experience[i][j]$for i between l to r.
QUICK EXPLANATION:
This can be done maintaining a convex of hull of lines on each node of a segment tree.
EXPLANATION:
If you don’t know what is convex hull optimization, I recommend reading from here. Let us say y = reliability[i][p] * x + experience[i][j], then we will have n lines and we need to select a line which has maximum value for a given x and every time experience[i][j] changes for some i^th batsman at j^th position we simply add a line with the new experience value. We don’t need to delete the line with old experience value because the old line can never yield a higher value of y for a given x than the new line. Maintaining and evaluating these lines can be done using convex hull optimization trick. But the question requires us to find the answer not for all the lines but only for the lines with index between l to r. We can do this using a segment tree. In each node of this segment tree will we store a convex hull of the lines in that particular range. Thereafter update and query can be done in O(logn).
Author’s Solution: Solution