TopCoder problem "CoinPiles" used in SRM 279 (Division II Level Three)



Problem Statement

    

We have some coins on the table. Each coin is characterized by its size. We want to arrange these coins into successive piles so that the following hold:

  1. The size of the top coin in each pile is strictly greater than the size of all the other coins in the same pile.
  2. The size of the top coin in each pile is strictly greater than the size of the top coin in the previous pile.
  3. The number of coins in each pile is strictly greater than the number of coins in the previous pile.

You will be given a int[] sizes, each element of which represents the size of a coin on the table. Return the maximal number of piles that we can organize according to the given rules. Each coin should be used in exactly one pile.

 

Definition

    
Class:CoinPiles
Method:organize
Parameters:int[]
Returns:int
Method signature:int organize(int[] sizes)
(be sure your method is public)
    
 

Notes

-The maximal element of sizes will be unique, so it's always possible to form at least one pile.
 

Constraints

-sizes will have between 1 and 50 elements, inclusive.
-Each element of sizes will be between 1 and 1000, inclusive.
-The maximal element of sizes will be unique.
 

Examples

0)
    
{1, 2, 2, 2, 2, 3}
Returns: 2
It's impossible to make 3 piles according to the given rules.
1)
    
{1, 1, 2, 2, 2, 3}
Returns: 3
We can make 3 piles: {1}, {2,1} and {3, 2, 2}. The piles are listed in order and the coins in each pile are listed from top to bottom.
2)
    
{1, 2, 2, 2, 3, 4}
Returns: 3
3)
    
{701, 701, 646, 701, 559, 559, 646, 701, 646, 881}
Returns: 4
4)
    
{701, 701, 646, 701, 559, 559, 646, 701, 701, 881}
Returns: 3
5)
    
{60, 348, 60, 18, 60, 60, 400, 38, 211, 150, 348, 348, 
 60, 400, 462, 60, 97, 400, 164}
Returns: 5

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8076&pm=4841

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force