Prerequisites: STL Map, Vector etc.
Problem:
Alex has N empty boxes, each represented as a cube with a side length of ai. The task is to place these boxes inside each other to minimize the number of visible boxes. A box is considered visible if it’s not placed inside another box.
Solution Approach:
The core idea of the solution is the observation that to minimize the number of visible boxes, smaller boxes should be placed inside larger boxes whenever possible.
To implement this idea, we use a map to store the frequency of each side length of the boxes. By iterating through this map, we can identify the most frequent side length, which corresponds to the size of the largest box that contains the maximum number of smaller boxes.
The side length with the maximum frequency in the map will be the size of the largest box that can contain the maximum number of smaller boxes. Thus, the frequency of this side length gives us the minimum number of visible boxes when all boxes are optimally nested.
Time Complexity:
O(N log N), as we’re using map insertion for all N boxes.
Space Complexity:
O(N)
I get the idea, I would just wonder something. If we have a cubical box of side length 2, and 8 cubical boxes of side 1, can I store the 8 of them?
If not, I guess it should be said something like:
Alex has N empty boxes, each represented as a cube with a side length of Ai. The task is to place these boxes inside of each other to minimize the number of visible boxes. A box is considered visible if it’s not placed inside another box.
You can place a single box inside of another as it’s possible, but you can’t place two or more little boxes next to each other inside a super bigger box. (i.e., you can’t place 2 boxes of length 1 into a box of length 2).
Another option could be using Matryoshka dolls instead of cubical boxes as reference. I think it’s more intuitive than a box.
I was wondering how this would work in C, as it doesn’t have a built-in hash DS, so:
I thought of this solution with O(N) complexity per test case:
#include <stdio.h>
#include <stdlib.h>
#define ll long long
int compare(const void *a, const void *b) {
long long x = *(long long *)a;
long long y = *(long long *)b;
if (x < y) return -1;
if (x > y) return 1;
return 0;
}
int main(){
// Test cases
ll T;
scanf("%lld", &T);
while(T--){
// Needed array length
ll N;
scanf("%lld", &N);
// Size of the boxes
ll A[N];
for(ll i=0; i<N; i++){
scanf("%lld", &A[i]);
}
// Sorting
qsort(A, N, sizeof(ll), compare);
// Determinate the mode
ll local_count = 1;
ll bigger = 0;
for(ll i=1; i<N; i++){
if (A[i] == A[i-1]){
local_count++;
}
else{
if(local_count > bigger){
bigger = local_count;
}
local_count = 1;
}
}
if(local_count > bigger){
bigger = local_count;
}
printf("%lld\n", bigger);
}
return 0;
}