A. Programming Contest

This problem is a straightforward implementation task. The idea is to count the number of valid years betweeen two given years, excluding specific invalid years provided in the input.

void solve() {
    int n, m;
    std::cin >> n;
    std::vector<int> invalidYearFlag(10000, 0); // Assuming a safe upper bound for year range
    std::cin >> m;
    for(int i = 0; i < m; ++i) {
        int year;
        std::cin >> year;
        invalidYearFlag[year] = 1;
    }
    int upperBound;
    std::cin >> upperBound;
    int validCount = 0;
    for(int year = n; year <= upperBound; ++year) {
        if(!invalidYearFlag[year]) {
            validCount++;
        }
    }
    std::cout << validCount << std::endl;
}

C. Trading

The goal is to maximize profit by buying from the cheapest suppliers and selling to the most expensive buyers. This is achieved using a greedy approach with two pointers.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve() {
    ll n;
    std::cin >> n;
    std::vector<pair<ll, ll>> shops;
    for(ll i = 0; i < n; ++i) {
        ll buyPrice, stock;
        std::cin >> buyPrice >> stock;
        shops.push_back({buyPrice, stock});
    }
    ll totalProfit = 0;
    sort(shops.begin(), shops.end());
    int left = 0, right = n - 1;
    while(left < right) {
        ll minUnits = min(shops[left].second, shops[right].second);
        totalProfit += (shops[right].first - shops[left].first) * minUnits;
        shops[left].second -= minUnits;
        shops[right].second -= minUnits;
        if(shops[left].second == 0) left++;
        if(shops[right].second == 0) right--;
    }
    std::cout << totalProfit << std::endl;
}

D. New Houses

This problem involves optimziing satisfaction for residents based on weather they have neighbors or not. The solution involves sorting and prefix sums to efficiently compute maximum satisfaction for different configurations.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve() {
    ll n, m;
    std::cin >> n >> m;
    std::vector<ll> aloneSatisfaction(n + 1), withNeighborSatisfaction(n + 1);
    std::vector<ll> diff(n + 1);
    ll totalAlone = 0;
    for(int i = 1; i <= n; ++i) {
        std::cin >> withNeighborSatisfaction[i] >> aloneSatisfaction[i];
        diff[i] = withNeighborSatisfaction[i] - aloneSatisfaction[i];
        totalAlone += aloneSatisfaction[i];
    }
    sort(diff.begin() + 1, diff.end());
    ll maxSatisfaction = totalAlone;
    ll prefixSum = 0;
    for(int i = n; i >= 1; --i) {
        prefixSum += diff[i];
        if(2 * n - (n - i + 1) <= m) {
            maxSatisfaction = max(maxSatisfaction, totalAlone + prefixSum);
        }
    }
    if(m >= 2 * n - 1) {
        maxSatisfaction = max(maxSatisfaction, totalAlone);
    }
    std::cout << maxSatisfaction << std::endl;
}

I. Path Planning

The problem involves finding the maximum value $x$ such that there exists a path from the top-left to bottom-right of a grid where all values from 0 to $x-1$ appear in order. The solution uses binary search combined with a greedy check.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
vector<vector<int>> grid;

bool isValid(int x) {
    int lastColumn = -1;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(grid[i][j] < x) {
                if(j < lastColumn) return false;
                lastColumn = j;
            }
        }
    }
    return true;
}

void solve() {
    std::cin >> n >> m;
    grid.resize(n, vector<int>(m));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            std::cin >> grid[i][j];
        }
    }
    int low = 0, high = n * m;
    while(low < high) {
        int mid = (low + high + 1) / 2;
        if(isValid(mid)) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    std::cout << low << std::endl;
}

K. Peg Solitaire

This problem involves solving a peg solitaire game with a small board size. A depth-first search approach is used to explore all valid moves and track the minimum number of remaining pegs.

#include <bits/stdc++.h>

using namespace std;

int minPegs = 100;
int moveDeltas[4][2] = {{0,2},{2,0},{0,-2},{-2,0}};
int jumpDeltas[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

void dfs(int rows, int cols, vector<vector<int>>& board, int pegCount) {
    for(int i = 0; i < rows; ++i) {
        for(int j = 0; j < cols; ++j) {
            if(board[i][j]) {
                for(int d = 0; d < 4; ++d) {
                    int ni = i + moveDeltas[d][0];
                    int nj = j + moveDeltas[d][1];
                    int ji = i + jumpDeltas[d][0];
                    int jj = j + jumpDeltas[d][1];
                    if(ni >= 0 && ni < rows && nj >= 0 && nj < cols && board[ni][nj] == 0 && board[ji][jj] == 1) {
                        board[i][j] = 0;
                        board[ji][jj] = 0;
                        board[ni][nj] = 1;
                        dfs(rows, cols, board, pegCount - 1);
                        board[i][j] = 1;
                        board[ji][jj] = 1;
                        board[ni][nj] = 0;
                    }
                }
            }
        }
    }
    minPegs = min(minPegs, pegCount);
}

void solve() {
    int rows, cols, pegs;
    std::cin >> rows >> cols >> pegs;
    vector<vector<int>> board(rows, vector<int>(cols, 0));
    for(int i = 0; i < pegs; ++i) {
        int x, y;
        std::cin >> x >> y;
        board[x][y] = 1;
    }
    minPegs = pegs;
    for(int i = 0; i < rows; ++i) {
        for(int j = 0; j < cols; ++j) {
            if(board[i][j]) {
                dfs(rows, cols, board, pegs);
            }
        }
    }
    std::cout << minPegs << std::endl;
}