TopCoder problem "Embassy" used in SRM 414 (Division I Level One , Division II Level Two)



Problem Statement

    You've just qualified for the on-site round of a major coding tournament! You now need to sort out a visa to allow you to travel to the event. You know that this is likely to be a long process, but are determined to sort it out as quickly as possible, even if it means working day and night. The process involves filling out a series of forms, which then have to be approved by the embassy. When the last form is approved your visa is granted. The approval process is very quick (instantaneous for the purpose of this problem), but there is a catch: each form has to be approved by the embassy before they will give you the next form to fill out. The embassy opens at exactly the same time each day and remains open for openTime time units. By the non-standard embassy clocks, a day is dayLength time units long, so the embassy then remains closed for dayLength - openTime time units before it opens the next day. Forms can be approved at any point in time between the time that the embassy opens and the time it closes, inclusive. However, if you finish filling in a form when the embassy is closed, you have to wait until it opens again before the form can be approved. The length of time it takes you to fill out form i is forms[i] units and the forms must be completed in the order they are given in forms. You already have the first form in your possession and can start filling it out at any time. Return the minimum length of time between starting to fill out the first form and getting your visa granted.
 

Definition

    
Class:Embassy
Method:visaApplication
Parameters:int[], int, int
Returns:int
Method signature:int visaApplication(int[] forms, int dayLength, int openTime)
(be sure your method is public)
    
 

Constraints

-forms will contain between 1 and 50 elements, inclusive.
-Each element of forms will be between 1 and 1,000,000 (10^6), inclusive.
-dayLength will be between 1 and 1,000,000 (10^6), inclusive.
-openTime will be between 1 and dayLength, inclusive.
 

Examples

0)
    
{4,4,4}
24
8
Returns: 12
The embassy is open for 8 hours out of a 24 hour day. Each of the three forms takes 4 hours to fill in. If you start filling in the first form 4 hours before the embassy opens, you can get it approved just as the embassy opens. The embassy will still be open 4 hours later to approve the second form and the third form can be approved just as the embassy shuts. Since you never have to wait, the total time is 12 hours.
1)
    
{4,4,4,4}
24
8
Returns: 28
Now there is an additional form to fill in. You can't complete the process in a single day.
2)
    
{2,2,2,2}
24
1
Returns: 73
The embassy is only open for one hour each day, so you can only get one form approved per day.
3)
    
{25,500,630,2500,1000,350,22,58,100,400,500,5000}
1440
360
Returns: 16945
Time is now measured in minutes. It's optimal to start filling in the first form 335 minutes after the embassy first opens.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13505&pm=9895

Writer:

StevieT

Testers:

PabloGilberto , Olexiy , gawry , ivan_metelsky

Problem categories:

Brute Force, Search, Simulation