PROBLEM LINK:Author: Trung Nguyen 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 $ab\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_{k1}}p_{i_k})(w_{i_1}+\dots+w_{i_{k}})]$. Then we can see that $$d_i=\max\limits_{j < i} (d_j + p_ip_j  w_i)$$ and sequence exists iff $d_i+p_ip_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+xp_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 xp_{j_1}xp_{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.
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_{k1},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. RELATED PROBLEMS:asked 24 Oct '17, 18:40

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

@admin takes wrong solution :). Correct one: https://www.codechef.com/viewsolution/16014967 . answered 30 Oct '17, 21:03

Can you suggest links to similar problems? answered 30 Oct '17, 18:35

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

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

Can someone explain what's the point of using optL and optR as well as best.second in authors solution. answered 02 Feb, 13:55
