ATTENTION!!!Before posting your query about asking for help make sure that your output for the case PROBLEM LINK:Author: Anton Lunyov DIFFICULTY:MEDIUM PREREQUISITES:Cylinder volume, Optimization using derivatives PROBLEM:You have a rectangle W × H. QUICK EXPLANATION:Let V(W, H) be the maximum volume of the cylinder provided that the first cut is parallel to the side W. The side H−X is the height of the cylinder.The optimal value of X in this case is X = min(W/π, 2/3 * H) and the volume is V = π/4 * X * X * (H − X). The side W is the height of the cylinder.Then the volume of the cylinder is V = π/4 * D * D * W. So we should maximize D. It can be proved that:
Also note that your output should have relative error 10^{11}. Many of you were confused about this. EXPLANATION:Here we discuss in detail the two cases mentioned in the QUICK EXPLANATION. The side H−X is the height of the cylinder.Then π * D ≤ W since we should roll up the second rectangle along the side W.
The side W is the height of the cylinder.Then the volume of the cylinder is V = π/4 * D * D * W. Horizontally aligned circles.At first let's see when it is optimal to cut out horizontally aligned circles. Vertically aligned circles.Now let's see when it is optimal to cut out vertically aligned circles. Thus, we have justified the first to subcases mentioned in the QUICK EXPLANATION. The toughest subcase.So now we have W * (π + 1) / 2 < H < W * (π + 2) ALTERNATIVE SOLUTION 1:You may noticed that the author's solution has a bit different way of calculating the answer :) Lemma 1. The maximum D for which we can cut out two nonoverlapping circles of diameter D from the rectangle A × B is D = min(A, B, A + B − sqrt(2 * A * B)).The best way to prove this lemma is to draw a picture since picture is worth a thousand words. By Lemma 1 the maximum D for which we can cut out two nonoverlapping circles of diameter D from the rectangle W × X is D = min(W, X, W + X − sqrt(2 * W * X)). Hence the complete set of restrictions we have on X and D is the following:
In view of the formula for the volume we should find maximum D for which there exists X, If D ≤ W/2, this inequality is satisfied for all X. Thus, analyzing the whole set of restrictions, Now assume that D > W/2.
It is clear that existing of such X is equivalent to Summarizing the entire analysis leads to the following formula for maximum D:
And you can find exactly this formulas implemented in the author's solution. ALTERNATIVE SOLUTION 2:Actually it is possible to solve the problem without calculating V(W, H) and V(H, W) separately. OPEN PROBLEMS:Till the very beginning of the contest there were no restriction that lateral surface should be cut parallel to the sides of the second rectangle, since we believe that it is always optimal to cut it so. But we can't find the proof of this and hence had to add this restriction. If someone knows either the proof or counterexample to the "without parallel restriction' version we would like to see it. At some point I also think on version where there is no initial cut and we simply need to cut all three pieces from the initial rectangle, but this version seems much more complicated. I still have feeling that the current solution is optimal even for such version but I could be wrong. Again if someone knows either the proof or counterexample to this general version we would like to see it, or if it is really interesting and challenging then that someone could set the new problem ;) AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:eolimp  889  Cylinder
This question is marked "community wiki".
asked 15 Apr '13, 15:00
showing 5 of 11
show all

@jaskaran_1 Recall that we are now in the case when
Since we have a vertical gap, let's draw a vertical line in the middle of this gap, Hence we get a correct pieces for the cylinder of diameter D + eps by this small perturbation. answered 23 Jun '13, 00:21
Thanks a lot for your help!I was missing the vertical gap(the wasted steel) which instead of taking in the centre(b/w circles and lateral surface) I had taken on the right side of the lateral surface.
(23 Jun '13, 01:02)

The idea of having maths intensive problems in a long contest is great as you have time to think,make and solve equation which you don't have in a short contest. answered 15 Apr '13, 22:29

would some sort of binary search over all possible cutting points X work in time? answered 17 Apr '13, 07:10
I have tried ternary search for finding x in case of when the side Hx is the height of cylinder. Because the volume function(x) is cubic function, the value of x which make maximum function value lies between 0 and H. if we draw a graph of the function we recognize that the function increases until x equals to H*2/3, and starts to decrease. If we exploit this fact, we can use ternary search for finding x. But the ternary search did not help me solve this problem in time. so I changed my approaches. We can also solve this problem using simple trigonal geometry. I will explain my solution soon.
(17 Apr '13, 08:20)
I don't know if binary search aproach was possible in C/C++ (refer to commented code in tester's solution http://www.codechef.com/download/Solutions/2013/April/Tester/CYLINDER.cpp ), but in java (because of longer allowed time) binary search worked in time (see my solution: http://www.codechef.com/viewsolution/2049808 )
(17 Apr '13, 11:57)

Could somebody please help me with the vertically aligned circles case when W/2 < H/(PI+1).
How are we able to move the circles in this case could somebody show it pictorially.I understood the movement in the horizontal circle case.In this case if D=W/2 and X=W/2 then we won't be able to move the 2 circles at all. answered 22 Jun '13, 20:32
Yes, I know that picture here is the best explanation. But it is so annoying to make pictures. Especially here, since it should be some kind of gif. So if someone who understands this place draw a picture and put it to the editorial it will be awesome :)
(22 Jun '13, 23:29)
What I don't understand is that how would we able to move the vertical circles to a somewhat diagonal position thereby increasing D(for the optimum fit) if the circles X=W/2 ie the circles are perfectly fit
(22 Jun '13, 23:43)

:( that was great @anton_lunyov
Is you emoticon correct? :)
yes sad because i failed to get AC. previously I was trying to derive a generalized formula using maxima and minima using derivatives. but then broke into cases. but i was stuck in precision also. submitted to check, but even cout<<setprecision(12)<<something; was giving TLE.
cout is slow here  prefer printf.
@anton_lunyov >> btw at one point you're saying "You cut it into two rectangles by vertical or horizontal cut. Then from one of the rectangles you cut out two equal circles of radius R" and again you're saying "diagonal aligning is also possible" aren't these contradicting each other?
because in the case of diagonal alignment, we are taking circles from both the rectangle actually, one from each. isn't it?
No, from rectangle 7 by 7 the only way to cut out two circles of radius 2 is to align them diagonally inside the rectangle (in two opposite corners).
Oh I see. And thank you for the "%.11e" part. It was news. And how did you come to this formula for maximum diameter diam = W + H  sqrt(2 * W * H)
Read proof of Lemma 1. It also gives a natural way how to come up with this formula.
haaah :( got WA just because i forgot to consider one condition :(
Really nice wuestion anton
@bugkiller Try imagining it like this .You have a 2+sqrt(2) side square and have 2 circles of side 1 inscribed it it. Now suppose this is a part of a long sheet (2+sqrt(2))(y+2+sqrt(2)) . So basically after cutting you have an (2+sqrt(2))(y) sheet left. Your cut is such that you are cutting this square (or rectangle as the case may be) out of the sheet.