CHEFCUP - Editorial

PROBLEM LINK:

Practice
Contest

Author: Aswin Ashok
Tester: Harshit Agarwal
Editorialist: Aswin Ashok

DIFFICULTY:

EASY.

PREREQUISITES:

Math, Ternary Search

PROBLEM:

Given a cupboard. Assume that the width of the base is X. Then the Length of the base should not exceed (A−X) and the Height of the cupboard should not exceed (B−X). Also The Volume of the Cupboard should be maximum. You have to find minimum X which satisfies the given condition.

EXPLANATION:

We know that the maximum volume of the cupboard will be X*(A-X)*(B-X). To find the required X we can do a Ternary Search on X in the range 1 to min(A,B).

ALTERNATIVE SOLUTION:

The more popular solution for this question was to differentiate the above equation and solve for X to get the required answer.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

//