STRQUER - Editorial

melfice · November 27, 2017, 9:10am

PROBLEM LINK:

Practice
Contest

Author: Misha Chorniy
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov

DIFFICULTY:

MEDIUM

PREREQUISITES:

Treap or segment tree

PROBLEM:

You’re given array A of N numbers. You have to make some connections between those numbers in such way that any number is connected to at least one another one. Cost of making a connection between numbers x and y is |x-y|. Also you have to maintain inserting and erasing elements from the set.

QUICK EXPLANATION:

Maintain dp[l][r][2][2] which is answer to segment [l,r] with indicators of whether endpoints connected with any number inside the segment. Keep it in treap or segment tree to recover the answer.

EXPLANATION:

First of all we should note that optimal connection is segment connecting minimum and maximum numbers from the set with some drop off segments connecting two consequent points.

If we would like to solve the problem in static case we can consider dynamic programming: dp[n][2] with state is number of considerent points (in sorted order) and boolean indicator of either we connected n^{th} number with previous. Then

\begin{cases}dp[i][0] = dp[i-1][1],\\dp[i][1]=|A_i-A_{i-1}|+\min(dp[i-1][1],dp[i-1][0])\end{cases}

To solve this particular problem however we should consider a bit more general dynamic programming dp[l][r][2][2] which is the answer to subset of numbers from segment [l,r] having two indicators of whether corresponding endpoints are connected with the number inside segment. Now assume that for some l< m< r we know dp[l][m] and dp[m][r] (answers for r-l\leq 2 can be handled manually). Then we can say that

dp[l][r][a][b] = \min\limits_{\substack{x,y\\x|y=1}}\{dp[l][m][a][x] + dp[m][r][y][b]\}

Indeed we can’t allow case when m is connected neither to m-1 nor to m+1 but all other cases are okay for us and they cover everything. To solve the problem we should note that we don’t need to calculate values for all [l,r]. Actually only ones corresponding to some vertices of treap or segment tree built over given numbers are sufficient. And luckily we can recalculate that dynamic programming while returning from recursion in this trees. In treap it would be straightforward to maintain the same trick in segment tree one should firstly compress numbers or maintain its dynamic version.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.