TopCoder SRM 592 - 1000: SplittingFoxes2

Problem Statement

题目简述：

n 个格子围成一个圆，编号 0 到 n-1。
用 p[i] 表示 i 号格子上的数，p[i] 是非负整数。
这个圆圈关于 0 号位置对称，即 p[i mod n] = p[(-i) mod n]。

现在给出将 p 数组做一次循环卷积后的数组 a，
求可能的 p 数组中字典序最小的。如果没有，返回 -1。

数据范围：n <= 25, 0 <= a_i <= 10^6。

Once again, Fox Ciel is practicing splitting. This time there are N cells arranged into a circle. The cells are numbered 0 through N-1 around the circle (with cell N-1 being adjacent to cell 0).

At the beginning, there was exactly 1 fox in cell 0, and all the remaining cells were empty. Then there were two rounds of splitting, as described below.

There is some unknown splitting pattern P: a sequence of N non-negative integers. The pattern should also be considered cyclic: P[N-1] is adjacent to P[0]. The pattern is known to be symmetric around 0. Formally, for each i, P[i mod N] = P[(-i) mod N].

For example, for N=5 one valid pattern is P=(3,1,4,4,1). Note that for N=5 we must have P[1]=P[4] and P[2]=P[3].

We will now describe what happens when a fox splits. Assume that the fox is currently in the cell x. The fox that splits disappears. In its place, new foxes appear according to the pattern P. For each i from 0 to N-1, inclusive, P[i] new foxes appear in the cell (x+i) mod N.

In each round of splitting, all of the currently present foxes split at the same time, independent from each other. All the foxes use the same splitting pattern P.

You are given a int[] amount with N elements. For each i, amount[i] is the number of foxes in cell i after the second round of splitting. Your goal is to recover and return the pattern P. If there are multiple possibilities, return the lexicographically smallest one. If there is no pattern P that can produce amount, return {-1}. (I.e., the return value should be a int[] with 1 element, and the value of the element should be -1.)

Definition

Class SplittingFoxes2
Method getPattern
Parameters vector<int>
Returns vector<int>
Method signature vector<int> getPattern(vector<int> amount)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

Notes

Given two different N-element sequences of non-negative integers, the lexicographically smaller one is the one with the smaller element on the smallest index where they differ.
The 'mod N' operator used in the problem statement is the mathematical 'modulo N' operator that always returns an integer between 0 and N-1, inclusive. For example, (-3) mod 10 = 7.

Constraints

amount will contain between 1 and 25 elements, inclusive.
For each i, amount[i mod N] will be equal to amount[(-i) mod N], where N is the number of elements in amount.
Each element in amount will be between 0 and 1,000,000, inclusive.

Test cases

input
- amount { 2, 0, 1, 1, 0 }
output
Returns { 0, 1, 0, 0, 1 }

note

In each step each fox splits into two new ones: one in the cell to its left and one in the cell to its right.
input
- amount { 1, 0, 0, 0, 0, 0 }
output
Returns { 0, 0, 0, 1, 0, 0 }

note

Note that P = {1, 0, 0, 0, 0, 0} would also produce the final state given in amount. The correct return value is lexicographically smaller than this one.
input
- amount { 2, 0, 0, 0, 0, 0 }
output
Returns { -1 }

note

There is no solution in this case.
input
- amount { 10, 0, 8, 0, 10, 0, 8, 0 }
output
Returns { 1, 0, 2, 0, 1, 0, 2, 0 }

input

amount { 35198, 27644, 22185, 26896, 34136, 26896, 22185, 27644 }

output

Returns { 0, 59, 90, 76, 22, 76, 90, 59 }

note

This time we have 8 solutions:

{0, 59, 90, 76, 22, 76, 90, 59}
{17, 42, 107, 59, 39, 59, 107, 42}
{22, 76, 90, 59, 0, 59, 90, 76}
{39, 59, 107, 42, 17, 42, 107, 59}
{79, 59, 11, 76, 101, 76, 11, 59}
{96, 42, 28, 59, 118, 59, 28, 42}
{101, 76, 11, 59, 79, 59, 11, 76}
{118, 59, 28, 42, 96, 42, 28, 59}

input
- amount { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
output
Returns { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

back to the menu