bonydoso's blog

Greedy/DP OA question need help
By bonydoso, 16 months ago, In English

Jack is an ambitious bus driver. In his journey driving , he passes through N stations located at position S1,S2,....,SN along the positive X axis. In order to ride the bus at the i-th station , a passenger must pay Ci dollars. You are also given an array D with length N-1 such that D1 represents the distance between station 1 and station 2 in meters . D2 represents the distance bet station 2 and station 3 in meters and so on.

Jack starts his journey at the 1st station at time 0. Your task is to calculate the maximum number of dollars Jack can earn throughout the journey."

each station i has 2 properties :

Pi denoting number of passengers that come to station per second Gi denoting the maximum time a passenger can wait for the bus, but when the passenger enters the bus, he will never leave the bus

NOTE : the bus travels at speed of one meter per second Jack can only stop in the stations (never stops in between) When the bus stops at a specific station , it will take exactly 2 seconds to go again and continue his journey
The bus has infinite capacity (can accomodate aany number of passengers)

Insights : since speed is constant = 1 = d / t , therefore d = t (distance convered = time) except for stops when delaying by 2 sec to go again

Input :

T number of test cases <= 100 Each test case starts with single integer N number of stations second line contains N space separated integers C1,C2,....,CN, Ci <= 10^3 (The Cost of riding the bus at station i) The third line contains N-1 space separated integers D1, D2, .... DN (di<=1e3) (Distance between each two consecutive stations) Fourth line contains N space separated integers P1,P2,...,PN (Pi<=1e3) (Number of passengers per second) Fifth line contains N space separated integers G1,G2,...GN (Gi <=1e3) Maximum time a passenger can wait for a bus (of course if that time elapsed Jack loses the money of that passenger)

Goal / output : For each test case, print the maximum profit Jack can make in dollars.

Example

Input :

1 5 10 12 5 3 2 4 3 2 5 2 4 5 2 3 5 2 1 10 11

Output : 457 dollars D I can't reach at 457 . so I would really appreciate any help.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Something is missing from the statement. He can easily make infinite money.

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

    I agree. This was a problem from the TRASH ECPC Questions. Egyptian Collegiate Programming Contest. Their questions are trash. Imagine such a confusing problem. In addition, there were problems in the set that refuse correct solutions. For more, look here

    Note: I provided the statement as it is just changing people names. The question was really so vague.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This question is very vague. Initially there are no people in any station

you need to calculate how many people will be on the station at the time the bus will arrive and add all of them in the bus. then all the people who arrive in the next 2 secs before the bus departures are also added. This is done for each station and then the total earnings will be no. of people from station i * cost of boarding bus from station i.

In corner cases, at first station the bus arrives at t = 0 and departs at t = 2. at last station bus waits for 2 secs and adds those people to the bus as well

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
        vector arrive(n);
    vector depart(n);
    arrive[0] = 0;
    depart[0] = 2;
    for i, 1 to n-1:
        arrive[i] = depart[i-1] + D[i-1];
        depart[i] = arrive[i] + 2;

    vector people(n);
    for i, 0 to n-1:
        people[i] = (min(arrive[i], G[i]) + 2) * P[i];

    int earn = 0;
    for i, 0 to n:
        earn += people[i] * c[i];

    print(earn)
    → Reply