Connection Status:
Competition Arena > SelfDescFind

SelfDescFind

TCO19 SRM 758 · 2019-05-09 · by misof

TCO19 SRM 758 · 2019-05-09 · by misof · Brute Force, Dynamic Programming, Math, Recursion, Search
Class Name: SelfDescFind
Return Type: String
Method Name: construct
Arg Types: (vector<int>)
Problem Statement

Problem Statement

The number 31143310 is self-describing because we can read it as the statement "this number contains three '1's, one '4's, three '3's, and one '0'", and that statement correctly describes the whole number.

More formally, a number is called self-describing if it satisfies the following:

  • It has an even number of digits. Below, we will label the individual digits a[0], b[0], a[1], b[1], ... from the left to the right.
  • The digits b[i] are all distinct.
  • For each valid i, the number contains exactly a[i] copies of the digit b[i].
  • The number does not contain any other digits, except for those described by the statements mentioned above.

You are given the int[] digits. Find the smallest self-describing number N such that the digits that appear in N are precisely the digits in digits. If such a number exists, return a String with its decimal representation. Otherwise, return an empty String

Notes

  • Watch out for integer overflow.

Constraints

  • digits will contain between 1 and 10 elements, inclusive.
  • Each element of digits will be between 0 and 9, inclusive.
  • The elements of digits will form a strictly increasing sequence.
Examples
0)
{1}
Returns: ""
1)
{2}
Returns: "22"

The smallest self-describing number is 22. It contains two '2's, and it says about itself that it contains two '2's.

2)
{0,1,3,4}
Returns: "10143133"
3)
{0,1,2,4,5,6,8,9}
Returns: ""
4)
{0,1,2,3,5,6,8,9}
Returns: "1016181923253251"
5)
{4}
Returns: ""

Note that 4444 is not a valid self-describing number.

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

Coding Area

Language: C++17 · define a public class SelfDescFind with a public method string construct(vector<int> digits) · 83 test cases · 2 s / 256 MB per case

Submitting as anonymous