Can anyone share their approach to solve FLOWERPO problem from Aug Long Challenge?
2 Likes
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…
1 Like
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
8 Likes
Thank you. I missed the observation that just two phases are guaranteed to give the answer 
1 Like
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.
1 Like
Thank you meooow for the found mistake. Now the formula should be fixed
i still didn’t understand the states of the dp. can someone explain it to me