OPTSSET - Editorial

chemthan
editorial
ltime53
maths
medium-hard
optimization

#1

PROBLEM LINK:

Practice

Contest

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

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:


#2

Can you suggest links to similar problems?


#3

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.


#4

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?


#5

@admin takes wrong solution :). Correct one: https://www.codechef.com/viewsolution/16014967 .


#6

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.


#7

Can someone explain what’s the point of using optL and optR as well as best.second in authors solution.


#8

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).


#9

That is really sad :confused:


#10

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


#11

@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.