TopCoder problem "SelfCatalogue" used in SRM 254 (Division I Level Three)



Problem Statement

    

A self-catalogue is a sentence that truthfully and comprehensively describes its own composition. In this problem, we are concerned with sentences that count numerals occurring in themselves, such as the following.

This sentence contains 1 occurrence of 0, 2 occurrences of 1, 3 occurrences of 2, and 2 occurrences of 3.

The above is a self-catalogue because it gives an accurate count for each numeral occurring in itself. The following sentence, although accurate in the counts that it gives, is not a self-catalogue because it does not give a count for the numeral 3.

This sentence contains 3 occurrences of 1, 1 occurrence of 8, and 1 occurrence of 9.

A self-catalogue must not give more than one count for the same numeral. Thus, the following is not a self-catalogue.

This sentence contains 4 occurrences of 4, and 4 occurrences of 4.

Given a int[] specifying a count for each of the numerals 0 through 9, try to find a self-catalogue that agrees with these counts. A count of 0 means that the numeral does not appear in the sentence at all, and a specified count of -1 means that any count (including 0) is acceptable. If there is no sentence meeting this specification, return an empty int[]. Otherwise, return a int[] of the same size as the input and containing the same non-negative counts, but with each -1 replaced by an accurate count. If several self-catalogues are possible, choose the one that yields the smallest value in element 0 of the result. If a tie remains, select for the smallest value in element 1; if there is still a tie, select for the smallest value in element 2; and so forth.

 

Definition

    
Class:SelfCatalogue
Method:construct
Parameters:int[]
Returns:int[]
Method signature:int[] construct(int[] counts)
(be sure your method is public)
    
 

Notes

-Leading zeros are not permitted for any number appearing in a self-catalogue.
 

Constraints

-counts contains exactly 10 elements.
-Each element of counts is between -1 and 100, inclusive.
 

Examples

0)
    
{1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
Returns: {1, 2, 3, 2, 0, 0, 0, 0, 0, 0 }
The first sentence from the problem statement satisfies the input specification that there be exactly one occurrence of the numeral 0:

This sentence contains 1 occurrence of 0, 2 occurrences of 1, 3 occurrences of 2, and 2 occurrences of 3.
1)
    
{100, -1, -1, -1, -1, -1, -1, -1, -1, -1}
Returns: { }
It is impossible to make a self-catalogue with 100 zeros.
2)
    
{1, 11, -1, -1, -1, -1, -1, -1, -1, -1}
Returns: {1, 11, 0, 1, 1, 1, 1, 1, 1, 1 }
Note that 11 contains two occurrences of 1.
3)
    
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
The following self-catalogue illustrates this degenerate case:

This is a sentence.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8006&pm=2246

Writer:

Eeyore

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Brute Force, Recursion