Word Squared
Time limit1sMemory limit512 MB
Given a permutation of 1 to n, build the smallest square matrix in which the permutation appears as a contiguous block in every row and every column.
- Level
Medium7 of 10
- Topics
- Combinatorics, Implementation, Brute force, Math
- Solved
- No attempts yet
Problem
Given a permutation of the numbers from 1 to n, find a square matrix satisfying the following rules:
- The matrix may contain only numbers that appear in the permutation.
- The given permutation must occur in every row of the matrix as a contiguous subsequence, read from left to right.
- The given permutation must occur in every column of the matrix as a contiguous subsequence, read from top to bottom.
- The size of the matrix must be as small as possible.
Input
The first line contains a positive integer n (n ≤ 500).
The second line contains n space-separated integers: the permutation.
Output
The first line should contain an integer m, the size of the matrix. The next m lines should list the m rows of the matrix in order. Each of these lines should contain the m values of the corresponding row, separated by spaces.
The size m must be as small as possible. If there are several valid answers, print any one of them.
Hint
This shows where the permutation occurs in the matrix from the example:
