Problem Statement

A postman has to deliver several letters along a street. He has the address (in the form of the number of meters from the left end of the street to the destination of the letter) and the maximum time he can take to deliver each letter. The postman moves at 1 meter per second and can deliver a letter instantly once he reaches the right location. You need to find out if it's possible to make all the deliveries within the given constraints, and if so, the minimum time the postman can take to do it.

You will be given two int[]s address and maxTime, where the ith element of each represents the address and maximum time of delivery of the ith letter. You will also be given an int initialPos with the initial position of the postman (in the same units and format as the addresses). Return the minimum amount of time the postman needs to deliver all letters within the constraints or -1 if it's impossible to do so.

Definition

 Class: FastPostman Method: minTime Parameters: int[], int[], int Returns: int Method signature: int minTime(int[] address, int[] maxTime, int initialPos) (be sure your method is public)

Constraints

-address will contain between 1 and 50 elements, inclusive.
-address and maxTime will contain the same number of elements.
-Each element of address will be between 1 and 1000000 (106), inclusive.
-Each element of maxTime will be between 1 and 1000000000 (109), inclusive.
-initialPos will be between 1 and 1000000 (106), inclusive.

Examples

0)

 `{1,3,5,7}` `{9,2,5,100}` `4`
`Returns: 13`
 The only way to deliver all the letters within the maximum times is to go through all the houses in the following order: 3-5-1-7.
1)

 `{1,5}` `{6,2}` `3`
`Returns: 6`
 If the postman starts from the house with address 5, he will make both just in time.
2)

 `{1000000}` `{45634}` `876`
`Returns: -1`
 No way!
3)

 `{1,7,10,4}` `{15,6,28,39}` `2`
`Returns: 20`
4)

 `{1000000,1000000,1000000,1000000}` `{563,23452,32426,1}` `1000000`
`Returns: 0`
 The postman is lucky and starts right in front of the only house that has correspondence.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10670&pm=7684

soul-net

Testers:

PabloGilberto , brett1479 , Yarin , Olexiy

Problem categories:

Dynamic Programming