PROBLEM LINK: Game of Chefs
Author: Jeevansh Gagroo
Tester: Tanay Morakhia
Editorialist: Jeevansh Gagroo
DIFFICULTY
Hard
PREREQUISITES
Dynamic Programming
EXPLANATION
Some Observations:
- The trick here is to see that since the sum of the two players’ scores is the sum of the input list, Player 1 tries to maximize score1−score2, while Player 2 tries to minimize it.
- Let Ai denote the value of the ith number. Let dp[i][j] denote the difference between the score of the first player and the second player, score1 - score2 if they play the game between the indices i and j.
- For every interval (i, j) there is a fixed person who is going to be playing on that interval. dp[i][j] stores the difference between the scores of the person who is playing on that interval and then person who plays next if they are only allowed to use that interval. Since the person playing can only take the ends of the intervals, only i and j are available.
- Call the person taking currently A. If he takes i, then the interval becomes (i + 1, j). dp[i + 1][j] stores the value of B- A, so you subtract it from a[i] to get A + a[i] - B which is the value for the current segment if A takes i. It is very similar for if A takes j, and you compare them to get dp[i][j]. dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1]).
For better explanation refer: Explanation
SOLUTION
C++ Solution: Game of Chefs C++ Solution
Python Solution: Game of Chefs Python Solution
Java Solution: Game of Chefs Java Solution