33rd Friday Fun Session – 15th Sep 2017
Given a lunch schedule – a sequence of days when lunch is planned, and three price plans – daily, weekly and monthly, we want to get the cheapest lunch price.
This is the solution to JLTi Code Jam – Aug 2017 problem.
Let us walk through an example
Let us take an example as mentioned here: 1, 2, 4, 5, 17, 18. Since first day is 1 and last day is 18, it can be put under a month that consists of 20 consecutive days (not calendar month). We can use a monthly plan. But it would be too expensive (S$ 99.99) for just 6 days.
The days: 1, 2, 4 and 5 fall within a week that requires consecutive 5 days (not a calendar week). We have an option to buy a weekly plan for these 4 days that would cost S$ 27.99. However, that would be higher than had we bought day-wise for 4 days at a price of S$24.
Dynamic Programming
In general, at any given day, we have three options:
- We buy lunch for this day alone, using daily price S$ 6. Add that to the best price found for the previous day.
- We treat this as the last day of a week, if applicable, and buy a weekly plan at a cost of S$ 27.99. Add that to the best price for the day immediately prior to the first day of this week.
- We treat this as the last day of a month, if applicable, and buy a monthly plan at a cost of S$ 99.99. Add that to the best price for the day immediately prior to the first day of this month.
This is an optimization problem that can be solved with dynamic programming where we use the result of already solved sub-problems.
Bottom-up
We have two options: top-down and bottom-up. We realize that, at the end, all the sub-problems (for each of the days) have to be solved. We also find that it is easy to visualize the problem bottom-up. And if we do use bottom-up then the required space would be limited by the last day number.
Hence, we will solve it using bottom-up dynamic programming.
Blue colored days are when lunch is scheduled.
On day 1:
Cost S$ 6.
On day 2:
Daily basis: S$ 6 + price at day 1 = S$ 12
Weekly basis: S$ 27.99
Monthly basis: S$ 99.99
Best price: S$ 12
On day 3:
No lunch schedule, cost of previous day S$ 12 is its cost.
On day 4:
Daily basis: S$ 6 + price at day 3 = S$ 18
Weekly basis: S$ 27.99
Monthly basis: S$ 99.99
Best price: S$ 18
On day 5:
Daily basis: S$ 6 + price at day 4 = S$ 24
Weekly basis: S$ 27.99
Monthly basis: S$ 99.99
Best price: S$ 24
From day 6 to day 16:
No lunch schedule, cost of previous day will be carried forward: S$ 24.
On day 17:
Daily basis: S$ 6 + price at day 16 = S$ 30
Weekly basis: S$ 27.99 + price at day 12 = S$ 51.99
Monthly basis: S$ 99.99
Best price: S$ 30
On day 18:
Daily basis: S$ 6 + price at day 17 = S$ 36
Weekly basis: S$ 27.99 + price at day 13 = S$ 51.99
Monthly basis: S$ 99.99
Best price: S$ 36
Finally, the best price is S$ 36.
Another example
Let us work with another example: 1, 3, 4, 5, 6, 7, 10.
On day 7:
Daily basis: S$ 6 + price at day 6 = S$ 36
Weekly basis: S$ 27.99 + price at day 2 = S$ 33.99
Monthly basis: S$ 99.99
Best price: S$ 33.99
Finally, the best price at the end is S$ 39.99.
Complexity
The complexity is O(n), where n is the largest day number. It is a pseudo-polynomial time algorithm.
GitHub: FaaS
Sharing Experiences 