Algorithmic Solutions for Competitive Programming Problems

Extracting Initial Characters from Input Strings

When solving problems that require extracting the first letters of words from input strings, a direct character-by-character approach can be effective:

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

int main() {
    string input;
    getline(cin, input);
    string result = "";
    int wordsNeeded = 3;
    
    for (int i = 0; wordsNeeded > 0 && i < input.length(); i++) {
        if (i == 0 || input[i-1] == ' ') {
            result += input[i];
            wordsNeeded--;
        }
    }
    cout << result << endl;
    return 0;
}

When using getline after cin operations, be aware that a newline character might remain in the input buffer. To handle this, include cin.ignore() after cin to consume the leftover newline.

Counting Divisible Numbers in Large Ranges

Given three numbers a, b, and x, we need to determine how many integers y in the range [a, b] are divisible by x. The constraints are substantial: 0 ≤ a, b ≤ 10^18 and 1 ≤ x ≤ 10^18.

A naive approach of calculating floor((b-a+1)/x) is incorrect because the distribution of divisible numbers isn't uniform across arbitrary ranges. Instead, we should identify the smallest number ≥ a that's divisible by x and the largest number ≤ b that's divisible by x.

#include <iostream>
using namespace std;

long long countDivisible(long long lower, long long upper, long long divisor) {
    // Find the smallest number >= lower divisible by divisor
    long long firstDivisible = ((lower + divisor - 1) / divisor) * divisor;
    // Find the largest number <= upper divisible by divisor
    long long lastDivisible = (upper / divisor) * divisor;
    
    if (firstDivisible > lastDivisible) return 0;
    return (lastDivisible - firstDivisible) / divisor + 1;
}

int main() {
    long long a, b, x;
    cin >> a >> b >> x;
    cout << countDivisible(a, b, x) << endl;
    return 0;
}

Minimizing Operations for Adjacent Constraints

Consider a sequence of N boxes, each containing a specific number of candies. We can perform operations to remove one candy from any box. The objective is to minimize operations such that the sum of candies in any two adjacent boxes does not exceed a given threshold x.

An optimal strategy involves processing sequentially from one end of the sequence. For each adjacent pair (i, i+1), if their sum exceeds x, we remove candies from box i+1. This greedy approach ensures that each operation only affects the current constraint without creating new problems with previously processed boxes.

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

int minimizeOperations(vector<int>& candyCounts, int threshold) {
    int operations = 0;
    int numBoxes = candyCounts.size();
    
    for (int i = 0; i < numBoxes - 1; i++) {
        int adjacentSum = candyCounts[i] + candyCounts[i+1];
        if (adjacentSum > threshold) {
            // Remove excess from the right box
            int excess = adjacentSum - threshold;
            candyCounts[i+1] -= excess;
            operations += excess;
        }
    }
    return operations;
}

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> candies(n);
    for (int i = 0; i < n; i++) {
        cin >> candies[i];
    }
    cout << minimizeOperations(candies, x) << endl;
    return 0;
}

Game Theory: String Character Removal Game

Consider a game played on a string s (length ≥ 3) with no adjacent identical characters. Two players alternately remove a character (not at the ends) that doesn't create adjacent identical characters. Alice moves first, and the player who cannot make a move loses.

The outcome depends on the characters at the ends and the length of the string. If the end characters are the same, the first player wins if the number of internal characters is even. If the end characters are different, the first player wins if the number of internal characters is odd.

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

string determineGameWinner(string gameString) {
    char firstChar = gameString[0];
    char lastChar = gameString.back();
    int internalChars = gameString.length() - 2;
    
    if (firstChar == lastChar) {
        return (internalChars % 2 == 0) ? "First" : "Second";
    } else {
        return (internalChars % 2 == 1) ? "First" : "Second";
    }
}

int main() {
    string s;
    cin >> s;
    cout << determineGameWinner(s) << endl;
    return 0;
}