MissingPuzzlePiece
SRM 848 · 2023-08-03 · by misof
Problem Statement
You have a rectangular puzzle. The puzzle consists of R rows by C columns of roughly-square puzzle pieces.
When the puzzle is solved, each piece has a specific place in the grid. We can label the rows of the puzzle using the first R uppercase English letters (top to bottom), and the columns of the puzzle by positive integers (left to right). The label of each puzzle piece is then produced by concatenating the label of its row and column.
For example, the top left piece is "A1", and in a puzzle with R=4 rows and C=14 columns the bottom right piece is "D14".
Your friend has been working on an app that can help assemble the puzzle. So far, she has implemented the part that can look at a puzzle piece and determine its label.
Sadly, after you tested her code on your puzzle, you realized that one of your puzzle pieces is missing.
You are given R, C, and the
Constraints
- R will be between 1 and 20, inclusive.
- C will be between 1 and 20, inclusive.
- pieces will contain exactly R*C - 1 elements.
- All elements of pieces will be distinct.
- Each element of pieces will be a valid label of a puzzle piece in a R times C puzzle.
1
1
{}
Returns: "A1"
A really sad story: the only piece of your 1 by 1 puzzle is missing. Obviously, this is the "A1" piece.
3
3
{"A1", "B1", "C1", "C2", "C3", "B3", "A3", "A2"}
Returns: "B2"
The middle piece of a 3x3 puzzle is missing in this test case.
3
3
{"A1", "A2", "A3", "B1", "B3", "C1", "C2", "C3"}
Returns: "B2"
The same puzzle as in the previous example. The only difference is that the pieces that are not missing are presented in a different order.
1
12
{"A1", "A3", "A5", "A7", "A9", "A2", "A4", "A6", "A8", "A10", "A12"}
Returns: "A11"
This puzzle only has one row.
1
12
{"A1", "A3", "A5", "A7", "A9", "A2", "A4", "A6", "A8", "A10", "A11"}
Returns: "A12"
Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MissingPuzzlePiece with a public method string identify(int R, int C, vector<string> pieces) · 77 test cases · 2 s / 256 MB per case