We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Separate the chocolate

Separate the chocolate

Problem
Submissions
Leaderboard
Discussions
Editorial

Chinese Version
Russian Version

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:
    XX
    XX

Input Format

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

Constraints

0≤ M, N ≤8
0≤ K ≤ M * N

Output Format

A single line containing the number of ways to divide the chocolate bar.

Sample Input

2 2 4
UU
UU

Sample Output

12

Explanation

Note: In the explanation T and D are used to represent, which parts belong to Tom and Derpina respectively. There are 24 = 16 possible separations. The 4 invalid are:

TT
TT

DD
DD

DT
TD

TD
DT

Some of the valid ones are:

TD
TD

TT
DD

DD
TT

DT
DT

Author

cpcs

Difficulty

Expert

Max Score

250

Submitted By

1842

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy