Problem Links
Category
Easy
Pre-requisites
Greedy Algorithm
Problem Statement
Given two numbers m and n and two players. Both of the persons want to win. In each turn either m can subtracted by 1 till it’s not 0 and 1 gets added to n or n is reduced by 1. Given and equation Ax^2+b^2+Cx*y. We have to find the maximum sum of the all the values player 1 can get.
Explanation.
Let us consider Ax^2+By^2+Cx*y=f(x,y). For each player, there are two option either to do f(x-1,y+1) given x>0 or f(x,y-1) given y>0. Now at any point we can compare these two functions. We can see which one gets us the maximum value and follow that direction.
A pseudocode can be
totalscore=0
if( (x+y)%2==1)
{
if(x>0) ans1=f(x-1,y+1)
if(y>0) ans2=f(x,y-1)
if(ans1>ans2)
{
totalscore=+ans2;
x—;y++;
}
else
{
totalscore+=ans1;
y—;
}
}
else
{
if(x>0) ans1=f(x-1,y+1)
if(y>0) ans2=f(x,y-1)
if(ans1<ans2)
{
totalscore=+ans2;
x—;y++
}
else
{
totalscore+=ans1;
y—;
}
}
Editorialist’s Solution