## Intuition The problem requires us to transform an array into a "cool" array by performing a series of operations. A "cool" array is one where each element is a peak, meaning it is greater than its immediate neighbors. The key insight is to recognize that we can achieve this by strategically removing elements to create peaks. ## Approach 1. **Identify Peaks**: For an array to be cool, every element should be a peak. A peak at position `i` satisfies `a[i] > a[i-1]` and `a[i] > a[i+1]`. 2. **Greedy Strategy**: We can use a greedy approach to transform the array into a cool array. The strategy is to iterate through the array and ensure that each element is a peak by removing the necessary elements. 3. **Operation Count**: For each element that is not a peak, we need to perform an operation. The operation involves removing one of the adjacent elements to make the current element a peak. 4. **Iterate and Transform**: Traverse the array and for each element that is not a peak, increment the operation count and adjust the array by considering the removal of one of its neighbors. 5. **Edge Cases**: Handle the boundaries of the array carefully since the first and last elements have only one neighbor. ## Complexity - **Time Complexity**: O(n) per test case, where n is the length of the array. This is because we traverse the array once to identify and fix non-peak elements. - **Space Complexity**: O(1), as we are modifying the array in place and using a constant amount of extra space. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; vector a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } int operations = 0; for (int i = 1; i < n - 1; ++i) { // Check if a[i] is not a peak if (a[i] <= a[i - 1] || a[i] <= a[i + 1]) { // We need to perform an operation to make a[i] a peak operations++; // Choose to remove the element that makes the next element a peak if (a[i + 1] > a[i - 1]) { a[i] = a[i + 1]; } else { a[i] = a[i - 1]; } } } cout << operations << '\n'; } return 0; } ``` This solution reads the input, processes each test case by iterating through the array, and counts the necessary operations to make the array cool. It outputs the result for each test case. This approach ensures that we handle each element efficiently, maintaining the required time complexity.

Simons and Beating Peaks

Problem Details