hackerbaba's blog

By hackerbaba, history, 17 months ago, In English

Could someone please help me with Deque. I tried watching Errichto's explanation and couldn't quite understand it. I was struck on this problem and quite gave up no the whole DP as I found it so tough.

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
17 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

So first of all we are making a dp[n][n], where dp[i][j] states that the maximum difference we can attain by considering only numbers from index starting from i and terminating at j.

dp[i][j] can be written as val[i],whenever i and j are equal, because this is the maximum difference we can attain after selecting from i to j, whenever i>j dp[i][j]=0, and whenever i<j, we can write dp[i][j] as, dp[i][j]=max((val[i]-dp[i+1][j]),(val[j]-dp[i][j-1]))

Now the question still remains how did we got these dp states, so consider two players A and B__, and number of elements in the array to be three and A takes the first chance, so A got to choose when there are 3 elements and B when there are two similarly A again when there is 1 element, so players chose alternatively as we consider opposite also, and each one will try to maximize the difference of the coins collected and the total collected by the other player, so from i to j they have two choices select the one available at i or the one available at j, after selecting the one available at i, the difference that he gathered is val[i]-dp[i+1][j], because dp[i+1][j] was the difference earned by other player.

now see it using simple states, let's see when size is 1 and A got to chose element so he will chose element and the other person have zero, so the difference earned by A is simply val[i], now when size is 2 then B got to chose, and he will also try to maximize the difference, let he selects the one at i, then the total difference earned is val[i]-dp[i+1][j], as dp[i+1][j] was storing with how much point A is above B,

code

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a side note, this is actually an extrememly well known problem.

IOI 1996 Day 1 Problem 1