TopCoder problem "WindowWasher" used in SRM 168 (Division II Level Three)



Problem Statement

    

You are the proud owner of a window washing company. Your workers tirelessly clean the outside of tall buildings. Of course, not all of your workers are equal. Some are faster than others. So your job is to place them at the best locations so that the job gets done the fastest. All the workers work in the same pattern. They start at the top of the first column of windows they are to wash. Using lifts, they wash the highest window, then the second highest, and so forth until all the windows in a column are washed. When they reach the lowest window, they use the lift controls to move to the column to the right. In this column, they work their way up the building until they reach the top. Using this zig-zag pattern, they wash all the windows they can until they get either to a column of windows that is being washed, or has been washed by another worker, or to the edge of the building. Because the lifts are on the same railing, they cannot cross over each other, or be in the same column at the same time. Not all of your workers need to be used on a job, and not all of them need to be working the entire time.

You will be given three arguments. width is the number of window columns the side of a building has, height is the number of rows of windows the side of a building has, and washTimes is a int[] which represents the time it takes each worker to wash a single window, in seconds. Each element represents a different worker's wash time.

Given this information, return the least amount of time in which your crew can wash that side of the buliding.

 

Definition

    
Class:WindowWasher
Method:fastest
Parameters:int, int, int[]
Returns:int
Method signature:int fastest(int width, int height, int[] washTimes)
(be sure your method is public)
    
 

Constraints

-width is between 1 and 1000, inclusive.
-height is between 1 and 1000, inclusive.
-washTimes has between 1 and 50 elements, inclusive.
-Each element of washTimes is between 1 and 1000, inclusive.
 

Examples

0)
    
10
10
{60}
Returns: 6000
The sole proprieter case. You can wash each window in 60 seconds, and there are 100 windows, which takes you 6000 seconds, or 100 minutes.
1)
    
10
10
{60, 60}
Returns: 3000
With a partner that works as fast as you can, the windows are washed in half the time.
2)
    
10
10
{60, 30}
Returns: 2100
After sending your partner to a window washers' conference, he has learned a new technique to cut the washing time in half. If you wash 3 columns, that lets your partner wash 7 columns, and you can get the job done in 35 minutes. Note that if the lifts allowed you to work on the same column, you could both work on the last column at the same time and get done quicker, but this is not allowed.
3)
    
1000
1000
{1000}
Returns: 1000000000
I would recommend that this guy get out of the window washing business.
4)
    
421
936
{111,56,931,22,445,90,14,222}
Returns: 2450448
5)
    
25
25
{1,625}
Returns: 625
In this case, it is better not to use the second worker, as the first can get the job done in the same time it takes the second to wash one window!
6)
    
12
754
{728, 734, 147, 464, 6, 703, 254}
Returns: 54288

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4645&pm=1919

Writer:

schveiguy

Testers:

lbackstrom , brett1479

Problem categories:

Dynamic Programming