You are not logged in. Please login at www.codechef.com to post your questions!

×

OPTSSET - Editorial

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:

asked 24 Oct '17, 18:40

melfice's gravatar image

4★melfice
811637
accept rate: 0%

edited 30 Oct '17, 13:44

admin's gravatar image

0★admin ♦♦
19.6k349497539


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?

link

answered 30 Oct '17, 20:56

harrycoda's gravatar image

5★harrycoda
29519
accept rate: 0%

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) alex_2oo87★

That is really sad :/

(30 Oct '17, 23:09) harrycoda5★

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

(30 Oct '17, 23:52) taran_14076★

@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) taran_14076★

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

link

answered 30 Oct '17, 21:03

chemthan's gravatar image

7★chemthan
1913
accept rate: 12%

edited 30 Oct '17, 21:04

Can you suggest links to similar problems?

link

answered 30 Oct '17, 18:35

gagan86nagpal's gravatar image

4★gagan86nagpal
11116
accept rate: 11%

edited 30 Oct '17, 18:37

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.

link

answered 30 Oct '17, 19:11

vatsalsura's gravatar image

1★vatsalsura
1659
accept rate: 8%

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.

link

answered 06 Nov '17, 23:29

daniel_1999's gravatar image

6★daniel_1999
212
accept rate: 0%

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

link

answered 02 Feb, 13:55

cope's gravatar image

3★cope
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,119
×1,188
×1,156
×228
×72
×64

question asked: 24 Oct '17, 18:40

question was seen: 1,020 times

last updated: 02 Feb, 13:55