Connection Status:
Competition Arena > IncreasingSequence

IncreasingSequence

SRM 402 · 2008-05-24 · by srbga

SRM 402 · 2008-05-24 · by srbga · Dynamic Programming
Class Name: IncreasingSequence
Return Type: int
Method Name: getProduct
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are given a String[] digits. Concatenate the elements of digits to get one large string. Then, insert spaces to divide it into a list of strictly increasing integers (leading zeros are allowed). If there are multiple ways to do this, minimize the last integer. If there are still multiple solutions, maximize the first integer. If multiple solutions still remain, maximize the second integer, then the third one, etc. Return the product of all the integers in the list, modulo 1,000,000,003.

Notes

  • Two integers that differ only by the number of leading zeros they contain (for example, 0123 and 00123, or 95 and 00095) are considered equal (i.e., neither of them is less than the other).

Constraints

  • digits will contain between 1 and 50 elements, inclusive.
  • Each element of digits will contain between 1 and 50 characters, inclusive.
  • Each element of digits will contain digits ('0'-'9') only.
  • The first character of the first element of digits will not be '0'.
Examples
0)
{"12345"}
Returns: 120

Each single character can be an integer. The sequence 1, 2, 3, 4, 5 is strictly increasing.

1)
{"543210"}
Returns: 45150

The best thing we can get is 5, 43, 210.

2)
{"20210222"}
Returns: 932400

There are multiple ways to divide this string. The minimal last integer among all solutions is 222. There are four solutions where the last integer is 222: 2 021 0222 2 0210 222 20 21 0222 20 210 222 The last two solutions are better than the first two, because 20 > 2. And the last solution is the best one, because 210 > 21. So we need to return 20 * 210 * 222 = 932,400.

3)
{"1111111111"}
Returns: 1356531

Adjacent integers should never be equal to each other, so the optimal solution here is 1, 11, 111, 1111.

4)
{"171829294246"}
Returns: 385769340

Though we can try to start the sequence by 1, 7, 18, 29, we'll soon find that the only way to finish it is with 294246, which is unsatisfactory. The optimal sequence is 1, 71, 82, 92, 94, 246. The product is 12,385,769,376, which gives 385,769,340 as a remainder, when divided by 1,000,000,003.

5)
{"3","235","236"}
Returns: 264320

The last integer must be 236. But the sequence 3, 235, 236 is not optimal. We can maximize the first integer in 32, 35, 236, the product is 32 * 35 * 236 = 264,320.

8)
{"281002820"}
Returns: 7924200

2810*02820=7924200

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

Coding Area

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

Submitting as anonymous