Connection Status:
Competition Arena > LeftRightDigitsGame2

LeftRightDigitsGame2

SRM 556 · 2012-06-05 · by mystic_tc

SRM 556 · 2012-06-05 · by mystic_tc · Dynamic Programming, Simple Math, String Manipulation
Class Name: LeftRightDigitsGame2
Return Type: String
Method Name: minNumber
Arg Types: (string, string)
Problem Statement

Problem Statement

You are playing a solitaire game called Left-Right Digits Game. This game uses a deck of N cards. Each card has a single digit written on it. These digits are given as characters in the String digits. More precisely, the i-th character of digits is the digit written on the i-th card from the top of the deck (both indices are 0-based).

The game is played as follows. First, you place the topmost card (whose digit is the 0-th character of digits) on the table. Then, you pick the cards one-by-one from the top of the deck. For each card, you have to place it either to the left or to the right of all cards that are already on the table.

After all of the cards have been placed on the table, they now form an N-digit number. You are given a String lowerBound that represents an N-digit number. The primary goal of the game is to arrange the cards in such a way that the number X shown on the cards will be greater than or equal to lowerBound. If there are multiple ways to satisfy the primary goal, you want to make the number X as small as possible.

Return the smallest possible value of X you can achieve, as a String containing N digits. If it is impossible to achieve a number which is greater than or equal to lowerBound, return an empty String instead.

Notes

  • lowerBound has no leading zeros. This means that any valid number X should also have no leading zeros (since otherwise it will be smaller than lowerBound).

Constraints

  • digits will contain between 1 and 50 characters, inclusive.
  • Each character of digits will be between '0' and '9', inclusive.
  • lowerBound will contain the same number of characters as digits.
  • Each character of lowerBound will be between '0' and '9', inclusive.
  • The first character of lowerBound will not be '0'.
Examples
0)
"565"
"556"
Returns: "556"

You can achieve exactly 556. The solution is as follows: Place the first card on the table. Place the second card to the right of all cards on the table. Place the last card to the left of all cards on the table.

1)
"565"
"566"
Returns: "655"
2)
"565"
"656"
Returns: ""

The largest number you can achieve is 655, but it is still less than 656.

3)
"9876543210"
"5565565565"
Returns: "5678943210"
4)
"8016352"
"1000000"
Returns: "1086352"
60)
"9613963206361956826579275983537488795314240324017"
"2286079350108094970403342259916655130449482506546"
Returns: "2286091693632361956265792759835374887953144034017"

2286091693632361956265792759835374887953144034017

113)
"22283375788952998280235623996945902896551888023210"
"15326202222283375788959988359969459028965188802321"
Returns: "15326202222283375788959988359969459028965888023210"

15326202222283375788959988359969459028965888023210

123)
"10001011010010110110000101010110110001110111100111"
"10101000010010111100111000010100100001111111111100"
Returns: "10101000010010111100111000010100100010111111111011"

10101000010010111100111000010100100010111111111011

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

Coding Area

Language: C++17 · define a public class LeftRightDigitsGame2 with a public method string minNumber(string digits, string lowerBound) · 154 test cases · 2 s / 256 MB per case

Submitting as anonymous