×

PDELIV - Editorial

Author: Full name Tester: Full name Editorialist: Oleksandr Kulkov

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.

This question is marked "community wiki".

4★melfice
811737
accept rate: 0%

19.7k350498541

 1 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) . answered 19 Jul '18, 18:26 298●9 accept rate: 8% 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. (20 Jul '18, 01:02) melfice4★ 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. (20 Jul '18, 01:53)
 0 "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! :) answered 19 Jul '18, 16:39 15.2k●1●18●60 accept rate: 18% 5 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$ (19 Jul '18, 17:10)
 0 "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. answered 19 Jul '18, 17:31 0●4 accept rate: 0% 1 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... (19 Jul '18, 21:25) 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... (19 Jul '18, 21:28) Note:- but if any only if know won't vary according to pizzeria we select... it can change with customer... (19 Jul '18, 21:33) 1 Thanks @l_returns (20 Jul '18, 08:14)
 0 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. answered 19 Jul '18, 18:21 298●9 accept rate: 8% You should have tried with a block size greater than root(n) (19 Jul '18, 21:44) apptica5★ I tried still it didn't work. (20 Jul '18, 01:48)
 0 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
 0 Somebody please give reference from where Convex Hull Trick can be learnt. answered 21 Jul '18, 18:54 4★psycic03 0●1 accept rate: 0% (22 Jul '18, 00:07) Thank you :) (22 Jul '18, 20:21) psycic034★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,498
×1,237
×120

question asked: 18 Jul '18, 06:35

question was seen: 1,547 times

last updated: 22 Jul '18, 20:21