PROBLEM LINK:
Author: Shikhar Gupta
DIFFICULTY:
MEDIUM
PREREQUISITES:
PROBLEM:
There are N equal length carpet strips arranged adjacent to each other.
Every carpet strip is divided into M blocks which are either Clean (‘C’) or Dirty (‘D’).
We have to re-arrange the carpet strips in a way such that the area of clean portion gets maximized.
The problem can be solved using Dynamic Programming and a sorting.
EXPLANATION:
We can visualize the floor as a matrix of blocks with each row representing a carpet strip.
Let the matrix be stored in mp[][] where mp[i][j] represents the jth block in the ith row.
Now we make a dp[][] in which dp[j][i] stores the number of consecutive clean blocks to the left of the jth block in the ith row.
Now we sort each of the rows in the dp matrix (The sorting can be done in O(N)) and iterate through each of the rows to find the maximum value of dp[i][j]*(n-j+1).
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.