Saleswoman
SRM 714 · 2017-02-20 · by lg5293
Problem Statement
There are n people who live on the real axis. The people are numbered 0 through n-1. Person i lives at the position pos[i]. All of these positions are distinct.
Alice is a saleswoman. She travels along the real axis and she makes trades with the n people who live there. Alice trades items of a single type. Each person has a particular supply or demand of that item. In particular, if delta[i] is positive, the person has a supply of delta[i] units, otherwise the person has a demand of -delta[i] units. It is guaranteed that the sum of all elements of delta is nonnegative.
At the beginning, Alice is at position 0 and she has no items. In one second, she can move left or right by one unit. She can trade with a person if and only if she is exactly at the same position as that person. All trades happen instantly. During each trade Alice can buy or sell as many items as she wants. Of course, she can only sell the items she currently owns. While walking along the real axis, Alice can carry arbitrarily many items at the same time. She can pass through a position with a person without trading with them, if that is what she wants. (She can always come back and trade with them later.)
Alice has two goals:
- She must trade the items in a way that will satisfy all demands.
- She must end her travels at the position of the rightmost person.
Determine and return the smallest amount of time in which Alice can achieve both goals.
Constraints
- pos will have between 1 and 300 elements, inclusive.
- delta will have the same number of elements as pos.
- Each element of pos will be between 1 and 10^5, inclusive.
- Elements in pos will be distinct and will be strictly increasing.
- Each element of delta will be between -10^5 and 10^5, inclusive.
- The sum of delta will be nonnegative.
{3,14,15,92,101}
{-3,2,3,-3,1}
Returns: 143
Here we have five people. Person 0 is at position 3 and has a demand of 3 units. Person 1 is at position 14 and has 2 units of supply. Person 2 is at position 15 and 3 units of supply. Person 3 is at position 92 and has a demand of 3 unit. Person 4 is at position 101 and has 1 unit of supply In this case, one optimal path for Alice is as follows: First, walk to position 15. Since Alice is at the same position as person 2, she can take all of their supply. Next, walk to position 14. Alice can take all of the supply here, so she has a total of 5 units of supply. Next, walk to position 3. Alice can satisfy this person's demand. She will be left with 2 units of supply. Walk to position 101. Alice grabs the supply, so she has 3 units. Walk to position 92. Alice can satisfy this person's demands, and she is left with 0 units of supply. Finally, walk back to position 101 and end the walk. The total time taken by Alice is 15+1+11+98+9+9 = 143.
{1,2,4,8,16,32,64,128}
{-1,-1,-1,-1,1,1,1,1}
Returns: 382
In this case, Alice's path will look like 0 -> 128 -> 1 -> 128.
{100000}
{0}
Returns: 100000
Note that Alice must end at the rightmost person, even if she doesn't need to do any trades. Note that it is also allowed for a person's delta to be zero.
{100,200,300,400}
{10,-3,-5,2}
Returns: 400
{1,2,3,5,8,13,21,34,55,89}
{-1,1,-1,1,-1,1,-1,1,-1,1}
Returns: 199
Submissions are judged against all 81 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Saleswoman with a public method int minMoves(vector<int> pos, vector<int> delta) · 81 test cases · 2 s / 256 MB per case