PROBLEM LINK:
DIFFICULTY:
Easy-Medium
PREREQUISITES:
DP, Sliding Window, RMQ
PROBLEM:
Given an array A of size N and an array B of size M, Chef and chefu play a game which has M turns. In ith turn a player can choose a subarray of size B[i] which lies completely inside the previously selected subarray except in the first turn where chef can choose any subarray of B1 size. When chef selects a subarray he adds points equal to the sum of elements in the subarray in the final score and chefu subtracts his points from the final score. Chef starts the game and if both players play optimally i.e. chef wants to maximise the final score and chefu wants to minimise it, we have find out the maximum score that can obtained at the end of the game.
EXPLANATION:
Subtask 1 :
Simplest and most straightforward way is to code a simple recursive function according to the problem statement and memoize it . So let’s try to write the recursive function :
Long long int solve ( int end ,int turn )
{
if(turn==m+1)
{
Return 0;
}
if(Memo[end][turn]) // Memoized the function
Return Memo[end][turn];
Long long int sol;
if(turn%2==0) // Even turn, Chefu minimises the score
{
sol=1e18;
for(int i=end-B[turn-1]+1+B[turn]; i < end;i++) //find min over range [i,i - B[turn]+1]
{
sol=min (sol,solve(i,turn+1)-(Prefix[i]-Prefix[ i - B[turn]]) );
}
}
Else // Odd turn, Chef maximises the score
{
sol=-1e18;
for(int i=end-B[turn-1]+1+B[turn]; i < end;i++) //find max over range [i,i - B[turn]+1]
{
sol=max(sol,solve(i,turn+1)+(Prefix[i]-Prefix[ i - B[turn]]) );
}
}
Return Memo[end][turn]=sol;
}
Assuming : B[0]=n+2 , and function is called with solve(n+1,1).
Code Explanation : The recursive function solve(End,Turn) denotes the maximum score that can be obtained when the previous subarray ended at “End” and the current turn is “Turn”. It’s easy to see that if turn==M+1 this means that the game ends and if the game doesn’t end then we play the next turn accordingly. Prefix[X]-prefix[Y-1] denotes the sum of all element between positions X and Y inclusive.
Time complexity is O(M*N^2). Gives you 20 pts .
Subtask 2 :
In this subtask M=2. Now lets try to think how we can optimise our previous recursive function. If we take a look at the inner loops they only find minimum or maximum value over some range. This can be optimised but it’s not doable in this recursive fashion so now we will think of this DP in bottom up fashion. Let DP[i][j] denote maximum score that can be obtained in jth turn such that the subarray considered is [i-B[j]+1,i]. We already know the answer for DP[1.i…N][M], it will be the sum of elements from [i-B[M]+1,i] and we can multiply this with -1 if the last turn is of Chefu.
Okay now with DP[1…i…N][M] precomputed, we have to compute DP[1…i…N][M-1] somehow. Because M=2 we can build a RMQ data structure over DP[1…i…N][M] so that we don’t have to loop multiple times to find the max/min value over the range. We can extend this idea to any M , first we precompute dp[1…i…N][M] and then build RMQ on this, then using this RMQ we compute DP[1…i…N][M-1], then we build RMQ over DP[1…i…N][M-1] to compute DP[1…i…N][M-2] and so on.
Time complexity is O(N*M*logn). This Gives you 40 pts.
Subtask 3 :
Let’s have look at the inner loops again and you can notice something special about the range queries the loops do. They start with [i,i - B[turn]+1] and then [i+1,i - B[turn]+2] , [i+2,i - B[turn]+3] … so on. This is nothing but finding min/max in a sliding window of a constant size B[turn], which is a standard problem that can be solved by Deque in O(n). Now adding this to our previous idea, we don’t need a complex RMQ structure, we will use Deque and build DP[1…i…N][M-1] from DP[1…i…N][M], again use Deque over DP[1…i…N][M-1] to build DP[1…i…N][M-2] and so on. This gives you 100 pts.
Time complexity :
O(N*M)