Indian Computing Olympiad

Training Material

Dynamic Programming→Speculating on buffalos, Version 2

Ramu was a lazy farmer. He had inherited a fairly large farm and a nice house from his father. Ramu leased out the farm land to others and earned a rather handsome income. His father used to keep a buffalo at home and sell its milk but the buffalo died a few days after his father did.

Ramu too wanted to make some money from buffalos, but in a quite a different way. He decided that his future lay in speculating on buffalos. In the market in his village, buffalos were bought and sold everyday. The price fluctuated over the year, but on any single day the price was always the same.

He decided that he would buy buffalos when the price was low and sell them when the price was high and, in the process, accummulate great wealth. Unfortunately his house had space for just one buffalo and so he could own at most one buffalo at any time.

Before he entered the buffalo market, he decided to examine to examine the variation in the price of buffalos over the last few days and determine the maximum profit he could have made.

Suppose the price of a buffalo over a period of 10 days varied as 

	-------------------------------------------------
	Day   :  1   2   3   4   5   6   7   8   9  10
	-------------------------------------------------
	Price : 11   7  10   9  13  14  10  15  12  10
	-------------------------------------------------

The maximum money he can make in this case is 13 ---

  • buy on day 2, sell on day 3 (+3)
  • buy on day 4, sell on day 6 (+5)
  • buy on day 7, sell on day 8 (+5)

To discourage speculation, the panchayat has decided to charge a transaction fee. Each time a buffalo is bought or sold, Rs 2 has to be paid to the panchayat. What should Ramu's strategy be now? 

	-------------------------------------------------
	Day   :  1   2   3   4   5   6   7   8   9  10
	-------------------------------------------------
	Price : 11   7  10   9  13  14  10  15  12  10
	-------------------------------------------------

Example:

  • buy on day 2, sell on day 6 --- profit is (14-7) - 4 = 3
  • buy on day 7, sell on day 8 --- profit is (15-10) - 4 = 1

Solution

Let Profit[i..N] be the money Ramu can make on days i..N, assuming he has no buffalos at the start of day i.

On day i, Ramu can either buy or not buy a buffalo.

If Ramu does not buy on day i, it is as though Ramu started his transactions directly on day i+1. So,

  • Profit[i..N] = Profit[i+1..N]

If Ramu does buy on day i, the money he makes depends on when he sells the buffalo:

  • If he sells on day i+1, the money he makes is Price(day i+1) - Price(day i) - 4 + Profit[i+2..N]
  • If he sells on day i+2, the money he makes is Price(day i+2) - Price(day i) - 4 + Profit[i+3..N]
    …
  • If he sells on day N-2, the money he makes is Price(day N-2) - Price(day i) - 4 + Profit[N-1..N]
  • If he sells on day N-1, the money he makes is Price(day N-1) - Price(day i) - 4 + Profit[N]
  • Notice that Profit[N] is zero since he cannot buy and sell a buffalo in one day. If he sells on day N, the money he makes is. Price(day N) - Price(day i) - 4

Ramu's best strategy is to calculate the maximum of all these quantities.

  • Profit[i..N] =
                    max (
                       Profit[i+1..N],
                       Price(i+1) - Price(i) - 4 + Profit[i+2..N],
                       Price(i+2) - Price(i) - 4 + Profit[i+3..N],
                       …
                       Price(N-2) - Price(i) - 4 + Profit[N-1..N],
                       Price(N-1) - Price(i) - 4 + Profit[N],
                       Price(N) - Price(i) - 4
                     )

Using this we can compute explicitly

  • Profit[N-1] = max (Profit[N], Price(N) - Price(N-1) - 4)

Once we know Profit[N] and Profit[N-1], we can compute Profit[N-2] explicitly

  • Profit[N-2] = max (Profit[N-1], Price(N-1) - Price(N-2) - 4 + Profit[N], Price(N) - Price(N-2) - 4)

Continuing in this vein, we can compute Profit[N-3], Profit[N-4], ..., Profit[i]. In general, the final answer that we want is Profit[1].

A linear time algorithm:

  • With[i] — max profit starting i, if Ramu already has a buffalo
  • Without[i] — max profit starting i, if Ramu does not have a buffalo
  • With[i] = max { With[i-1], Without[i-1] - Price(i) - 2 }

    If Ramu has a buffalo at i, either he already had it at i-1 (With[i-1]), or he did not have it at i-1 and bought it at i (Without[i-1] - Price(i) - 2)
  • Without[i] = max { Without[i-1], With[i-1] + Price(i) - 2 }

Problems related to