Connection Status:
Competition Arena > SplittingFoxes2

SplittingFoxes2

SRM 592 · 2013-06-25 · by cgy4ever

SRM 592 · 2013-06-25 · by cgy4ever · Advanced Math, Brute Force
Class Name: SplittingFoxes2
Return Type: int[]
Method Name: getPattern
Arg Types: (vector<int>)
Problem Statement

Problem Statement

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.)

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.
Examples
0)
{2,0,1,1,0}
Returns: {0, 1, 0, 0, 1 }

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.

1)
{1,0,0,0,0,0}
Returns: {0, 0, 0, 1, 0, 0 }

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.

2)
{2,0,0,0,0,0}
Returns: {-1 }

There is no solution in this case.

3)
{10,0,8,0,10,0,8,0}
Returns: {1, 0, 2, 0, 1, 0, 2, 0 }
4)
{35198,27644,22185,26896,34136,26896,22185,27644}
Returns: {0, 59, 90, 76, 22, 76, 90, 59 }

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}

Submissions are judged against all 123 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SplittingFoxes2 with a public method vector<int> getPattern(vector<int> amount) · 123 test cases · 2 s / 256 MB per case

Submitting as anonymous