Brotherly Field Division
InterviewTime limit1sMemory limit256 MB
Choose a non-decreasing staircase cut across N columns of an N x N grid to minimize the harvest difference between the two regions, and output one such cut.
- Level
Medium5 of 10
- Topics
- Dynamic programming, Brute force, Matrix
- Solved
- No attempts yet
Problem
There is a rice field made of N x N unit plots. Each plot has a predicted rice harvest, measured in sacks.
Two brothers will divide the field by columns. In each column, the elder brother receives some number of plots from the bottom, and the younger brother receives the remaining plots above them. Let h_i be the number of plots given to the elder brother in column i. The division must form a staircase, so it must satisfy 0 <= h_1 <= h_2 <= ... <= h_N <= N.
Divide the field so that the absolute difference between the brothers' predicted harvest totals is as small as possible. Find that minimum difference and one corresponding sequence h_1, h_2, ..., h_N.
Input
The first line contains the field size N (2 <= N <= 20).
Each of the next N lines describes one row of the field, from the top row to the bottom row. Each row contains N integers between 0 and 100, separated by spaces.
Output
On the first line, print the minimum possible difference between the two predicted harvest totals.
On the second line, print N integers: the values h_1, h_2, ..., h_N from the first column through the N-th column. If there are several optimal divisions, print any one of them.