Preparation Strategy

Prior to a major algorithm competition, it is beneficial to maintain momentum by solving medium-difficulty problems within a time limit. This approach helps reinforce template usage and sharpens intuition without exhausting mental resources. The following selection covers common patterns including simulation, sorting, string manipulation, mathematics, and graph traversal.

Morning Schedule Analysis

This problem requires parsing time inputs and categorizing them based on specific minute ranges. The core logic involves converting hours and minutes into total minutes elapsed since midnight.

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

void processCase() {
    int count;
    cin >> count;
    int rangeA = 0;
    int rangeB = 0;
    
    for (int i = 0; i < count; ++i) {
        int h, m;
        char sep;
        cin >> h >> sep >> m;
        int totalMinutes = h * 60 + m;
        
        if (totalMinutes > 480 && totalMinutes <= 485) {
            rangeA++;
        } else if (totalMinutes > 485) {
            rangeB++;
        }
    }
    cout << rangeA << " " << rangeB << endl;
}

int main() {
    int t = 1;
    cin >> t;
    while (t--) {
        processCase();
    }
    return 0;
}

Maximum Divisible Number

Given a set of digits, the goal is to form the largest possible number. If the resulting number must be divisible by 10, the last digit must be zero. If no zero exists among the digits, formation is impossible under specific constraints.

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

int main() {
    int n;
    cin >> n;
    vector<int> digits(n);
    bool hasZero = false;
    
    for (int i = 0; i < n; ++i) {
        cin >> digits[i];
        if (digits[i] == 0) hasZero = true;
    }
    
    sort(digits.begin(), digits.end(), greater<int>());
    
    if (!hasZero) {
        for (int x : digits) cout << x;
        cout << endl;
        return 0;
    }
    
    long long result = 0;
    for (int x : digits) {
        result = result * 10 + x;
    }
    
    if (result % 10 == 0) {
        cout << result << endl;
    } else {
        cout << -1 << endl;
    }
    return 0;
}

Numeric String Rounding

This task involves implementing custom rounding logic on a string representation of a number. The algorithm processes digits from least significant to most significant, handling carry operations manually.

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

void solve() {
    int n;
    cin >> n;
    while (n--) {
        string s;
        cin >> s;
        reverse(s.begin(), s.end());
        s += '0'; // Padding for carry
        
        int carryIndex = -1;
        for (size_t i = 0; i < s.length() - 1; ++i) {
            if (s[i] >= '5') {
                s[i + 1]++;
                carryIndex = i;
            }
        }
        
        for (int i = 0; i <= carryIndex; ++i) {
            s[i] = '0';
        }
        
        if (s.back() == '0') s.pop_back();
        reverse(s.begin(), s.end());
        cout << s << endl;
    }
}

int main() {
    solve();
    return 0;
}

Constructive Math Problem

Determine two numbers based on sum and modulo constraints. A solution exists only if the sum is sufficient large compared to the modulo value.

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long sumVal, modVal;
        cin >> sumVal >> modVal;
        
        if (sumVal > 2 * modVal) {
            cout << modVal << " " << (sumVal - modVal) << endl;
        } else {
            cout << -1 << endl;
        }
    }
    return 0;
}

Integer Rounding to Nearest Ten

A straightforward arithmetic problem requiring rounding an integer to the nearest multiple of 10 using standard rounding rules.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int remainder = n % 10;
    int base = n / 10;
    
    if (remainder >= 5) {
        cout << (base + 1) * 10 << endl;
    } else {
        cout << base * 10 << endl;
    }
    return 0;
}

Circular Pattern Matching

To find occurrences of a substring in a circular string, concatenate the original string with itself. Then search for the pattern within the bounds of the original length.

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

int main() {
    string text, pattern;
    cin >> text >> pattern;
    int len = text.length();
    text += text;
    
    int count = 0;
    size_t pos = 0;
    
    while ((pos = text.find(pattern, pos)) != string::npos) {
        if (pos >= len) break;
        count++;
        pos++;
    }
    
    cout << count << endl;
    return 0;
}

Range Frequency Calculation

Use a difference array to handle range updates efficiently. After processing all updates, compute the prefix sum to find the actual values and determine the maximum frequency.

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

const int MAXN = 1000005;
int diffArr[MAXN];

int main() {
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            cin >> l >> r;
            diffArr[1]++;
            diffArr[l]--;
            diffArr[r + 1]++;
            diffArr[n + 1]--;
        } else {
            int idx;
            cin >> idx;
            if (type == 2) {
                diffArr[1]++;
                diffArr[idx]--;
            } else {
                diffArr[idx + 1]++;
                diffArr[n + 1]--;
            }
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        diffArr[i] += diffArr[i - 1];
    }
    
    int maxVal = 0;
    for (int i = 1; i <= n; ++i) {
        maxVal = max(maxVal, diffArr[i]);
    }
    
    int count = 0;
    for (int i = 1; i <= n; ++i) {
        if (diffArr[i] == maxVal) count++;
    }
    
    cout << maxVal << " " << count << endl;
    return 0;
}

Unique Elements in Grid

Count the number of distinct values present in a 2D grid. A hash set or map can track encountered values efficiently.

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

void solve() {
    int rows, cols;
    cin >> rows >> cols;
    unordered_set<int> uniqueValues;
    
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            int val;
            cin >> val;
            uniqueValues.insert(val);
        }
    }
    cout << uniqueValues.size() << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Sequence Validity Check

Verify if a sequence can be arranged such that adjacent elements differ by at least 1. Sorting the array allows checking for duplicates easily.

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

void solve() {
    int n;
    cin >> n;
    vector<long long> arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];
    
    sort(arr.begin(), arr.end());
    
    bool possible = true;
    for (int i = 0; i < n - 1; ++i) {
        if (arr[i] == arr[i + 1]) {
            possible = false;
            break;
        }
    }
    
    if (!possible) {
        cout << -1 << endl;
    } else {
        for (int i = 0; i < n; ++i) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Grid Traversal Count

Perform a BFS starting from a specific character to explore reachable cells. Count specific target characters encountered during the traversal.

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

int rows, cols;
vector<string> grid;
vector<vector<bool>> visited;
int targetCount = 0;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void bfs(int startX, int startY) {
    queue<pair<int, int>> q;
    q.push({startX, startY});
    visited[startX][startY] = true;
    
    while (!q.empty()) {
        auto curr = q.front();
        q.pop();
        
        for (int i = 0; i < 4; ++i) {
            int nx = curr.first + dx[i];
            int ny = curr.second + dy[i];
            
            if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue;
            if (visited[nx][ny]) continue;
            if (grid[nx][ny] == '#') continue;
            
            if (grid[nx][ny] == '!') targetCount++;
            
            visited[nx][ny] = true;
            q.push({nx, ny});
        }
    }
}

int main() {
    cin >> rows >> cols;
    grid.resize(rows);
    visited.assign(rows, vector<bool>(cols, false));
    
    int startX, startY;
    for (int i = 0; i < rows; ++i) {
        cin >> grid[i];
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == '@') {
                startX = i;
                startY = j;
            }
        }
    }
    
    bfs(startX, startY);
    cout << targetCount << endl;
    return 0;
}

Bitwise Subarray Logic

Track the positions of zero bits for each bit position across the array. The contribution of each element to the result depends on the nearest previous index where a bit was zero.

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

const int MAXN = 1000005;
int lastZeroPos[32];
int arr[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
    
    long long totalRes = 0;
    for (int i = 1; i <= n; ++i) {
        int minIdx = 1e9;
        for (int bit = 0; bit < 32; ++bit) {
            if (!((arr[i] >> bit) & 1)) {
                lastZeroPos[bit] = i;
            }
            minIdx = min(minIdx, lastZeroPos[bit]);
        }
        totalRes += minIdx;
    }
    
    cout << totalRes << endl;
    return 0;
}