Connection Status:
Competition Arena > MinesweeperStrings

MinesweeperStrings

SRM 855 · 2024-05-22 · by misof

SRM 855 · 2024-05-22 · by misof · Math, Sorting
Class Name: MinesweeperStrings
Return Type: String
Method Name: generate
Arg Types: (int, long long)
Problem Statement

Problem Statement

Minesweeper strings are strings of length N with the following properties:

  • Each character is either a '*' (representing a mine) or a digit: '0', '1', or '2'.
  • The value of each digit must be equal to the number of mines adjacent to it.

For example, for N = 7:

  • "0000000" is a valid minesweeper string with no mines.
  • "*******" is a valid minesweeper string with seven mines.
  • "0001*2*" is a valid minesweeper string with two mines.
  • "0001000" is not a valid minesweeper string because the number of mines adjacent to the '1' in the middle is not 1.
  • "**0001*" is not a valid minesweeper string because the number of mines adjacent to the leftmost '0' is not 0.
  • "2*1*02*" is not a valid minesweeper string: all digits are wrong.

Suppose we order all valid minesweeper strings lexicographically (i.e., using the ASCII values of the characters that form them) and then number the sorted order starting from 0.

Given the string length N and the non-negative integer X, find the minesweeper string number X in the order described in the previous paragraph. Return that string, or an empty string if no string has the number X.

Notes

  • The ASCII values of characters '*', '0', '1', and '2' are 42, 48, 49, and 50, respectively.
  • In all common programming languages, the built-in string comparison operator produces the desired lexicographic order.

Constraints

  • N will be between 1 and 60, inclusive.
  • X will be between 0 and 10^18, inclusive.
Examples
0)
1
0
Returns: "*"

There are only two valid minesweeper strings for N=1. The lexicographically smaller one (i.e., string number 0) is "*".

1)
1
1
Returns: "0"

There are only two valid minesweeper strings for N=1. The lexicographically bigger one (i.e., string number 1) is "0".

2)
1
47
Returns: ""

There are only two valid minesweeper strings for N=1. There is no string number 47, so the correct return value is an empty string.

3)
7
71
Returns: "0001*2*"

Our old friend, the valid minesweeper string "0001*2*", has number 71 among all strings of length 7.

4)
14
9876543210987654
Returns: ""

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

Coding Area

Language: C++17 · define a public class MinesweeperStrings with a public method string generate(int N, long long X) · 32 test cases · 2 s / 256 MB per case

Submitting as anonymous