@admin plz move the following problem of Beginners Special 1.0 to practice section:
1 Like
This problem is really difficult, so where is the solution?
1 Like
This problem is not very hard…observe that you are given ‘m’ lines with slopes B[j] and intercept C[j]. Further you are given ‘n’ points A[i] and for each point you need to find the line which minimizes the value for that point. You can study the algorithm here:
After that you just need a segment tree to query the minimum value in different ranges. I don’t know why I am getting wrong answer…
According to my contacts it was done using sparse table. I have the solution but unable to understand 
tks,I will try to understand it
I am also getting WA…Infact there is no successful submission…Also you need to change your ternary search. See this:
Hey, so solution was to convert given statement into question that given n lines of form y = m*x + c, where m = B[j] & c = C[j].
Now, for each x which is A[i], you have to find minimum value of y which we can get from n lines.
now sort lines in decreasing order of slope, and x in increasing order and start from smaller x,
you will notice that if B[0]*x+C[0] is greater than B[1] * x + C[1] then for all A[i] greater than x it will be valid, so remove those as go downward.
you can go through solution,
here #include<bits/stdc++.h>using namespace std;#pragma GCC optimize("Ofast") - Pastebin.com
if their are any issues in solution pls highlight.
Your logic is incorrect…haven’t you studied the algorithms for convex hull??
The test case where your logic fails is:
1 3
10
10 30 50
-1000 400 2
1
1 1
Correct Answer -900
Your Output 502
The problem is you can’t simply sort the lines and query the answer…you need to consider the previous lines which have no significance after inserting a new line…See the gfg link which I mentioned above…
Because test cases are wrong…the setter’s solution is incorrect…And your solution looks correct…
1 Like
But i saw u got AC without using convex hull.
Lol…that’s setter’s solution only…My solution(WA but I think is correct) is this:
https://www.codechef.com/viewsolution/35252779
1 Like
Hey you are correct solution was incorrect, sorry for inconvenience, i had thought if they ware sorted initially then convex hull will be maintained 
Really Sorry for inconvenience.
fixed？
Hey Test Cases are fixed now, really sorry for inconvenience…
hey ken thanks for this question.
I read this concept/trick a long ago but didn’t apply anywhere.
Thanks for such a classic