ChocolateBreaking
2019 TCO India Fun · 2019-04-15 · by misof
Problem Statement
You have a rectangular chocolate that consists of rows times cols unit squares. The chocolate is still in its wrapper. Without removing the wrapper, you want to break the chocolate into exactly pieces parts by breaking it fully between some rows and between some columns.
If your goal cannot be achieved, return -1. If it can be achieved, among all valid ways to break the chocolate find the one that minimizes the difference between the area of the largest and the area of the smallest piece. Return that difference.
Constraints
- rows will be between 1 and 10^9, inclusive.
- cols will be between 1 and 10^9, inclusive.
- pieces will be between 1 and 10^14, inclusive.
20 30 6 Returns: 0
You want to break a 20x30 chocolate into 6 pieces. There are two perfect ways to do so: either you break it into six 10x10 squares or into six 20x5 rectangles. In either case, the difference between the biggest and the smallest piece is zero.
3 3 5 Returns: -1
Given the restrictions in the problem statement, it is impossible to break a 3x3 chocolate into exactly five pieces.
5 5 4 Returns: 5
There are two ways to break a 5x5 chocolate into four pieces: One is to break it between any three columns (or any three rows), producing a single 2x5 piece and three 1x5 pieces. The other is to break it on either side of the middle row and on either side of the middle column of unit squares. This produces a 2x2 piece, two 2x3 pieces, and a 3x3 piece. In either case, the difference between the biggest and the smallest piece is 5. (In the first case it is 10-5, in the second case it is 9-4.)
3 10 4 Returns: 3
4 7 1 Returns: 0
You don't need to break anything if you only need one piece. The difference between the largest and the smallest piece is obviously zero.
4 6 15 Returns: 3
This is the smallest non-trivial test (i.e., with a solution that is not -1) that fails if you don't check that each piece must have both dimensions positive.
Submissions are judged against all 238 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ChocolateBreaking with a public method long long minDiff(int rows, int cols, long long pieces) · 238 test cases · 2 s / 256 MB per case