Beginners Special 1.0 problems

@admin plz move the following problem of Beginners Special 1.0 to practice section:
https://www.codechef.com/BGS12020/problems/BSPDP3

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 :slight_smile:

tks,I will try to understand it :slight_smile:

https://paste.ubuntu.com/p/vTGQqRgkr5/
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:
https://codeforces.com/blog/entry/43440

https://paste.ubuntu.com/p/qtMYxVkS7N/

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[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 https://pastebin.com/7CjFy7Kw
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…

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…

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 :sweat_smile:
Really Sorry for inconvenience.

fixed?

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