Internet Problem Solving Contest

IPSC 2012

Problem M – Matrix nightmare

As Obi-Wan would put it: “This isn’t the problem statement you are looking for. Move along.”

The double factorial numbers are the numbers di defined by the following recursive formula: d0 = 1, and i > 0 : di = di1 i!. For example, d3 = 1! 2! 3! = 12.

Sequences of length n with all elements belonging into the set {0,.n 1} are called limited sequences of order n. For example, (0,2,0,1) is a limited sequence of order 4. The set of all limited sequences of order n will be denoted 𝒮n.

The spread factor of a sequence A = (a 0,,an1) is the value σ(A) = i=0n1 j=i+1n1(ai aj).

There is a direct isomorphism between pairs of sequences and sequences of pairs. Formally: Let A,B ∈𝒮n. We can denote their elements as follows: A = (a0,,an1), B = (b0,,bn1). The corresponding sequence of pairs ((a0,b0),,(an1,bn1)) will be denoted PA,B.

Pairs of integers can be ordered lexicographically in the usual fashion: (a,b) (c,d) if either a < c, or (a = cb d). A sequence P = (p0,,pn1) of pairs of integers is ordered lexicographically if for all i, pi pi+1. Let ρ(P) = [if P is ordered lexicographically then 1 else 0].

Let M be a n × n matrix, with rows and columns indexed from 0 to n 1. Elements of M will be denoted mr,c. A matrix is called a -var matrix if each element in the matrix is either an integer or a variable. The n-step traversal weight of M is the following value:

                                   (                    n−1     )
φ(M ) = -1--⋅    ∑          ∑       ρ(P   )⋅|σ(A )|⋅σ(B )⋅∏  m
        d2n−1 A=(a,...,a  )B=(b,...,b   )    A,B              i=0  ai,bi
                 0A∈𝒮nn−1    0B∈𝒮nn−1

Problem specification

Given is a multivariate polynomial p with integer coefficients. Produce any reasonably small -var matrix M such that φ(M) = p.

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of a single line describing the polynomial. The variables are the letters a through z, the syntax will be clear from the input file. Each polynomial in the input file contains less than 50 operations (i.e., additions, subtractions and multiplications).

Output specification

For each test case output one matrix in the following format: First its size n, then all its elements in row major order. The elements may be separated by any positive amounts of whitespace. The size of the matrix must not exceed 70. All integers must be between 109 and 109, inclusive.

If for a given polynomial no such matrix exists, output a single zero instead.



1 y
x 0