Dynamic Bound Tracking for Absolute Value Sums

When calculating the maximum possible sum of an array where an absolute value operation can be applied to the running total at any point, tracking the exact moment to apply the operation is complex. A flawed approach might conditionally apply absolute values based on the sign of the next element and the current sum, which fails on sequences like -5, -3, 2, -1, -7 where delaying the absolute value yields a larger result.

The optimal strategy involves maintaining both the maximum and minimum possible running sums simultaneously. Since the absolute value operation flips the sign of the sum, the next state depends on both the previous maximum and minimum bounds. By evaluating all four possibilities at each step (adding the current element to the max bound, adding to the min bound, and taking the absolute values of both), we can update the new bounds. The final answer is the maximum bound after processing the entire array.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;
using ll = long long;

int main() {
    int count;
    cin >> count;
    vector<ll> values(count);
    for (int i = 0; i < count; ++i) {
        cin >> values[i];
    }
    
    ll max_bound = 0, min_bound = 0;
    for (int i = 0; i < count; ++i) {
        ll next_max = max_bound + values[i];
        ll next_min = min_bound + values[i];
        max_bound = max({next_max, next_min, abs(next_max), abs(next_min)});
        min_bound = min({next_max, next_min, abs(next_max), abs(next_min)});
    }
    cout << max_bound << endl;
    return 0;
}

Binary Search for Turn-Based Combat Simulation

In scenarios where a target must be depleted of health using periodic attacks with different damage values and cooldown times, determining the exact number of turns required exhibits monotonicity. If a target is defeated in t turns, it will also be defeated in t + k turns. This property allows for a binary search on the number of turns.

For a given turn count x, calculate the total damage inflicted. The first turn applies all attacks instantly. For the remaining x - 1 turns, each attack deals damage proportional to how many full cooldown cycles fit into that duration. If the accumulated damage meets or exceeds the target's health, the turn count is sufficient, and we search for a smaller value; otherwise, we search higher.

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

ll compute_damage(ll turns, ll remaining_hp, const vector<ll>& dmg, const vector<ll>& cd) {
    turns--; 
    for (size_t i = 0; i < dmg.size(); ++i) {
        remaining_hp -= (turns / cd[i]) * dmg[i];
    }
    return remaining_hp;
}

int main() {
    ll target_hp;
    int skill_count;
    cin >> target_hp >> skill_count;
    
    vector<ll> damage(skill_count);
    vector<ll> cooldown(skill_count);
    
    for (int i = 0; i < skill_count; ++i) {
        cin >> damage[i];
        target_hp -= damage[i];
    }
    for (int i = 0; i < skill_count; ++i) {
        cin >> cooldown[i];
    }
    
    ll low = 1, high = 5e10, result = 0;
    while (low <= high) {
        ll mid = low + (high - low) / 2;
        if (compute_damage(mid, target_hp, damage, cooldown) <= 0) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout << result << endl;
    return 0;
}

Greedy Pairing with Overlap Deduction

When pairing adjacent entities around a focal point (such as cows around a grass patch), a greedy approach can count the maximum pairs. If a focal point has more than two adjacent entities, it guarantees a new pair. If it has exactly two, we must check for overlapping pairs.

Overlaps occur in specific 2x2 grid configurations (e.g., two focal points diagonally adjacent, with the two entities occupying the other two diagonal corners). If this 2x2 pattern is detected and the adjacent focal point has already been processed, the current focal point must skip the pairing to avoid double-counting the same pair.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int rows, cols;
    cin >> rows >> cols;
    vector<vector<char>> grid(rows + 2, vector<char>(cols + 2));
    vector<vector<int>> adj_cows(rows + 2, vector<int>(cols + 2, 0));
    
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    
    for (int i = 1; i <= rows; ++i)
        for (int j = 1; j <= cols; ++j)
            cin >> grid[i][j];
            
    for (int i = 1; i <= rows; ++i)
        for (int j = 1; j <= cols; ++j)
            for (int k = 0; k < 4; ++k)
                adj_cows[i][j] += (grid[i + dx[k]][j + dy[k]] == 'C');
                
    int pairs = 0;
    for (int i = 1; i <= rows; ++i) {
        for (int j = 1; j <= cols; ++j) {
            if (grid[i][j] == 'G') {
                if (adj_cows[i][j] > 2) {
                    pairs++;
                } else if (adj_cows[i][j] == 2) {
                    bool overlap = (grid[i][j-1] == 'C' && grid[i-1][j-1] == 'G' && grid[i-1][j] == 'C' && adj_cows[i-1][j-1] == 2) ||
                                   (grid[i-1][j] == 'C' && grid[i][j+1] == 'C' && grid[i-1][j+1] == 'G' && adj_cows[i-1][j+1] == 2);
                    if (!overlap) pairs++;
                }
            }
        }
    }
    cout << pairs << endl;
    return 0;
}

Optimal Stacking by Weight and Strength Sum

To minimize the maximum risk when stacking items where each item has a weight and a load-bearing strength, sort the items by the sum of their weight and strength in descending order. Placing items with a higher combined sum at the bottom provides the most stable configuration.