PROBLEM LINK:
Author: Trung Nguyen
Tester: Oleksandr Kulkov
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM
PREREQUISITES:
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
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
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.
- D(j_1, j_2) can be found by binary search in O(\log n).
- 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.
- 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
and
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.
