Editorial-GLBEGA

Problem Links

Practice

Contest

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

Solution

I think you should add y++ in the if conditions along with x--