Minimum Path Validation

To determine if a destination point can be reached from a starting position using fixed step sizes, check if both coordinate differences are divisible by their respective step increments. Additionally, the sum of the resulting quotients must be even.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

bool isReachable(ll start_x, ll start_y, ll end_x, ll end_y, ll step_x, ll step_y) {
    ll diff_x = end_x - start_x;
    ll diff_y = end_y - start_y;
    
    if (diff_x % step_x != 0 || diff_y % step_y != 0) {
        return false;
    }
    
    ll quotient_sum = (diff_x / step_x) + (diff_y / step_y);
    return (quotient_sum % 2 == 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll x1, y1, x2, y2, dx, dy;
    cin >> x1 >> y1 >> x2 >> y2 >> dx >> dy;
    
    cout << (isReachable(x1, y1, x2, y2, dx, dy) ? "YES" : "NO") << "\n";
    return 0;
}

Triplet Combination Counting

After sorting an array, the product of the three smallest elements yields the minimum possible product. Let these values be denoted as first, second, and third. The count of occurrences of the third element determines the calculation method:

1. When all three elements are identical, select any three from the total count: count * (count-1) * (count-2) / 6
2. When the first two elements are equal but less than the third, or when all three are distinct, multiply by the count of third elements
3. When the second and third elements are equal but greater than the first, choose two from the count: count * (count-1) / 2

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll calculateCombinations(vector<ll>& values) {
    sort(values.begin(), values.end());
    
    ll first = values[0];
    ll second = values[1];
    ll third = values[2];
    
    ll frequency = count(values.begin(), values.end(), third);
    
    if (first == second && second == third) {
        return frequency * (frequency - 1) * (frequency - 2) / 6;
    }
    else if (first == second || second < third) {
        return frequency;
    }
    else if (second == third) {
        return frequency * (frequency - 1) / 2;
    }
    
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll size;
    cin >> size;
    vector<ll> data(size);
    
    for (ll& item : data) {
        cin >> item;
    }
    
    cout << calculateCombinations(data) << "\n";
    return 0;
}

Large Number Enumeration

For numbers where the difference between the value and its digit sum meets a threshold, binary search efficiently iedntifies the soltuion range. The search space spans from 1 to 10^18, with the valid count being the numbers from the found boundary to n.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll computeDigitSum(ll number) {
    ll total = 0;
    while (number > 0) {
        total += number % 10;
        number /= 10;
    }
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll upper_bound, threshold;
    cin >> upper_bound >> threshold;
    
    ll left = 1, right = 1e18;
    
    while (left <= right) {
        ll middle = (left + right) / 2;
        if (middle - computeDigitSum(middle) >= threshold) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    
    ll result = (left > upper_bound) ? 0 : upper_bound - left + 1;
    cout << result << "\n";
    return 0;
}