Comprehensive Solutions for AtCoder ABC 065

<div> <h3>Problem 1: Freshness Assessment</h3> Objective: Determine the condition of food consumed after a delay. You possess an item with A days of remaining shelf life. You intend to consume it after B days. Consuming food that is already expired does not cause illness unless the time past the expiration date exceeds a threshold X. If the food is fresh, it tastes good. If it is expired but within the tolerance range X, it is safe. Beyond that, it poses a health risk. Methodology: Calculate the number of days passed relative to the expiration date. If A − B ≥ 0, the food has not expired yet. Otherwise, determine the extent of expiration. If the duration past expiration (B − A) is less than or equal to X, the result is acceptable. Any excess results in a critical status. Implementation: <pre><code>int main() { int limitDays, currentDaysLeft, waitTime; std::cin >> limitDays >> currentDaysLeft >> waitTime; int diff = currentDaysLeft - waitTime; if (diff >= 0) { std::cout << "delicious" << std::endl; } else { int exceeded = waitTime - currentDaysLeft; if (exceeded <= limitDays) { std::cout << "safe" << std::endl; } else { std::cout << "dangerous" << std::endl; } } return 0; }</code></pre> <hr> <h3>Problem 2: Lamp Control Sequence</h3> Objective: Navigate a directed graph representing lamp switches to reach a target state with minimum operations. There are N lamps numbered 1 through N. Initially, lamp 1 is active. Pressing the switch on lamp i toggles it off and activates lamp a[i]. Determine the minimum presses to activate lamp 2, or return -1 if impossible. Methodology: This forms a functional graph where each node has exactly one outgoing edge. Starting from node 1, we trace the path. Since the graph size is finite, the path must eventually enter a cycle. If node 2 appears in the trajectory from node 1, record the steps. If node 2 is not found before entering a previously visited node, it is unreachable. Implementation: <pre><code>void solve() { int numLamps; std::cin >> numLamps; std::vector<int> nextState(numLamps + 1); for(int i = 1; i <= numLamps; ++i) { std::cin >> nextState[i]; } std::vector<bool> visited(numLamps + 1, false); int curr = 1; int steps = 0; // Traverse until target found or cycle detected while(!visited[curr]) { visited[curr] = true; curr = nextState[curr]; steps++; if(curr == 2) { std::cout << steps - 1 << "\n"; return; } } // Target not reached before loop closure std::cout << "-1" << "\n"; } </code></pre> <hr> <h3>Problem 3: Animal Arrangements</h3> Objective: Count the number of ways to arrange N dogs and M cats in a line such that no two animals of the same species stand adjacent. Methodology: Valid arrangements require alternating types. This implies the absolute difference between the counts |N - M| cannot exceed 1. If the difference is greater than 1, the answer is 0. If N == M, the pattern can start with either a dog or a cat (2 choices), multiplied by the permutations of individual dogs and cats (N! × M!). If |N - M| == 1, the species with the higher count must start and end, leaving only 1 pattern configuration for species order, multiplied by internal permutations. Since results can be large, compute modulo 1E9 + 7. Implemantation: <pre><code>const int MOD_VAL = 1e9 + 7; long long factorial[100005]; void precompute() { factorial[0] = 1; for (int i = 1; i <= 100000; i++) { factorial[i] = (factorial[i - 1] * i) % MOD_VAL; } } void solve() { precompute(); int n, m; std::cin >> n >> m; if (std::abs(n - m) > 1) { std::cout << 0 << "\n"; return; } long long result = (factorial[n] * factorial[m]) % MOD_VAL; if (n == m) { result = (result * 2) % MOD_VAL; } std::cout << result << "\n"; } </code></pre> <hr> <h3>Problem 4: Connect Townships</h3> Objective: Find the minimum cost to connect all towns given their 2D coordinates. The cost between town i and j is min(|xi - xj|, |yi - yj|). Methodology: This is a Minimum Spanning Tree (MST) problem. Calculating all possible edges yields <math>O(N^2)</math> edges, which is too slow for N = 10^5. Observation dictates that for any dimension (X or Y), optimal edges exist only between geometrically adjacent points when sorted by that coordinate. Therefore, we sort the points by X, add edges between neighbors, repeat for Y, resulting in roughly <math>4N</math> candidate edges. Runing Kruskal's algorithm on this reduced set provides the solution efficiently. Implementation: <pre><code>struct Point { int x, y, id; }; struct Connection { int u, v, w; bool operator<(Connection const> other) const { return w < other.w; } }; struct DSU { std::vector<int> parent; DSU(int n) { parent.resize(n + 1); std::iota(parent.begin(), parent.end(), 0); } int find(int i) { if (parent[i] == i) return i; return parent[i] = find(parent[i]); } void unite(int i, int j) { int rootI = find(i); int rootJ = find(j); if (rootI != rootJ) parent[rootI] = rootJ; } }; void solve() { int N; std::cin >> N; std::vector<Point> cities(N); for (int i = 0; i < N; i++) { std::cin >> cities[i].x >> cities[i].y; cities[i].id = i; } std::vector<Connection> potentialEdges; auto sortAndAdd = [&](int axisIdx) { std::sort(cities.begin(), cities.end(), [axisIdx](Point const> a, Point const> b) { return (axisIdx == 0) ? a.x < b.x : a.y < b.y; }); for (int i = 1; i < N; i++) { Connection edge; edge.u = cities[i-1].id; edge.v = cities[i].id; edge.w = (axisIdx == 0) ? (cities[i].x - cities[i-1].x) : (cities[i].y - cities[i-1].y); potentialEdges.push_back(edge); } }; sortAndAdd(0); sortAndAdd(1); std::sort(potentialEdges.begin(), potentialEdges.end()); DSU dsu(N); long long totalCost = 0; int edgesCount = 0; for (const auto& edge : potentialEdges) { if (dsu.find(edge.u) != dsu.finnd(edge.v)) { dsu.unite(edge.u, edge.v); totalCost = (totalCost + edge.w) % 1000000007; edgesCount++; if (edgesCount == N - 1) break; } } std::cout << totalCost << "\n"; } </code></pre> </div>

Tags: AtCoder Competitive Programming Beginner Contest C++ Problem Solving

Posted on Thu, 07 May 2026 07:56:10 +0000 by phpvn.org

Freaks City

Comprehensive Solutions for AtCoder ABC 065

Hot Tags