Machine Translation Software (Queue Simulation)

Problem Description

A translation software maintains a memory buffer with M slots. When translating a word, the system first checks if the word exists in memory. If found, no external lookup is needed. Otherwise, it searches the dictionary, stores the word in memory, and increments the lookup counter.

When memory is full and a new word needs to be stored, the oldest word is evicted using a FIFO strategy.

Solution Approach

Use a queue data structure to simulate the memory management. Track the number of dictionary lookups separately.

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

int main() {
    int M, N;
    cin >> M >> N;
    vector<int> words(N);
    for (int i = 0; i < N; i++) cin >> words[i];
    
    vector<int> memory;
    unordered_set<int> lookup;
    int dictionaryLookups = 0;
    
    for (int word : words) {
        if (lookup.find(word) == lookup.end()) {
            dictionaryLookups++;
            lookup.insert(word);
            memory.push_back(word);
            if ((int)memory.size() > M) {
                int evicted = memory.front();
                memory.erase(memory.begin());
                lookup.erase(evicted);
            }
        }
    }
    
    cout << dictionaryLookups << endl;
    return 0;
}

Turtle Chess Game (Four-Dimensional Dynamic Programming)

Problem Description

A turtle piece starts at position 1 on a board with N cells, each containing a score. There are M cards, each with a value from 1 to 4, representing how many steps the turtle moves. Each card can only be used once, and all cards must be used exactly once to reach position N.

The total score equals the sum of all visited cell scores. Find the maximum possible score.

Solution Approach

This is a 4D DP problem where the state represents the number of cards of each type used. Let dp[a][b][c][d] represent the maximum score achievable using a cards of type 1, b cards of type 2, c cards of type 3, and d cards of type 4.

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> score(N);
    for (int i = 0; i < N; i++) cin >> score[i];
    
    vector<int> cnt(5, 0);
    for (int i = 0; i < M; i++) {
        int x; cin >> x;
        cnt[x]++;
    }
    
    int maxScore[41][41][41][41] = {0};
    maxScore[0][0][0][0] = score[0];
    
    for (int a = 0; a <= cnt[1]; a++) {
        for (int b = 0; b <= cnt[2]; b++) {
            for (int c = 0; c <= cnt[3]; c++) {
                for (int d = 0; d <= cnt[4]; d++) {
                    if (a == 0 && b == 0 && c == 0 && d == 0) continue;
                    int pos = a + b * 2 + c * 3 + d * 4;
                    int best = 0;
                    if (a > 0) best = max(best, maxScore[a-1][b][c][d]);
                    if (b > 0) best = max(best, maxScore[a][b-1][c][d]);
                    if (c > 0) best = max(best, maxScore[a][b][c-1][d]);
                    if (d > 0) best = max(best, maxScore[a][b][c][d-1]);
                    maxScore[a][b][c][d] = best + score[pos];
                }
            }
        }
    }
    
    cout << maxScore[cnt[1]][cnt[2]][cnt[3]][cnt[4]] << endl;
    return 0;
}

Prisoner Conflict (Union-Find with Greedy Strategy)

Problem Description

N prisoners must be divided into two prisons. Each pair of prisoners has a conflict value. If two prisoners with conflict are in the same prison, a conflict event occurs. The mayor only checks the largest conflict event. Find the minimum possible largest conflict value.

Solution Approach

Sort all conflicts in descending order. Process from highest to lowest, attempting to separate conflicting prisoners into different prisons. If two prisoners in the current conflict are already in the same set, this is the answer.

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

struct Conflict {
    int prisoner1, prisoner2, value;
};

int findParent(int x, vector<int>& parent) {
    return parent[x] == x ? x : parent[x] = findParent(parent[x], parent);
}

bool unionSets(int x, int y, vector<int>& parent) {
    int px = findParent(x, parent);
    int py = findParent(y, parent);
    if (px == py) return false;
    parent[px] = py;
    return true;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<Conflict> conflicts(M);
    for (int i = 0; i < M; i++) {
        cin >> conflicts[i].prisoner1 >> conflicts[i].prisoner2 >> conflicts[i].value;
    }
    
    sort(conflicts.begin(), conflicts.end(), [](const Conflict& a, const Conflict& b) {
        return a.value > b.value;
    });
    
    vector<int> parent(N * 2 + 1);
    for (int i = 1; i <= N * 2; i++) parent[i] = i;
    
    for (const auto& c : conflicts) {
        int p1 = c.prisoner1;
        int p2 = c.prisoner2;
        
        if (findParent(p1, parent) == findParent(p2, parent)) {
            cout << c.value << endl;
            return 0;
        }
        
        unionSets(p1, p2 + N, parent);
        unionSets(p2, p1 + N, parent);
    }
    
    cout << 0 << endl;
    return 0;
}

Water Supply System (BFS with Interval Covering)

Problem Description

An N×M grid represents cities with different elevations. Water source stations can only be built in the first row. A water station can be built in any cell if there exists an adjacent cell (sharing an edge) with higher elevation that already has a water facility.

All cities in the last row must have water facilities. Determine if this is possible, and if so, find the minimum number of water source stations needed.

Solution Approach

Perform BFS from each potential source in the first row to determine which cells in the last row can be reached. Each source covers a continuous interval in the last row. Then solve as a minimum interval covering problem.

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> elevation(N, vector<int>(M));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> elevation[i][j];
    
    vector<vector<int>> visited(N, vector<int>(M, -1));
    vector<pair<int, int>> coverage(M, {-1, -1});
    
    for (int start = 0; start < M; start++) {
        queue<pair<int, int>> q;
        q.emplace(0, start);
        visited[0][start] = start;
        
        while (!q.empty()) {
            auto [row, col] = q.front(); q.pop();
            int directions[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
            for (auto& dir : directions) {
                int nr = row + dir[0], nc = col + dir[1];
                if (nr >= 0 && nr < N && nc >= 0 && nc < M &&
                    visited[nr][nc] != start &&
                    elevation[nr][nc] < elevation[row][col]) {
                    visited[nr][nc] = start;
                    q.emplace(nr, nc);
                }
            }
        }
        
        int left = -1, right = -1;
        for (int j = 0; j < M; j++) {
            if (visited[N-1][j] == start) { left = j; break; }
        }
        for (int j = M-1; j >= 0; j--) {
            if (visited[N-1][j] == start) { right = j; break; }
        }
        if (left != -1) coverage[start] = {left, right};
    }
    
    int unreachable = 0;
    for (int j = 0; j < M; j++)
        if (visited[N-1][j] == -1) unreachable++;
    
    if (unreachable > 0) {
        cout << 0 << "\n" << unreachable << endl;
        return 0;
    }
    
    int count = 0, current = 0;
    while (current < M) {
        int farthest = current;
        for (int i = 0; i < M; i++) {
            if (coverage[i].first <= current)
                farthest = max(farthest, coverage[i].second);
        }
        current = farthest + 1;
        count++;
    }
    
    cout << 1 << "\n" << count << endl;
    return 0;
}

These four problems represent classic algorithmic challenges from NOIP 2010, covering queue simulation, multi-dimensional dynamic programming, union-find data structures with greedy processing, and graph traversal combined with interval covering techniques.