Connection Status:
Competition Arena > PartialSumPyramid

PartialSumPyramid

SRM 836 · 2022-08-29 · by misof

SRM 836 · 2022-08-29 · by misof · Simple Math, Simple Search, Iteration
Class Name: PartialSumPyramid
Return Type: int[]
Method Name: reconstruct
Arg Types: (int, int, vector<int>, vector<int>)
Problem Statement

Problem Statement

A pyramid of size N is an arrangement that consists of N rows of cells. The rows are numbered 0 to N-1 from top to bottom. Row i contains exactly i+1 adjacent cells. All cells have the same size, and all rows have their centers on the same x coordinate.

For example, a pyramid of size N = 4 looks as follows: 


      +---+
      |   |
    +---+---+
    |   |   |
  +---+---+---+
  |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+

For each cell not in the bottom row, the two cells it stands on are called its children.

A pyramid is called a number pyramid if each cell contains a non-negative integer.

A number pyramid is called a sum pyramid modulo M if each cell that's not in the bottom row contains the sum of the values in its two children, computing modulo M.

For example, below is one valid sum pyramid modulo M = 10. 


      +---+
      | 0 |
    +---+---+
    | 8 | 2 |
  +---+---+---+
  | 3 | 5 | 7 |
+---+---+---+---+
| 1 | 2 | 3 | 4 |
+---+---+---+---+

You are given the values N, M, and some partial information about a pyramid of size N that is a sum pyramid modulo M.

More precisely, you are given exactly one value in each row of the pyramid. In row i, the cells have indices 0 to i from left to right. For each i between 0 and N-1, inclusive, you are given the information that in row i the cell at index index[i] contains the number value[i].


Find a sum pyramid consistent with all the given data. Return a int[] containing the values in its bottom row (from left to right).

If there are multiple possibilities, you may return any one of them. If there are no sum pyramids consistent with the information you were given, return an empty int[] instead.

Constraints

  • N will be between 1 and 100, inclusive.
  • M will be between 1 and 10^9, inclusive.
  • index will have exactly N elements.
  • For each valid i, index[i] will be between 0 and i, inclusive.
  • value will have exactly N elements.
  • For each valid i, value[i] will be between 0 and M-1, inclusive.
Examples
0)
4
10
{0, 0, 0, 0}
{0, 8, 3, 1}
Returns: {1, 2, 3, 4 }

We are looking for a pyramid of size 4 that is a sum pyramid modulo 10. We are given the leftmost value in each row. We can easily check that these are consistent with the example shown above, so we know that {1, 2, 3, 4} is a valid bottom row.

1)
4
10
{0, 1, 2, 2}
{0, 2, 7, 3}
Returns: {1, 2, 3, 4 }

Again, this information is consistent with our example pyramid and thus {1, 2, 3, 4} is again a correct answer.

2)
5
47
{0, 1, 0, 3, 2}
{0, 0, 0, 0, 0}
Returns: {0, 0, 0, 0, 0 }

A pyramid full of zeros is clearly a valid sum pyramid modulo 47 that matches all the data we were given.

3)
5
47
{0, 1, 0, 3, 2}
{42, 23, 11, 0, 7}
Returns: {32, 33, 7, 8, 39 }
4)
1
47
{0}
{42}
Returns: {42 }

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

Coding Area

Language: C++17 · define a public class PartialSumPyramid with a public method vector<int> reconstruct(int N, int M, vector<int> index, vector<int> value) · 76 test cases · 2 s / 256 MB per case

Submitting as anonymous