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

×

Approach to solve FLOWERPO - August Long Challenge 17

Can anyone share their approach to solve FLOWERPO problem from Aug Long Challenge?

asked 18 Aug, 16:17

sumedhk's gravatar image

5★sumedhk
1917
accept rate: 0%

edited 18 Aug, 16:28


Truely (as specified by kauts_kanu) for C=1 it is a standard dp question

What was (at least for me) not obvious is that a complexity of $O(N^2\cdot B)$ is fine.

To solve the problem we can use the dp-table $dp_s[n][b]$ - the smallest cost to reach object with id $n$ with at most $b$ "steps" from some initial object $s$. It can be calculated by the following formula by brute force over the last step:

$dp_s[n][b]=\begin{cases}0 & \text{if }n=s\\ \infty & \text{if }n\neq s \wedge b=0\\min_{i\in\lbrace 1,\ldots, N\rbrace}\{(A_n-A_i)^2+dp_s[i][b-1]\} & else\end{cases}$

Therefore each value can be calculated in $O(N)$ by a simple for loop. This leads to the complexity of $O(N^2\cdot B)$ for calculation of the full table as $N\cdot B$ values need to be calculated.

This can be used to solve the subproblem where $C=1$ because if we reach object with id $n$ all objects in between are "visited".

Observations:

  • (*1) It does not make sense to go to an object $i\lt s$ while the aim is to go to an object $j\gt s$.
  • (*2) $dp_s[n][b]=dp_n[s][b]$, because the steps can just be done in "reversed order".
  • (*3) If we reach objects with ids $1$ and $n$ then all objects are visited
  • (*4) $\Rightarrow$ In the first phase we go to some object (possibly just the initial object) and in the second phase we go from there to objects $1$ and $n$
  • (*5) In phase two the first move is special, because the costs are only counted once!

The result is then the minimum over all splitting points, but we need to iterate over all options how many moves are possible for the first phase ($B_1$) and the second phase ($B_2$) and we also need to brute force over all options for the first move of phase two (Here $n_1,n_2$ are the nodes which are reached by the first step of phase two):

$\min\limits_{\substack{0\leq B_1 \lt B,\\B_2=B-B_1\\1\leq n\leq N\\1\leq n_1\leq n\\n\leq n_2\leq N}}\{dp_C[n][B_1]+\max\{(A_n-A_{n_1})^2,(A_n-A_{n_2})^2\}+dp_{n_1}[1][B_2-1]+dp_{n_2}[N][B_2-1]\}$

by application of (*2) we can reformulate this the calls of dp to:

$\min\limits_{\substack{0\leq B_1 \lt B,\\B_2=B-B_1\\1\leq n\leq N\\1\leq n_1\leq n\\n\leq n_2\leq N}}\{dp_C[n][B_1]+\max\{(A_n-A_{n_1})^2,(A_n-A_{n_2})^2\}+dp_1[n_1][B_2-1]+dp_N[n_2][B_2-1]\}$

Therefore we need to calculate the dp values only for starting positions $1,C,N$.

$\Rightarrow$ Runtime for dp calculation:$3\cdot O(N^2\cdot B)=O(N^2\cdot B)$

Now how can we calculate the minimum over $B_1,B_2,n,n_1,n_2$?

We acctually iterate over all options for $B_1$ and $n$. $B_2$ is received by $B-B_1$.

For each such combination we make two pointers $n_1=1,n_2=N$. Now we increase $n_1$ or decrease $n_2$ depending on whether object $n_1$ or $n_2$ is farther away from object $n$, because only then the cost of the fountain at id $n$ is decreased. We do this until $n_1,n_2$ reach $n$, which leads to $N$ iterations for fixed $n,B_1$. This accumulates again to $O(N^2\cdot B)$ and therfore we have the overall complexity of $O(N^2\cdot B)$.

An implementation can be found here

link

answered 18 Aug, 19:15

alexander86's gravatar image

6★alexander86
962
accept rate: 100%

edited 21 Aug, 12:38

1

Thank you. I missed the observation that just two phases are guaranteed to give the answer :)

(18 Aug, 21:20) meooow ♦6★
1

One small correction: $... dp_n[1][B_2-1] + dp_n[N][B_2-1]$ should be $... dp_{n1}[1][B_2-1] + dp_{n2}[N][B_2-1]$, and the same for the next statement.

(19 Aug, 02:14) meooow ♦6★

Thank you meooow for the found mistake. Now the formula should be fixed

(21 Aug, 12:40) alexander866★

For C=1, it was standard dp question.. You can follow it here..

I hope this should help. You can ask further if need, But I think you can easily get it why and how you will use above approach with FLOWERPO..

link

answered 18 Aug, 17:26

kauts_kanu's gravatar image

5★kauts_kanu
1.0k19
accept rate: 19%

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:

×191
×52
×30

question asked: 18 Aug, 16:17

question was seen: 519 times

last updated: 21 Aug, 12:40