TopCoder problem "FencingGarden" used in Member SRM 461 (Division I Level Three)



Problem Statement

    There is an empty grass field with an infinitely long straight wall. You are going to create a rectangular garden against the wall. Three sides of the garden will be enclosed with a fence. The fourth side of the garden is formed by part of the wall.



You currently have some fence segments. Each side of your fence can be created by connecting some of these segments. The length of a side of the fence is equal to the sum of the lengths of the fence segments that form it. The length of each side of the fence must be exactly equal to the length of the corresponding side of the rectangular garden. As in real life, each fence segment may only be used at most once.



Fortunately, you have a saw that can cut at most one of these segments into two shorter segments. The saw will break after being used one time. You may cut the one segment into two shorter segments at any point between its endpoints (non-integer length is allowed). Note that the total length of the two shorter segments created must be equal to the length of the original segment.



You are given int[] segment. The i-th element of segment represents the length of the i-th fence segment. Using these segments construct the garden fence (as described above) enclosing the maximum area possible and return the length of the garden's side parallel to the wall. If the maximum area can be formed in more than one way then return the largest parallel-to-the-wall length that gives the maximum area.
 

Definition

    
Class:FencingGarden
Method:computeWidth
Parameters:int[]
Returns:long
Method signature:long computeWidth(int[] segment)
(be sure your method is public)
    
 

Constraints

-segment will contain between 2 and 40 elements, inclusive.
-Each element of segment will be between 1 and 100,000,000, inclusive.
 

Examples

0)
    
{1,1,1,1,10}
Returns: 8
Cut the segment with length 10 into segments with lengths 2 and 8. Make two sides with length 3 and one side with length 8 using these segments. This gives a 3x8 rectangular garden.



Note that a 4x6 rectangular garden can also be constructed. It has the same maximum area of 24. But the correct answer is 8 since you should return the largest parallel-to-the-wall length that gives the maximum area and 8 is larger than 6.
1)
    
{50,25,25}
Returns: 50
Sometimes it is not necessary to cut any segment.
2)
    
{5,7,9,13,21,581,1848,1058,57172,58281,612,528}
Returns: 60078

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14181&pm=10733

Writer:

dolphinigle

Testers:

Rustyoldman , timmac , ivan_metelsky , mohamedafattah , it4.kp

Problem categories:

Search, Simple Math