Problem A

Given three integers A, B, and C, determine whether C falls within the range [A, B], i.e., check if A ≤ C ≤ B.

Solution

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

int main() {
    int first, last, target;
    cin >> first >> last >> target;
    
    if (first <= target && target <= last)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    
    return 0;
}

Problem B

Description There are N cities connected by M bidirectional roads. The i-th roadd connects city a_i and city b_i (where 1 ≤ a_i, b_i ≤ N). Determine how many roads are connected to each city.

Constraints:

1 ≤ N, M ≤ 50 1 ≤ a_i, b_i ≤ N a_i ≠ b_i

Solution The problem essentially asks for the degree of each vertex in an undirected graph.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<int> degree(n + 1, 0);
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        degree[u]++;
        degree[v]++;
    }
    
    for (int i = 1; i <= n; i++)
        cout << degree[i] << "\n";
    
    return 0;
}

Time Complexity: O(N + M)

Problem C

Description Start with an empty multiset. There are N operations. During the i-th operation, insert b_i copies of the value a_i into the multiset. Find the K-th smallest value after all insertions.

Constraints:

1 ≤ N, a_i, b_i ≤ 10^5 1 ≤ K ≤ Σ b_i

Solution Since the value are within reasonable bounds, we can use a frequency array and binary search on prefix sums to find the K-th smallest element.

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

const int MAXV = 100000 + 5;
ll freq[MAXV];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    ll K;
    cin >> N >> K;
    
    int maxVal = 0;
    for (int i = 0; i < N; i++) {
        int val, cnt;
        cin >> val >> cnt;
        freq[val] += cnt;
        maxVal = max(maxVal, val);
    }
    
    // Build prefix sums
    for (int i = 1; i <= maxVal; i++)
        freq[i] += freq[i - 1];
    
    // Binary search for K-th smallest
    int left = 0, right = maxVal + 1;
    while (right - left > 1) {
        int mid = left + (right - left) / 2;
        if (freq[mid] >= K)
            right = mid;
        else
            left = mid;
    }
    
    cout << right << "\n";
    return 0;
}

Time Complexity: O(N + log MAXV)

Problem D

Description Consider a directed graph with N vertices and M edges. The i-th edge goes from vertex a_i to vertex b_i with weight c_i.

A chess piece starts at vertex 1. Players can move the piece along directed edges and may end the game at vertex N. It is guaranteed that there exists at least one path from vertex 1 to vertex N.

When moving from u to v, the player earns c_{e(u,v)} points. Determine the maximum achievable score when ending the game. If infinite score is possible, output "inf".

Constraints:

2 ≤ N ≤ 100 1 ≤ M ≤ min(N(N-1)/2, 2000) -10^9 ≤ c_i ≤ 10^9 No self-loops or parallel edges

Solution Overview

Key Insight: If there exists a positive cycle reachable from vertex 1 and from which vertex N is reachable, then the player can earn infinite points by looping indefinietly on that cycle.

Otherwise, we need to find the longest path from vertex 1 to vertex N.

1. Detecting Positive Cycles

To detect positive cycles, we transform the problem by negating all edge weights. Finding a positive cycle in the original graph is equivalent to finding a negative cycle in the transformed graph.

The Bellman-Ford algorithm can detect negative cycles. If during the N-th iteration a distance can still be relaxed, a negative cycle exists. We then perform additional iterations to find all vertices reachable from such cycles.

2. Finding Longest Path

In graphs without positive cycles, the longest path can be found by applying Bellman-Ford on the negated edge weights (treating it as a shortest path problem).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL << 60);

struct Edge {
    int from, to;
    ll weight;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    cin >> N >> M;
    vector<Edge> edges(M);
    
    for (int i = 0; i < M; i++) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    
    // Create negated edge weights for shortest path
    vector<ll> dist(N + 1, INF);
    dist[1] = 0;
    
    // Standard Bellman-Ford relaxation
    for (int iter = 1; iter <= N; iter++) {
        for (int i = 0; i < M; i++) {
            int u = edges[i].from;
            int v = edges[i].to;
            ll w = -edges[i].weight;  // Negate for longest path
            
            if (dist[u] == INF) continue;
            if (dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }
    
    // Identify vertices affected by negative cycles
    vector<char> inNegCycle(N + 1, 0);
    vector<char> canReach(N + 1, 0);
    
    for (int i = 0; i < M; i++) {
        int u = edges[i].from;
        int v = edges[i].to;
        ll w = -edges[i].weight;
        
        if (dist[u] == INF) continue;
        if (dist[u] + w < dist[v]) {
            inNegCycle[v] = 1;
            canReach[v] = 1;
        }
    }
    
    // Propagate reachability from negative cycle vertices
    for (int iter = 1; iter <= N - 1; iter++) {
        for (int i = 0; i < M; i++) {
            int u = edges[i].from;
            int v = edges[i].to;
            
            if (canReach[u])
                canReach[v] = 1;
        }
    }
    
    if (canReach[N])
        cout << "inf\n";
    else
        cout << -dist[N] << "\n";
    
    return 0;
}

Time Complexity: O(N × M)

Space Complexity: O(N + M)