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.

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | ksun48 | 3575 |

4 | Radewoosh | 3562 |

5 | Miracle03 | 3480 |

6 | maroonrk | 3406 |

7 | ecnerwala | 3400 |

8 | peehs_moorhsum | 3384 |

9 | sunset | 3338 |

10 | Um_nik | 3320 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | Um_nik | 197 |

3 | YouKn0wWho | 192 |

4 | Errichto | 182 |

5 | sus | 181 |

6 | awoo | 180 |

7 | tourist | 175 |

8 | -is-this-fft- | 171 |

8 | SecondThread | 171 |

10 | Ashishgup | 170 |

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.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/25/2021 21:32:36 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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`

explaining first time anyone, hope it helps.

well explained. it helped.

gr8 explaination dude.. I was just missing the value in recurrence relation, which you used as val[i] or val[j].

tks for explanation

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

IOI 1996 Day 1 Problem 1