Problem 1: Chessboard Pattern Validation

Given an n×m grid with cells marked 'B' (black) or 'W' (white), determine the minimum flips required to achieve a checkerboard pattern where adjacent cells have different colors. Two valid patterns exist starting with 'W' or 'B' at position (1,1).

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int rows, cols;
    cin >> rows >> cols;
    vector<string> grid(rows);
    for (int i = 0; i < rows; ++i) cin >> grid[i];

    auto generatePattern = [cols](char start) {
        vector<string> pattern(rows);
        for (int i = 0; i < rows; ++i) {
            string row = "";
            char current = start;
            for (int j = 0; j < cols; ++j) {
                row += current;
                current = (current == 'W') ? 'B' : 'W';
            }
            pattern[i] = row;
        }
        return pattern;
    };

    auto calculateFlips = [&grid](const vector<string>& pattern) {
        int flips = 0;
        for (int i = 0; i < grid.size(); ++i)
            for (int j = 0; j < grid[0].size(); ++j)
                if (grid[i][j] != pattern[i][j]) flips++;
        return flips;
    };

    vector<string> pattern1 = generatePattern('W');
    vector<string> pattern2 = generatePattern('B');
    cout << min(calculateFlips(pattern1), calculateFlips(pattern2));
    return 0;
}

Problem 2: Minimum Initial Health

Calculate the minimum starting health to traverse n stages where each stage modifies health (positive/negative). Health must never drop to ≤0 during traversal.

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int stages;
    cin >> stages;
    vector<int> healthChanges(stages);
    for (int i = 0; i < stages; ++i) cin >> healthChanges[i];

    long long current = 0;
    long long minHealth = LLONG_MAX;
    for (int change : healthChanges) {
        current += change;
        minHealth = min(minHealth, current);
    }

    cout << (minHealth > 0 ? 1 : abs(minHealth) + 1);
    return 0;
}

Problem 3: Maximum Non-Adjacent Sum

Find the maximum sum of non-adjacent elements in an array (house robber problem).

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int households;
    cin >> households;
    vector<long long> coins(households);
    for (int i = 0; i < households; ++i) cin >> coins[i];

    if (households == 0) return 0;
    vector<long long> maxGain(households);
    maxGain[0] = coins[0];
    if (households > 1) maxGain[1] = max(coins[0], coins[1]);

    for (int i = 2; i < households; ++i)
        maxGain[i] = max(maxGain[i-1], maxGain[i-2] + coins[i]);

    cout << maxGain[households-1];
    return 0;
}

Problem 4: Maximum Product Partition

Split an array into two subsets to maximize the product of their sums.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int size;
    cin >> size;
    vector<int> numbers(size);
    int total = 0;
    for (int i = 0; i < size; ++i) {
        cin >> numbers[i];
        total += numbers[i];
    }

    vector<bool> possible(total + 1, false);
    possible[0] = true;

    for (int num : numbers) {
        for (int j = total; j >= num; --j)
            possible[j] = possible[j] || possible[j - num];
    }

    for (int j = total / 2; j >= 1; --j)
        if (possible[j]) {
            cout << j * (total - j);
            return 0;
        }
    return 0;
}

Problem 5: Enhanced Pyramid Path with Multiplication

Find maximum path sum in a pyramid with up to k multiplications (doubling) of values along the path.

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int levels, magicCount;
    cin >> levels >> magicCount;
    vector<vector<int>> pyramid(levels);
    for (int i = 0; i < levels; ++i) {
        pyramid[i].resize(i + 1);
        for (int j = 0; j <= i; ++j) cin >> pyramid[i][j];
    }

    vector<vector<vector<long long>>> maxSum(levels, vector<vector<long long>>(levels, vector<long long>(magicCount + 1, LLONG_MIN)));
    maxSum[0][0][0] = pyramid[0][0];

    for (int i = 1; i < levels; ++i) {
        for (int j = 0; j <= i; ++j) {
            for (int k = 0; k <= magicCount; ++k) {
                long long base = maxSum[i-1][j][k] + pyramid[i][j];
                if (j > 0) base = max(base, maxSum[i-1][j-1][k] + pyramid[i][j]);
                if (k > 0) {
                    long long withMagic = maxSum[i-1][j][k-1] + 2 * pyramid[i][j];
                    if (j > 0) withMagic = max(withMagic, maxSum[i-1][j-1][k-1] + 2 * pyramid[i][j]);
                    base = max(base, withMagic);
                }
                maxSum[i][j][k] = base;
            }
        }
    }

    long long result = LLONG_MIN;
    for (int k = 0; k <= magicCount; ++k)
        for (int j = 0; j < levels; ++j)
            result = max(result, maxSum[levels-1][j][k]);
    cout << result;
    return 0;
}

Problem 6: Traveling Salesman Path

Find the shortest Hamiltonian cycle starting and ending at city 0.

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int cityCount;
    cin >> cityCount;
    vector<vector<int>> distance(cityCount, vector<int>(cityCount));
    for (int i = 0; i < cityCount; ++i)
        for (int j = 0; j < cityCount; ++j)
            cin >> distance[i][j];

    vector<vector<int>> minCost(1 << cityCount, vector<int>(cityCount, INT_MAX));
    minCost[1][0] = 0;

    for (int mask = 1; mask < (1 << cityCount); ++mask) {
        for (int last = 0; last < cityCount; ++last) {
            if (mask & (1 << last)) {
                int prevMask = mask ^ (1 << last);
                for (int prev = 0; prev < cityCount; ++prev) {
                    if (prevMask & (1 << prev)) {
                        minCost[mask][last] = min(minCost[mask][last], minCost[prevMask][prev] + distance[prev][last]);
                    }
                }
            }
        }
    }

    int result = INT_MAX;
    int fullMask = (1 << cityCount) - 1;
    for (int i = 0; i < cityCount; ++i)
        result = min(result, minCost[fullMask][i] + distance[i][0]);
    cout << result;
    return 0;
}