Approach to solve POLY - Nov Long Challenge 17

general
,
1

Can anyone share their approach to solve the POLY problem from Nov Long Challenge 17?

2

I found a discussion on codeforces about the same problem that might help you : Link

1 Like
3

Here some simple idea:

Store records {polinom value, polinom index, X value} in a priority queue, polinom value here is the key. Initilize it with values for X=0.
Now we proceeding all queries in increasing order of X. For each X, while record on the top of the queue was calculated for some older X, recalculate the record with current X and put it back to the queue. If the record’s X value matches, we have the answer.

Thanks to the weak test cases, such code passed without TLE. Don’t even need to add elimination of exactly same polinoms.

2 Likes
4

Can you explain segmk() function in your code?

5

The segmk() is used only for linear polinoms (e.g. where a2=a3=0) and has N*logN run time for that case. The function implements the convex hull trick, see: https://wcipeg.com/wiki/Convex_hull_trick. May be it can be removed from the soulution, I just left it from previous submission.

6

Cool Thanks mate!