 # Chef and Clothes Editorial

Contest

Practice

Author : Rajat De

Editorialist : Rajat De

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.

## Author’s Solution

//