LooRollPyramid
SRM 813 · 2021-09-15 · by misof
Problem Statement
Whenever Michael finishes a roll of toilet paper, he does not throw away the cardboard roll inside. Instead, he uses them to build a triangular pyramid in the corner of his bathroom.
The bottom row of the pyramid consists of A rolls next to each other. Each of the following rows is one shorter than the previous one, with each roll in the new row standing on two adjacent rolls in the previous row. The pyramid is built row by row, bottom to top, and each row is built left to right.
Below is a scheme of a complete pyramid for A = 5. Each "[]" represents one roll.
[]
[][]
[][][]
[][][][]
[][][][][]
Below is a partial pyramid for A = 5. The state shown is the state produced after B = 10 rolls have already been placed.
[]
[][][][]
[][][][][]
The numbers A and B uniquely determine the current state of the pyramid.
Michael is interested in moments when there is no partially complete row of the pyramid - i.e., moments in which each row is either completely full or still empty. Given A and B, your task is to find the smallest non-negative C with the following property: if Michael adds C more rolls to his current partial pyramid, he will reach one of those interesting moments.
You are given Q queries.
The parameters for these queries are in the arrays
Return a
Notes
- Even though B can be large, the answer cannot exceed A and therefore all answers fit into 32-bit signed integers.
Constraints
- Q will be between 1 and 100, inclusive.
- A will have exactly Q elements.
- Each element of A will be between 1 and 10^9, inclusive.
- B will have exactly Q elements.
- For each i, B[i] will be between 0 and the number of rolls in a complete pyramid with bottom side A[i], inclusive.
4
{5, 5, 5, 5}
{15, 10, 5, 0}
Returns: {0, 2, 0, 0 }
Four queries, each concerns a pyramid with A = 5: The first query is a complete pyramid, which is already an interesting moment, so nothing needs to be added. The second query is the incomplete pyramid shown in the problem statement. We need two extra loo rolls to complete the current row. The third query is a pyramid with just the bottom row. The row is complete and all other rows are empty. The last query is an empty pyramid. This is also an interesting moment (all rows are empty, no rows are complete), so again nothing needs to be added.
5
{4, 5, 6, 7, 8}
{10, 10, 10, 10, 10}
Returns: {0, 2, 1, 3, 5 }
These are the partial pyramids (each made of 10 loo rolls, but each with a different base): [] [][] [] [][][] [][][][] [][][][] [][][] [][] [][][][] [][][][][] [][][][][][] [][][][][][][] [][][][][][][][]
10
{987654321, 987654321, 987654321, 987654321, 987654321,
987654321, 987654321, 987654321, 987654321, 987654321}
{5432109876543210, 5432109876543211, 5432109876543212, 5432109876543213, 5432109876543214,
5432109876543215, 5432109876543216, 5432109876543217, 5432109876543218, 5432109876543219}
Returns: {735344876, 735344875, 735344874, 735344873, 735344872, 735344871, 735344870, 735344869, 735344868, 735344867 }
These are rather large pyramids. In the largest possible input there can be 100 such queries, not just 10. Is your solution fast enough?
46
{2, 7, 9, 8, 10, 6, 5, 9, 7, 7, 10, 1, 7, 1, 2, 1, 5, 8, 9, 1, 6, 10, 7, 4, 4, 9, 9, 6, 8, 4, 1, 9, 6, 6, 10, 6, 9, 10, 4, 4, 1, 3, 6, 2, 6, 10}
{3, 16, 34, 16, 6, 20, 7, 44, 27, 10, 13, 1, 23, 0, 3, 1, 9, 15, 35, 1, 11, 34, 18, 0, 7, 19, 36, 12, 16, 8, 0, 38, 3, 20, 53, 6, 24, 31, 4, 9, 0, 3, 0, 1, 17, 40}
Returns: {0, 2, 1, 5, 4, 0, 2, 0, 0, 3, 6, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 3, 3, 5, 1, 0, 1, 3, 0, 1, 0, 0, 3, 0, 0, 0, 0, 0, 1, 1, 0 }
98
{2, 2, 5, 9, 10, 9, 8, 7, 6, 1, 10, 5, 10, 9, 8, 6, 1, 10, 4, 4, 6, 7, 3, 3, 8, 4, 3, 2, 3, 10, 6, 9, 7, 2, 5, 8, 1, 2, 7, 2, 6, 1, 5, 1, 3, 3, 9, 8, 4, 8, 9, 8, 10, 10, 1, 2, 3, 3, 9, 6, 1, 10, 4, 1, 7, 2, 1, 2, 5, 1, 9, 5, 4, 10, 9, 3, 9, 10, 5, 10, 10, 2, 10, 8, 6, 9, 1, 2, 7, 7, 6, 5, 10, 8, 10, 3, 2, 9}
{0, 3, 14, 1, 27, 36, 33, 24, 2, 1, 50, 15, 32, 7, 15, 11, 1, 10, 7, 0, 18, 3, 5, 3, 29, 4, 5, 0, 4, 12, 21, 18, 1, 2, 15, 24, 0, 0, 28, 3, 17, 1, 9, 1, 6, 5, 13, 5, 1, 32, 19, 25, 21, 34, 1, 0, 6, 0, 39, 13, 1, 3, 5, 0, 12, 2, 1, 1, 9, 0, 29, 9, 7, 49, 28, 2, 43, 3, 4, 37, 30, 0, 1, 27, 14, 33, 1, 2, 9, 3, 9, 3, 10, 27, 21, 3, 3, 15}
Returns: {0, 0, 0, 8, 0, 3, 0, 1, 4, 0, 2, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 1, 0, 0, 0, 1, 7, 0, 6, 6, 0, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 4, 3, 3, 1, 5, 1, 6, 0, 0, 0, 0, 0, 0, 2, 0, 7, 2, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 2, 1, 1, 7, 1, 3, 4, 0, 9, 3, 1, 2, 0, 0, 4, 4, 2, 2, 0, 3, 6, 0, 0, 2 }
Submissions are judged against all 37 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LooRollPyramid with a public method vector<int> countMissing(int Q, vector<int> A, vector<long long> B) · 37 test cases · 2 s / 256 MB per case