Can anyone share their approach to solve FLOWERPO problem from Aug Long Challenge? asked 18 Aug '17, 16:17

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 dptable $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_nA_i)^2+dp_s[i][b1]\} & 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:
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=BB_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_nA_{n_1})^2,(A_nA_{n_2})^2\}+dp_{n_1}[1][B_21]+dp_{n_2}[N][B_21]\}$ by application of (*2) we can reformulate this the calls of dp to: $\min\limits_{\substack{0\leq B_1 \lt B,\\B_2=BB_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_nA_{n_1})^2,(A_nA_{n_2})^2\}+dp_1[n_1][B_21]+dp_N[n_2][B_21]\}$ 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 $BB_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 answered 18 Aug '17, 19:15
1
Thank you. I missed the observation that just two phases are guaranteed to give the answer :)
(18 Aug '17, 21:20)
1
One small correction: $... dp_n[1][B_21] + dp_n[N][B_21]$ should be $... dp_{n1}[1][B_21] + dp_{n2}[N][B_21]$, and the same for the next statement.
(19 Aug '17, 02:14)
Thank you meooow for the found mistake. Now the formula should be fixed
(21 Aug '17, 12:40)

i still didn't understand the states of the dp. can someone explain it to me answered 30 Oct '17, 19:45
