TopCoder problem "EqualTowers" used in SRM 442 (Division II Level Three)



Problem Statement

    

Johnny has some number of rectangular bricks. He can put bricks on top of each other to build a tower. He wishes to build two towers of equal height out of his bricks (each tower must contain at least one brick). He also wants the towers to be as tall as possible. Note that Johnny doesn't have to use all the bricks.

You are given a int[] bricks, where each element is the height of a single brick. Return the height of the tallest towers of equal height that Johnny can build. If it's impossible to build two towers of equal height, return -1 instead.

 

Definition

    
Class:EqualTowers
Method:height
Parameters:int[]
Returns:int
Method signature:int height(int[] bricks)
(be sure your method is public)
    
 

Constraints

-bricks will contain between 1 and 50 elements, inclusive.
-Each element of bricks will be between 1 and 500000, inclusive.
-The sum of all elements of bricks will not be greater than 500000.
 

Examples

0)
    
{ 2, 3, 5 }
Returns: 5
Johnny can build two towers of height 5. One contains a single brick of height 5, and the other contains a brick of height 2 and a brick of height 3.
1)
    
{ 10, 9, 2 }
Returns: -1
There's nothing Johnny can do here.
2)
    
{ 11, 11 }
Returns: 11
3)
    
{ 14, 3, 20, 15, 15, 14, 24, 23, 15 }
Returns: 64

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13750&pm=10466

Writer:

mateuszek

Testers:

PabloGilberto , kalinov , ivan_metelsky

Problem categories:

Dynamic Programming