×

# OPTSSET - Editorial

Author: Trung Nguyen
Tester: Oleksandr Kulkov
Editorialist: Oleksandr Kulkov

MEDIUM

DP optimizations

# PROBLEM:

You're given convex polygon $p_1, \dots, p_n$ and each point has weight $w_i$. Choose subsequence of its vertices such that $\dfrac{|p_{i_1}-p_{i_2}|+\dots+|p_{i_k}-p_{i_1}|}{w_{i_1}+\dots+w_{i_k}}$ is maximized and $i_1=1$.

# QUICK EXPLANATION:

Use binary search to reduce the problem from $\max \dfrac a b$ to $a-b\cdot c >^? 0$. After that use some DP optimization to check this.

# EXPLANATION:

Basic ideas: There is common trick to solve problems in which one is asked to optimize fraction. If we will make binary search of answer then we will just have to check whether there exist any $\{i_1,\dots,i_k\}$ such that $(|p_{i_1}-p_{i_2}|+\dots+|p_{i_k}-p_{i_1}|)-(w_{i_1}'+\dots+w_{i_k}')>0$. Here $w_i'=m \cdot w_i$ where $m$ is the answer we want to check. Indeed instead if trying to find sequence for which $\dfrac a b > c$ we will try to find sequence for which $a - bc > 0$.

Let's consider $O(n^2)$ solution first. Let $d_i=\max[(|p_{i_1}-p_{i_2}|+\dots+|p_{i_{k-1}}-p_{i_k}|)-(w_{i_1}+\dots+w_{i_{k}})]$. Then we can see that

$$d_i=\max\limits_{j < i} (d_j + |p_i-p_j| - w_i)$$

and sequence exists iff $d_i+|p_i-p_1|>0$ for some $i$. Thus we can solve problem in $O(n^2 \log n)$ for first two subtasks and $40$ points.

DP optimzation: The generic solution to such kind of problems can be found in the following article. In this editorial however the different kind of solution will be described.

Let $score_{j}(x)=d_j+|x-p_j|$. Consider some $j_1, j_2:score_{j_1}(p_i)\geq score_{j_2}(p_i)$. Let $D(j_1,j_2)$ be the first $i'>i$ such that $score_{j_1}(p_{i'}) < score_{j_2}(p_{i'})$. We can see that set of points for which $$score_{j_1}(x)= score_{j_2}(x) \Leftrightarrow |x-p_{j_1}|-|x-p_{j_2}|=d_{j_2}-d_{i_1}$$

Is hyperbolic line. Thus it splits our polygon in two parts, one containing $p_{j_1}$ and the second containing $p_{j_2}$. We can make some useful observations here.

1. $D(j_1, j_2)$ can be found by binary search in $O(\log n)$.
2. If $p_a$ at some point became worse than $p_b$ after being better then it will be worse till the very end. Thus position of optimal $p_j$ only increases when we increase $i$.
3. If $D(a, b) > D(b, c)$ then $b$ can never be optimal $j$ since it is covered by $b$ before it can cover $a$.

Given this we can maintain monotonic queue $q$ of candidats to be the best $j$. Such that $$score_{q_1}(p_i)>score_{q_2}(p_i)>\dots>score_{q_k}(p_i)$$

and

$$D(q_1,q_2)< D(q_2,q_3)< \dots< D(q_{k-1},q_k)$$

If we keep this then optimal candidate is always kept in the queue and order of scores can change only between first two elements of queue. If it happened, we simply pop first element from queue. Also before adding new element to queue we pop elements from the back of queue until second kind of inequality holds. Thus all operations with queue will take $O(n \log n)$ time overall which gives us $O(n\log^2 n)$ solution to the initial problem.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

# RELATED PROBLEMS:

4★melfice
811737
accept rate: 0%

19.7k350498541

 1 Can I ask why many submissions like https://www.codechef.com/viewsolution/15995306 a simple Greedy DP solution which I think should not work mathematically have passed for 40 points? Is it weak test cases or is there a proof for this Greedy solution? answered 30 Oct '17, 20:56 365●1●9 accept rate: 0% 2 The test cases are just weak, see this solution https://www.codechef.com/viewsolution/15995539 it only takes subsets of size 2 into account (i.e. point #1 and one other point). (30 Oct '17, 21:21) That is really sad :/ (30 Oct '17, 23:09) Another one (mine :P) https://www.codechef.com/viewsolution/15993038 PS: My Correct solution O(N^2) for 40 points https://www.codechef.com/viewsolution/16013985 (30 Oct '17, 23:52) @harrycoda had there been any proof for this greedy solution to work, these solutions would have got 100 points, not 40. In last sub task, there were test cases to fail this greedy approach. (30 Oct '17, 23:56)
 1 @admin takes wrong solution :). Correct one: https://www.codechef.com/viewsolution/16014967 . answered 30 Oct '17, 21:03 7★chemthan 191●3 accept rate: 12%
 0 Can you suggest links to similar problems? answered 30 Oct '17, 18:35 111●1●6 accept rate: 11%
 0 The links to Author's solution and Tester's solution aren't working. It is giving some kind of Access Denied error. Is it me or everyone is facing this issue? All the editorials of ltime53 are having same Issues. answered 30 Oct '17, 19:11 165●9 accept rate: 8%
 0 We can see that set of points for which: scorej1(x)=scorej2(x)⇔|x−pj1|−|x−pj2|=dj2−di1. I think there should be dj1 instead di1. answered 06 Nov '17, 23:29 31●2 accept rate: 0%
 0 Can someone explain what's the point of using optL and optR as well as best.second in authors solution. answered 02 Feb '18, 13:55 3★cope 1 accept rate: 0%
 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,499
×1,237
×1,179
×230
×72
×64

question asked: 24 Oct '17, 18:40

question was seen: 1,077 times

last updated: 02 Feb '18, 13:55