Strange Painter
Time limit1sMemory limit128 MB
Reconstruct a picture painted by a recursive quadrant-coloring process closest (in Hamming distance) to a given N x N binary target, then output that minimal difference and the picture.
- Level
Medium7 of 10
- Topics
- Divide and conquer, Dynamic programming, Recursion
- Solved
- No attempts yet
Problem
Josip paints square black-and-white pictures in an unusual recursive way. The picture has N x N pixels, where N is a power of two. Each pixel is either white (0) or black (1).
For a single-pixel square, he paints that pixel with its intended color. For any larger square, he divides it into four equal smaller squares, then chooses one quadrant to paint entirely white, chooses one different quadrant to paint entirely black, and recursively applies the same process to the two remaining quadrants.
Some desired pictures cannot be produced exactly by this process. Given the desired picture, find a paintable picture with the smallest possible difference. The difference between two pictures is the number of pixel positions whose colors differ.
Input
The first line contains an integer N (1 <= N <= 512), the size of the desired picture. N is a power of two.
Each of the next N lines contains N digits, each either 0 or 1, describing the desired picture.
Output
First output the minimum possible difference.
Then output N lines describing a paintable picture that achieves that minimum difference, in the same format as the input.
If several optimal pictures exist, any one of them is valid.