Problem Link-https://www.codechef.com/problems/J7
Consider a box with sides a, b, c .
Now the three characteristics of this box are volume, surface area and total edge length.
We are given P and S. So mathematically
- P = 4(a+b+c)
- S = 2(ab + bc + ca)
- V = abc
We have 4 unknowns (a, b, c, V) and 3 equations stated above. We can easily find a brute force solution from here.
Take an arbitrary side, Say ‘c’. Now 0 < c < P <= 40000 . Since we are to report the answer rounded to two decimal places taking the least count of a side = 0.1 should be sufficient.
Run a for loop with ‘c’ = 0.1 -> P, incrementing c by 0.1 at each step. You need to use the above equations to find a and b and then finally calculate volume by multiplying them.
To iterate from 0.1 to 40000 we do 4*10^6 operations and since we have around 10 test cases we do around 4*10^7 operations. Maybe, you will get TLE like I did in my first try. If you do you need to analyse how to improve the bounds of ‘c’.
Hint : By varying ‘c’ from 0 to P we will get repeat solutions. Eg. If solution is 1, 2, 3 we will get all its permutations.{(1,2,3), (2, 3, 1), …}. Find better bounds for ‘c’ to prevent this.
2 Likes
great but please provide explanation of optimal solution…
Umm, If by optimal solution you mean the best possible one I am sure you need to apply calculus. It isn’t required by the problem. Is that what you are asking for ?