PROBLEM LINK:
Div 1
Div 2
Practice
Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Convex hull trick, segment tree
PROBLEM:
There are n pizzerias located on positions s_i and m customers located on positions c_i. All pizzerias have distinct positions. Delivering pizza from point x_1 to point x_2 costs (x_1-x_2)^2, additionally each pizzeria has value p_i such that all pizza from that pizzeria cost additionaly p_i.
For each customer you have a list of pizzerias such that this customer won’t order from those pizzerias. You have to find for each customer amount of money they will spend for pizza delivery.
QUICK EXPLANATION:
You can assume that deletion of some pizzeria will lead to splitting of pizzeria set into k+1 continuous subsets, which you can compute independently using segment tree. You should also note that inside subset it’s simply minimization of linear functions, thus you can build convex hull of corresponding linear functions in each vertex of segment tree.
EXPLANATION:
First of all we should note that to deliver pizza from i-th pizzeria to any position x we will have to pay p_i+(s_i-x)^2 = (p_i+s_i^2)-2s_i \cdot x+x^2. Since coefficient near x^2 is 1 for all pizzerias we can ignore x^2 part at all and assume that we’re dealing with linear functions of cost: f_i(x) = (p_i+s_i^2)-2s_i \cdot x.
If k=0 for all queries we just have to find linear function with minimum value for set of points. Thus we certainly look for some modification of convex hull trick. To do this we should note that deletion of k pizzerias split array f_1(x),\dots,f_n(x) into k+1 subarrays. Now to find minimum possible value among remaining functions we can find it in each of these segments and return the minimum among these numbers. To answer such queries in segments we can maintain segment tree having lower envelope of functions which are met in segment of vertex. Please refer to authors solution and some tutorials on convex hull trick and merge-sort tree to understand basic concepts behind the solution. Suggested resources: Convex Hull Trick, Merge-Sort tree (“Saving the entire subarrays in each vertex” section).
ALTERNATIVE SOLUTIONS:
You can directly find k+1 functions having minimum value in given point if you consider function a_i \cdot x + b_i as point (a_i;b_i) and instead of k+1 functions having minimum value in c_i you will have to find k+1 points having minimum scalar product with point (c_i;1). To do this you will have to build convex layers of given points and do stuff like described here. This is much harder than original solution though.
Also you may use sqrt-decomposition instead of segment tree.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
"assume that we’re dealing with linear functions of cost: f_i(x) = (p_i+s_i^2)-2s_i \cdot x. "
Can you please provide justification/intuition here? Like, why? How can we prove that its correct ignoring {x}^{2} and that it wont cause any issue with finding minimas?
Thanks! 
For each query x^{2} is constant… So add them after finding minimum y from all lines f(x) = (p_i + s_i^{2}) - 2*s_i*x
5 Likes
“Since coefficient near x^2 is 1 for all pizzerias we can ignore x^2 part”
What if it wasn’t constant? Can we still ignore it? And simply find minimum of f(x) and add x^2 later?
Thanks in advance.
Sqare root decomposition.
My idea was divide the pizzerias into sq=sqrt(n) buckets. In each bucket maintain the sorted order of the pizzerias according to cost. for each query point X iterate each bucket from beginning to find lowest cost from a non banned pizzeria. Each query can be answered in O(sq+k) time.
For maintaining the sorted order first sort them at the min x value now in each bucket for each i find the point x where where i+1 the pizzeria becomes better than ith and insert this value into a priority queue.
When you reach this x or pass this swap the ith and i+1th pizzerias in the bucket to maintain correct order of costs. now since these have new neighbours find x where the new ith pizzeria becomes better than i-1th pizzeria and when i+2th pizzeria becomes better than i+1th pizzeria insert these values into priority queue and so on. It can be easily shown that once we swap pizzeria i and j(assuming i was above j initially) the ith pizzeria will never come above jth pizzeria again. since there sq elements in each bucket there will be at most sq*sq=n swaps. there will be additional log(n) factor for maintaining the priority queue. So it’ll take O(n*logn) per bucket and total of O(n*root(n)*logn) for all buckets for maintaining the sorted order.
Total time complexity O(n*root(n)*logn+q*root(n)+sum(k)).
Although it should be asymptotically good I couldn’t optimise it enough to fit the TL during contest.
Another idea was consider each pizzeria as 2d point (s_i,sqrt(p_i)) and for each query find the point nearest to (c_i,0) that is not banned using k nearest neighbours (because cost will be same as squared euclidean distance from pizzeria point) .
1 Like
Understand that we ignored s_i^2 as it was constant for each pizzeria… and we ignored x^2 because it is constant for each customer… so yes , we could also ignore k*x^2 if that k is a constant for particular customer… so even if u have different k’s for different customer then too we can ignore it…
1 Like
Because condition is from which pizzeria that customer can get food at a minimum cost… and as x is position of customer it won’t change with which pizzeria u select… so it will always be a constant…
Note:- but if any only if know won’t vary according to pizzeria we select… it can change with customer…
You should have tried with a block size greater than root(n)
Huh, nice. I only thought of reduction to nearest points in terms of scalar product. However, I don’t understand how it is possible to solve this version with good complexity.
I tried still it didn’t work.
If nearest neighbour search can be implemented with log(n) time deletion,query and insertion then for each query we could delete the banned points and query and insert them back it would take O((n+sum(k)+q)*log(n)). However I couldn’t find nearest neighbour search algorithm with fast insertion or deletion. We could use a voronoi diagram to solve 2nd test case but implementing it isn’t easy either.
My solution: for k>sqrt(n) just check all pizzerias. I did convex hull trick sqrt(n) times, removing the minimum envelope. Then I answered queries offline with k<sqrt(n) for each i checked lowest k+1 envelopes.
Somebody please give reference from where Convex Hull Trick can be learnt.