Art critics worldwide have only recently begun to recognize the creative genius behind the great bovine painter, Picowso.

Picowso paints in a very particular way. She starts with an N \times N blank canvas, represented by an N \times N grid of zeros, where a zero indicates an empty cell of the canvas. She then draws N^2 rectangles on the canvas, one in each of N^2 colors (conveniently numbered 1 \ldots N^2). For example, she might start by painting a rectangle in color 2, giving this intermediate canvas:

She might then paint a rectangle in color 7:

And then she might paint a small rectangle in color 3:

Each rectangle has sides parallel to the edges of the canvas, and a rectangle could be as large as the entire canvas or as small as a single cell. Each color from 1 \ldots N^2 is used exactly once, although later colors might completely cover up some of the earlier colors.

Given the final state of the canvas, please count how many of the N^2 colors could have possibly been the first to be painted.

.

Problem credits: Brian Dean

#4022 upload - done - how_to_reg -

Modern Art timer 2s memory 512MB

#4022

Modern Art 2s 512MB