Chef and Clothes Editorial

Problem Link



Author : Rajat De

Editorialist : Rajat De




Dynamic Programming

Quick Explaination

Make a dynamic programing solution with position of bucket and number of clothes left as state


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)

    $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.

## Author’s Solution