OPTSSET - Editorial

melfice · October 24, 2017, 5:57am

PROBLEM LINK:

Practice

Contest

Author: Trung Nguyen

Tester: Oleksandr Kulkov

Editorialist: Oleksandr Kulkov

DIFFICULTY:

MEDIUM

PREREQUISITES:

None

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 TODO

EXPLANATION:

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.

Let’s consider quadratic solution to begin with. 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 such sequence exist iff d_i+|p_i-p_1|>0 for some i.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found [here][333].
Tester’s solution can be found [here][444].