Dynamic Programming and the hardest problem on HackerRank
The hardest problem on HackerRank, sorted by Max Score and level “Expert” is Separate The Chocolate. It’s worth 250 points and the level “Expert” is the highest one. How to solve it?
Tom and Derpina have a rectangular shaped chocolate bar with chocolates labeled T, D and U. They want to split the bar into exactly two pieces such that:
- Tom’s piece can not contain any chocolate labeled D and similarly, Derpina’s piece can not contain any chocolate labeled T and U can be used by either of the two.
- All chocolates in each piece must be connected (two chocolates are connected if they share an edge), i.e. the chocolates should form one connected component
- The absolute difference between the number of chocolates in pieces should be at most K
- After dividing it into exactly two pieces, in any piece, there should not be 4 adjacent chocolates that form a square, i.e. there should not be a fragment like this:
The first line of the input contains 3 integers M, N and K separated by a single space.
M lines follow, each of which contains N characters. Each character is ’T’,’D’ or ‘U’.
0≤ M, N ≤8
0≤ K ≤ M * N
A single line containing the number of ways to divide the chocolate bar.
This problem is a complicated dynamic programming problem (DP). The idea is simple but the implementation is difficult.We can iterate the grids one by one. For each grid suppose the left and the upper one has been given to Tom or Derpina. (Color black or white.)To decide the square [i][j], we need all the square’s state in square[i][0..j – 1] and square[i – 1][j..n -1] , all the (n + 1) squares in total can decide this square’s state. We can use these as a part of state and we also must keep whether a component is dead. (If it’s dead then add one more square of the same color is invalid.)
- If you can solve a part of a very hard problem - it still can be very profitable in terms of HackerRank score. Compare 210.53 points to 50 points from “Two Robots” medium problem.
- Looking at other’s solutions, I’ve noticed this piece of code: