Connection Status:
Competition Arena > FastPostman

FastPostman

SRM 346 · 2007-04-24 · by soul-net

SRM 346 · 2007-04-24 · by soul-net · Dynamic Programming
Class Name: FastPostman
Return Type: int
Method Name: minTime
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

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.

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.

Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FastPostman with a public method int minTime(vector<int> address, vector<int> maxTime, int initialPos) · 107 test cases · 2 s / 256 MB per case

Submitting as anonymous