This problem is really difficult, so where is the solution?
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
this is my code,but get wronganswer…
I am also getting WA…Infact there is no successful submission…Also you need to change your ternary search. See this:
it’s also wa…plz ken_ can give us a corret answer…
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*x+C is greater than B * x + C then for all A[i] greater than x it will be valid, so remove those as go downward.
you can go through solution,
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:
10 30 50
-1000 400 2
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…
I don’t know why my solution is getting wa link
Because test cases are wrong…the setter’s solution is incorrect…And your solution looks correct…
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:
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.
Hey Test Cases are fixed now, really sorry for inconvenience…
Hey, editorials for beginners special 1.0 are out. LINK
hey ken thanks for this question.
I read this concept/trick a long ago but didn’t apply anywhere.
Thanks for such a classic