Problem Link
Author : Rajat De
Editorialist : Rajat De
Difficulty
Easy
PREREQUISITES:
Dynamic Programming
Quick Explaination
Make a dynamic programing solution with position of bucket and number of clothes left as state
Explaination
There are a few things to observe like :
-
We only move to bucket in increasing $x$ direction
The position of the clothes on the rope is always a continious block starting from x = 1
This suggests us a dynamic programming approach with state like dp(i , j) donoting the minimum evergy to place clothes numbered [i..A] such that the next clothe needs to be placed at x = i and the bucket is currently at x = j
The transition goes like dp(i , j) = min(dp(i + 1 , j) + cost1(i , j) , min(dp(i , k) + cost2(A - i + 1 , j , k)) \forall k > j)
where
-
$cost1(i , j)$ denotes the energy required to take a clothe from bucket at $x = j$ and put it on rope at $x = i$ and if there are still clothes left then return to $x = j$
cost2(i , j , k) denotes the energy required to move the bucket from x = j to x = k with i clothes remaining in bucket
The complexity of this solution is roughly O(A^3)
To make this work in O(A^2) , We need to get rid of the O(A) transiton time.
To do this , lets introduce another parameter in out dynamic programming which is a boolean denoting whether at the current moment of time , the bucket is being moved or not
With this we can do transitions in O(1) time , if the bucket if being moved then we can either choose to stop moving it or we can move it one more step forward . If the bucket is not being moved , we can either place a clothe here or start moving the bucket.
With this optimization the final solution has time complexity O(A^2) and O(A^2) memory , the memory can be optimized to O(A) by just storing the current and the previous row in dynamic programming.