Solution for Facebook coding problem "Missing Mail"

README.md

Missing Mail

You are the manager of a mail room which is frequently subject to theft. A period of N days is about to occur, such that on the i-th day, the following sequence of events will occur in order:

• A package with a value of Vi dollars will get delivered to the mail room (unless Vi = 0, in which case no package will get delivered).
• You can choose to pay C dollars to enter the mail room and collect all of the packages there (removing them from the room), and then leave the room.
• With probability S, all packages currently in the mail room will get stolen (and therefore removed from the room).

Note that you're aware of the delivery schedule V1..N, but can only observe the state of the mail room when you choose to enter it, meaning that you won't immediately be aware of whether or not packages were stolen at the end of any given day.

Your profit after the N-th day will be equal to the total value of all packages which you collected up to that point, minus the total amount of money you spent on entering the mail room.

Please determine the maximum expected profit you can achieve (in dollars).

Note: Your return value must have an absolute or relative error of at most 10^-6 to be considered correct.

Constraints

1 ≤ N ≤ 4 000 0 ≤ Vi ≤ 1 0000 1 ≤ C ≤ 1 0001 0.0 ≤ S ≤ 1.00

Sample test case #1

N = 5
V = [10, 2, 8, 6, 4]
C = 5
S = 0.0

Expected Return Value = 25.00000000

Sample test case #2

N = 5
V = [10, 2, 8, 6, 4]
C = 5
S = 1.0

Expected Return Value = 9.00000000

Sample test case #3

N = 5
V = [10, 2, 8, 6, 4]
C = 3
S = 0.5

Expected Return Value = 17.00000000

Sample test case #4

N = 5
V = [10, 2, 8, 6, 4]
C = 3
S = 0.15

Expected Return Value = 20.10825000

Sample Explanation

In the first case, packages will never be stolen. You should therefore enter the mail room just once, on the final day, at which point there are sure to be 5 packages there with a total value of 10 + 2 + 8 + 6 + 4 = 30 dollars. Subtracting the 5-dollar fee for entering the mail room, your profit is guaranteed to be 30 - 5 = 25 dollars.

In the second case, each package is sure to be stolen at the end of the day on which its delivered. You should enter the mail room on days 1, 3, and 4, each time collecting just the package delivered on that day. This yields a guaranteed profit of 10 + 8 + 6 - (3 * 5) = 9 dollars.

In the third case, on each day, there's a 50% chance that all packages in the mail room will be stolen. You should enter the mail room on days 1, 3, 4, and 5. Note that, when you enter on day 3, there will be a 50% chance of the room having 2 packages (with values of 2 and 8 dollars), and a 50% chance of the room having just 1 package (worth 8 dollars).

In the fourth case, you should only enter the mail room on days 1 and 5.

solution.py

from typing import List

def getMaxExpectedProfit(N: int, V: List[int], C: int, S: float) -> float:
    # Keep track of the best trajectory, where i is the number of days without pickup
    # Keep track of both the potential value for next pickup, and current profit
    best_traj = [(0, 0)]

    for price in V:
        print(price, best_traj)
        # Add the new day : (expected value to be picked up, final expected value)
        best_traj.insert(0, (0, 0))

        # Update the best trajectories so far for the new day, considering the packages could've stolen
        best_traj = [(p * (1 - S), f) for p, f in best_traj]

        # Possibility #1 : pickup that day
        # in this case, find the best possible choice among all saved so far (just keep the best one)
        val = max(f + p for p, f in best_traj) + price - C
        best_traj[0] = (0, val)

        # Possibility #2 : don't pickup
        # In this case, update the on-going price
        for i in range(1, len(best_traj)):
            p, f = best_traj[i]
            best_traj[i] = (p + price, f)

        print(best_traj, "\n==========")

    return max(f for p, f in best_traj)


def tests():
    assert getMaxExpectedProfit(5, [10, 2, 8, 6, 4], 5, 0.0) == 25
    assert getMaxExpectedProfit(5, [10, 2, 8, 6, 4], 5, 1.0) == 9
    assert getMaxExpectedProfit(5, [10, 2, 8, 6, 4], 3, 0.5) == 17
    assert getMaxExpectedProfit(5, [10, 2, 8, 6, 4], 3, 0.15) == 20.10825


if __name__ == "__main__":
    tests()

awesome solution, thanks for this!