NGME - Editorial

editorial
1

PROBLEM LINK:

Code Battle - Philosopher’s Code

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

DIFFICULTY:

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;
}