## Intuition The problem requires us to determine two things: the height of the tallest tower we can build and the total number of towers we can construct using all the bars. The key insight is that bars of the same length can be stacked to form a tower. Therefore, the problem reduces to counting the frequency of each bar length. ## Approach 1. **Count Frequencies:** Use a frequency array or a map to count how many bars there are of each length. This will help us determine both the height of the tallest tower and the total number of towers. 2. **Determine Tallest Tower:** The height of the tallest tower corresponds to the maximum frequency of any bar length. This is because the tallest tower will be made by stacking all bars of the most frequent length. 3. **Count Total Towers:** The total number of towers is equal to the number of unique bar lengths, as each unique length can form at least one tower. 4. **Output the Results:** Print the height of the tallest tower and the total number of towers. ## Complexity - **Time Complexity:** O(N), where N is the number of bars. This is because we make a single pass to count the frequencies and another pass to determine the maximum frequency and count unique lengths. - **Space Complexity:** O(M), where M is the maximum possible bar length (1000 in this case). This is for storing the frequency of each bar length. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector frequency(1001, 0); // Since lengths are between 1 and 1000 for (int i = 0; i < N; ++i) { int length; cin >> length; frequency[length]++; } int maxHeight = 0; int totalTowers = 0; for (int i = 1; i <= 1000; ++i) { if (frequency[i] > 0) { maxHeight = max(maxHeight, frequency[i]); totalTowers++; } } cout << maxHeight << " " << totalTowers << endl; return 0; } ``` This solution efficiently counts the frequency of each bar length and uses this information to determine the required outputs. The use of a fixed-size array for frequency counting is both time and space efficient given the constraints.

Towers

Problem Details