Hello CF ! I don't understand the editorial or the solution to USACO 2016 Feb Plat P2, P3. Can somebody help me understand them ? Thank you so much for all your help !
Also, if we're connecting a row and have already connected k columns (for k > 1), then we only need to remove m−k fences in that row, since the columns we've already processed are guaranteed to be connected.
Doesn't it depend on which vertical fence you remove ? There are two cases, for the first one you need to remove 4 fences, and for the second one you need to remove 1 fences (note: the picture shows the graph, not the original configuration. Edges are Cell-Cell distance, and vertices are cells)
Another way to think about this problem is to note that, if we have an optimal solution, then the solution isn't affected by switching two adjacent rows or two adjacent columns.
What does this means ?
In the editorial, I understand all but this para:
We can compute the best solution using k doors via dynamic programming, iterating on k and adding one door at a time. We can use a divide-and-conquer algorithm to solve the linear version of this problem. The idea is that we can compute the middle values of the dynamic program first: if we compute the position to put our k-th door in dp[k][n/2], then dp[k][i] for i<n/2 must be to the left of that and dp[k][i] for i>n/2 must be to the right of that. In this way, we can on average halve the search space at each level of the recursion, so we don't have to do O(n) work to compute each value of the dynamic program. At each level of the recursion, we do O(nk) work, meaning the total runtime of this algorithm ends up being O(nklogn) for the linear version of this problem.
In particular, how you calculate dp[k][n / 2] without calculating dp[k], ..., dp[k][n / 2 - 1] first ?
PS: Here's a question my friend asked on CSE: https://cs.stackexchange.com/questions/101109/intuition-behind-floyd-warshall-being-faster. Can you answer it there/here ? I and him came up with the problem while discussing it.