0
$\begingroup$

Following question was asked in a online hackathon that has been concluded. Given arrays $A_1,\ldots,A_n$ of length $\ell_1,\ldots,\ell_n$, we want to find cyclically rotate each array in a way which maximizes $$ \sum_{i=1}^{n-1} i|A_i[\ell_i] - A_{i+1}[1]|. $$

For example, on input $2,3,1 \mid 3,2 \mid 4,5$ the best cyclic rotation is $2,3,1 \mid 3,2 \mid 5,4$, and so the answer is $1|1-3| + 2|2-5| = 8$.

There could be up to $10^5$ arrays, and the sum of all elements in all arrays can be at most $10^6$.

I tried solving this by focusing on the two last arrays, but this turned out to be the wrong approach. I am unable to figure out the correct one. How can this be calculated efficiently?

$\endgroup$
  • $\begingroup$ Any assumption on the size of each array? $\endgroup$ – md5 Oct 13 '17 at 11:49
  • $\begingroup$ @md5 sum of all elements over all arrays will be less than 10^6. $\endgroup$ – Tom Oct 13 '17 at 12:07
1
$\begingroup$

You can solve this using dynamic programming. For each $1 \leq m \leq n$ and $1 \leq t_m \leq \ell_i$, calculate the maximal value of $\sum_{i=1}^{m-1} i|A_i[\ell_i]-A_{i+1}[1]|$ given that $A_m$ is rotated by $t_m$ places. This solution takes time $O(\sum_{i=1}^{n-1} \ell_i \ell_{i+1}) = O(\ell^2/n)$, where $\ell = \sum_{i=1}^n \ell_i$.

We can significantly improve on this algorithm by noticing that the objective function depends on the $i$th array via $\pm (i-1) A_i[1] \pm i A_i[\ell_i]$. This means that the shift we choose must maximize one of the following four quantities: $$ \begin{align*} +(i-1)A_i[1] + iA_i[\ell_i], \;+(i-1)A_i[1] - iA_i[\ell_i], \\-(i-1)A_i[1] + iA_i[\ell_i], \;-(i-1)A_i[1] - iA_i[\ell_i]. \end{align*} $$ This means that there are at most four values of $t_m$ that we need to consider (and at most two for $m \in \{1,n\}$). We can find these value in $O(\sum_{i=1}^{n-1} \ell_i) = O(\ell)$, and the dynamic programming part now takes only $O(n)$. In total, we obtain an $O(\ell)$ algorithm, that is, a linear time algorithm, which is asymptotically optimal.

$\endgroup$
  • $\begingroup$ thanks for the explanation but can you please elaborate that after calculating tm for every array how will we choose the correct tm that you mentioned can be solved with dp in O(n). $\endgroup$ – Tom Oct 13 '17 at 13:51
  • $\begingroup$ You use dynamic programming: for each $1 \leq m \leq n$ and for each of the up to four relevant values of $t_m$, you calculate the maximal value of $\sum_{i=1}^{m-1} i|A_i[\ell_i]-A_{i+1}[1]|$ given that $A_m$ is rotated by $t_m$ places. $\endgroup$ – Yuval Filmus Oct 13 '17 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.