 # 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 tks,I will try to understand it 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*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,
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
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 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