TopCoder problem "ThePriceIsRight" used in SRM 159 (Division I Level Two , Division II Level Three)



Problem Statement

    

The Price Is Right is a television game show. In the final round of competition, the contestant is shown the prizes which he can win. To win everything, he must make an educated guess and arrange the prizes in increasing order of price.

Once the contestant has completed ordering prizes, the host begins to reveal the price of each prize in any order that he wishes. To make the show more interesting however, the host reveals prices in such a way that as many prices are revealed as possible before an error in the order is revealed.

Each element in prices represents the price of a prize. The order of prices represents what the contestant thought the order was when arranging prices.

Given a int[] of prices as ordered by the contestant, return a int[] with two elements. The first element should be the maximum possible number of prices revealed before the order of prices is broken, while the second element should be the total number of ways of achieving that maximum number.

For example, prices = {30, 10, 20, 40, 50}

The host could reveal the following prices: 30 * * 40 50. The next price revealed (either 10 or 20) will cause an error in the ordering to be revealed. In this case, 3 prices were revealed. Alternatively, the host could reveal the following prices: * 10 20 40 50. Once again, the next price revealed will cause an error in the ordering to be revealed. However, in this case, 4 prices were revealed and thus the host would prefer to reveal the prices this way. Note that there is only 1 way of revealing 4 prices. The method should return {4,1}.

 

Definition

    
Class:ThePriceIsRight
Method:howManyReveals
Parameters:int[]
Returns:int[]
Method signature:int[] howManyReveals(int[] prices)
(be sure your method is public)
    
 

Notes

-The host DOES NOT work out any intermediate deductions. He reveals prices until the sequence order is broken. See examples 5 and 6.
 

Constraints

-prices will have between 1 and 50 elements inclusive.
-prices will not have any repeated elements.
-each element in prices will be between 1 and 1000000 inclusive.
 

Examples

0)
    
{30,10,20,40,50}
Returns: { 4,  1 }
See above.
1)
    
{39,88,67,5,69,87,82,64,58,61}
Returns: { 4,  2 }
The maximum number of prices that can be revealed is 4, and there are 2 ways of achieving it. The host could either reveal 39 * 67 * 69 87 * * * * or 39 * 67 * 69 * 82 * * *. The method should return {4,2}.
2)
    
{1,2,3,4,5,6,7,8,9,10}
Returns: { 10,  1 }
3)
    
{10,9,8,7,6,5,4,3,2,1}
Returns: { 1,  10 }
4)
    
{29,31,73,70,14,5,6,34,53,30,15,86}
Returns: { 5,  2 }
The host could either reveal 29 31 * * * * * 34 53 * * 86 or * * * * * 5 6 34 53 * * 86. The method should return {5,2}
5)
    
{100,99,1,2,3}
Returns: { 3,  1 }
In theory, because elements in prices are at least 1 (due to constraints), it is enough to reveal any of 1, 2 or 3 to know that the sequence of prices is broken. However, the host DOES NOT make these intermediate deductions and will reveal * * 1 2 3.
6)
    
{10,20,11,12}
Returns: { 3,  1 }
In theory, because there can be no price between 10 and 11, it is enough to reveal both 10 and 11 to know that the sequence of prices is broken. However, the host DOES NOT make these intermediate deductions and will reveal 10 * 11 12.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4600&pm=1784

Writer:

dimkadimon

Testers:

lbackstrom , brett1479

Problem categories:

Dynamic Programming