CHOCOCUT - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Alice has an N\times M bar of chocolate.
She can cut this either vertically or horizontally, at most once - then keep one piece and give away the other to Bob.
How much of the chocolate can she keep with her while ensuring Bob gets at least K units?

EXPLANATION:

Suppose Alice makes a vertical cut, say at distance i.
The chocolate is then split into two parts with dimensions i\times N and (M-i)\times N.
If i\times N \geq K Alice can give this part to Bob and keep (M-i)\times N for herself, otherwise this cut isn’t valid to satisfy Bob.
Try every vertical cut (i.e. every value of i from 0 to M) and take the best value among them for Alice.

Similarly, try every horizontal cut - which will split the rectangle into M\times i and M\times (N-i) - and take the best value for Alice among them.

The final answer is the maximum of both these values.

TIME COMPLEXITY:

\mathcal{O}(N+M) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, m, x = map(int, input().split())
    ans = 0
    for i in range(n+1):
        if i*m >= x: ans = max(ans, (n-i)*m)
    for i in range(m+1):
        if i*n >= x: ans = max(ans, (m-i)*n)
    print(ans)
2

isnt the right time complexity O(1) per testcase ??

because , when we have a chocolate bar of m*n blocks , it is guranteed that k blocks are going to be given to bob. now we just need to determine whether the extra blocks that are going to be given away are minimzed by horizontal or vertical cut.

lets say we have a 3x4 grid and bob needs 7 chocolates.

so out of 12 blocks , 7 are already gone.

5 remain.

if we take the cuts along the side with 3 blocks , we would have to give away 3 cuts which are 9 blocks ( 7 which bob wanted + 2 extra because we cut along the 3 block side) . if we cut along the side with 4 blocks , we just give away 8 blocks ( 7 + 1 extra)

so what im trying to say is , by doing constant time arithmetic calculation on M and N , we can minimize the “extra blocks” that are to be given away.

I am not 100% sure if my explanation is making sense but what im trying to say is , we are not doing any looping for given input , we just do some constant time arithmetic and spit out the output , so what i think is , the time complexity should be O(1) and not O(M+N)

does that make sense ?