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