# OPTSSET - Editorial

Practice

Contest

Author: Trung Nguyen

Tester: Oleksandr Kulkov

Editorialist: Oleksandr Kulkov

MEDIUM

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

### RELATED PROBLEMS:

[333]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[444]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server