VOID - Editorial



Author: Rahul Sharma

Tester: Sumukh Bhardwaj

Editorialist: Rahul Sharma




gcd, observation


Given a hollow cuboid L_h,B_h,H_h and an interger K. You need to select and fill it with solid cuboid such that each solid cuboid satisfy following conditions
L_s == B_s == A
1 \leq A \leq min(L_h, B_h)
1 \leq H_s \leq K
Find minimum number of solid cuboids required


Make use of Euclidean GDC algorithm to find number of squares required to fill rectangle L_h, b_h and multiply that with number of minimum slabs of height H_s required.


Subtask #1:
Since L_h==B_h for this subtask, therefore it is clear we need solid cuboids whose L_s == B_s == L_h == B_h. We only need to check the height parameter to get minimum count.
minimumSolidCuboids = ceil(H_h / K)

Subtask #2:
For this subtask, We will first solve the subpart,
Count minimum number of squares required to fill a rectangle L_h, B_h. We will count the number of squares with side length A = min(L_h, B_h) and update the L_h and B_h accordingly.
In case L_h > B_h then L_s = B_h, minSquares+=L_h/B_h
L_h = L_h \mod B_h
Similarly if L_h < B_h. This process is continued till L_h \mod B_h is zero or vica versa. Thus we get the count of minimum squares.

Let us consider an example where lenght and breadth of rectangle are as follows
L_h=9, B_h=4
We would need 6 squares to fill it up
2 squares with side length 4
4 squares with side lenght 1

Note: This is also the way gcd is calculated

For the second part since we need to calculate solid cuboids
We will now focus on height part i.e. H_s Minimum solid cuboids required to fill volume L_h*B_h*H_s is minSquares count.
Thus finally to fill complete hollow cuboid with minimum solid cuboid is given as
minimumSolidCuboids = minSquares*ceil(H_h / K)

Euclidean algorithm is used to solve this problem.


Time Complexity: O(log(min(L_h, B_h)) for each test case
Space Complexity: O(1) for each test case


Setter's Solution
using namespace std;

long long int minSquares(long long int l, long long int b)
	if(b == 0)
		return 0;
	return l/b + minSquares(b, l%b);
int main()
	long long int l, b, h, k;
	cin >> l >> b >> h;
	cin >> k;

	long long int minSquaresCount = minSquares(l,b);
	long long minSolidCuboids = 0;

	if(h%k == 0)
		minSolidCuboids = (h/k)*minSquaresCount;
		minSolidCuboids = (h/k + 1)*minSquaresCount;

	cout << minSolidCuboids;
1 Like