# NGME - Editorial

Code Battle - Philosopher’s Code

Author: Rahul Sharma
Tester: Naman Mittal
Editorialist: Om Bindal

EASY-MEDIUM

# PREREQUISITES:

Math, Number Theory, Observation.

# PROBLEM:

Given S sum of five variables v,w,x,y,z maximise value of expression z^2*(a+b+c) where a=vw(vw+2wx) , b=wx(wx+2xy) , c=xy(xy+2vw).

# QUICK EXPLANATION:

Simplified expression is (z(vw + wx + xy))^2 and to maximise it we need v=1,y=1 and remaning three variables should be as close as possible.

# EXPLANATION:

Naive Approach:
Use four nexted loop for four variables and find fifth variable as S-(v+w+x+y) and check the value of expression (z(vw + wx + xy))^2 in each iteration and output the maximum but for original constraints it may cause TLE.

Optimised Approach:
Optimized approach is to simplify the expression which will look as follows:
(z(vw + wx + xy))^2.

If you observe then vw + wx + xy can be written as (v+x)(w + y) - vy. This can imagined as area of rectangle with length (v + x) and breadth (w+y) and a section with length v and breadth y removed.

Thus to maximize the overall area we need to minimize the area of removed section and minimum value possible are v = y = 1.

Now w + x + z = S-2. To get the maximum answer w, x and z needs to be as close as possible i.e. their absolute difference between any two is 0 or 1.

# SOLUTIONS:

Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;

int main()
{
long long int t,v,w,x,y,z,val,mul,ans = 0, fans = 0,rem;
v = y = 1;
cin>>t;

while(t--)
{
cin>>val;

val = val - 2;
ans = fans = 0;
z = val/3;
rem = val%3;

if(rem == 1)
{
w = x = z;
z = z + 1;
}

else if(rem == 2)
{
w = x = z;
z = z + 1;
w = w + 1;
}

else
w = x = z;

mul = w + x + w*x;
ans = z*mul;
fans = ans*ans;
cout<<fans<<endl;
}

return 0;
}
``````