TopCoder problem "IncreasingLists" used in SRM 434 (Division I Level Three)



Problem Statement

    

A string is called an increasing list if it is a comma-separated list of increasing positive integers with no leading zeroes. For example, the strings "2,3,9", "30", and "1,100,1000000000000000000000" are increasing lists, while "5,6,6", "1,2,3,", "0" and "1,02" are not.

You're given a String mask consisting of digits, commas and question marks. Replace each question mark with a digit or a comma, so that the resulting string is an increasing list, and return the resulting string. If there are multiple possible resulting strings, return the lexicographically smallest one. If it is impossible to produce an increasing list, return the string "impossible" (quotes for clarity only).

 

Definition

    
Class:IncreasingLists
Method:makeIncreasingList
Parameters:String
Returns:String
Method signature:String makeIncreasingList(String mask)
(be sure your method is public)
    
 

Notes

-A string S is greater than a string T lexicographically if T is a proper prefix of S, or if S has a greater character at the first position where the strings differ.
-Character ',' (comma) is lexicographically smaller than any digit ('0'-'9').
 

Constraints

-mask will contain between 1 and 50 characters, inclusive.
-mask will contain only commas (','), digits ('0'-'9') and question marks ('?').
 

Examples

0)
    
"??"
Returns: "10"
There is no way to place two numbers here, so we need one two-digit number. The lexicographically smallest one is 10.
1)
    
"???"
Returns: "1,2"
This mask stands for either a three-digit number or two one-digit numbers (comma-separated). Since a comma is lexicographically smaller than any digit, "1,2" is lexicographically smaller than "100".
2)
    
"?????????,9"
Returns: "1,2,3,4,5,9"
The lists ends with a 9, so it can contain only one-digit numbers. It is optimal to use the smallest numbers.
3)
    
"??????????,9"
Returns: "impossible"
The lists ends with a 9, so it can contain only one-digit numbers. However, the length of a list of one-digit numbers must be odd.
4)
    
"?,10,?????????????????,16,??"
Returns: "impossible"
There is too much space between 10 and 16, we can only put numbers 11 to 15.
5)
    
"?2?5??7?,??"
Returns: "12,50,70,71"
6)
    
"???????????????????????????????,???"
Returns: "1,10,11,100,101,102,103,104,105,106"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10265

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13696&pm=10265

Writer:

darnley

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming, String Manipulation