Calculating Paths in Dynamic Graphs
To determine the total number of simple paths in a Directed Acyclic Graph (DAG), we analyze the in-degrees and out-degrees. Let $fwd_dp[i]$ be the number of paths ending at node $i$. This can be computed using topological sorting. The total number of paths in the original graph is $\sum fwd_dp[i]$ for all nodes $i$ where $out_degree[i] = 0$.
By reversing the edges and performing another topological sort, we calculate $rev_dp[i]$, the number of paths starting at node $i$. For any edge $x \to y$, the number of paths passing through this specific edge is $fwd_dp[x] \times rev_dp[y]$.
When adding or removing an edge, we must adjust the total path count. If removing an edge causes $x$ or $y$ to become a new leaf or root, we add their individual contributions ($fwd_dp[x]$ or $rev_dp[y]$). If adding an edge makes them no longer terminal nodes, we subtract those values accordingly.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
struct PathProcessor {
int size;
vector<vector<int>> adj;
vector<int> degree;
vector<ll> counts;
PathProcessor(int n) : size(n), adj(n + 1), degree(n + 1, 0), counts(n + 1, 0) {}
void connect(int u, int v) {
adj[u].push_back(v);
degree[v]++;
}
void compute() {
queue<int> q;
for (int i = 1; i <= size; ++i) {
if (degree[i] == 0) {
q.push(i);
counts[i] = 1;
}
}
while (!q.empty()) {
int curr = q.front();
q.pop();
for (int neighbor : adj[curr]) {
counts[neighbor] = (counts[neighbor] + counts[curr]) % MOD;
if (--degree[neighbor] == 0) q.push(neighbor);
}
}
}
};
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, queries;
cin >> n >> m >> queries;
PathProcessor fwd(n), rev(n);
vector<int> in_deg(n + 1, 0), out_deg(n + 1, 0);
for (int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
fwd.connect(u, v); rev.connect(v, u);
out_deg[u]++; in_deg[v]++;
}
fwd.compute(); rev.compute();
ll current_total = 0;
for (int i = 1; i <= n; ++i) {
if (out_deg[i] == 0) current_total = (current_total + fwd.counts[i]) % MOD;
}
cout << current_total << "\n";
while (queries--) {
int type, u, v;
cin >> type >> u >> v;
ll modified = current_total;
ll edge_contribution = (fwd.counts[u] * rev.counts[v]) % MOD;
if (type == 1) {
modified = (modified - edge_contribution + MOD) % MOD;
if (in_deg[v] == 1) modified = (modified + rev.counts[v]) % MOD;
if (out_deg[u] == 1) modified = (modified + fwd.counts[u]) % MOD;
} else {
modified = (modified + edge_contribution) % MOD;
if (in_deg[v] == 0) modified = (modified - rev.counts[v] + MOD) % MOD;
if (out_deg[u] == 0) modified = (modified - fwd.counts[u] + MOD) % MOD;
}
cout << modified << "\n";
}
return 0;
}
Square Sequence Construction
A sequence derived from the differences of squares $i^2 - (i-1)^2$ results in odd numbers. For a generalized sequence where each element interacts with the element at index $i-m$, we apply a recurrence based on the offset $m$. By iteratively adding the value from $i-m$ to the current difference, we satisfy the sequence requirements.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<long long> series(n + 1);
for (long long i = 1; i <= n; ++i) {
series[i] = i * i - (i - 1) * (i - 1);
}
for (int i = m; i <= n; ++i) {
series[i] += series[i - m];
}
for (int i = 1; i <= n; ++i) {
cout << series[i] << (i == n ? "" : " ");
}
return 0;
}
Sequence Variance Minimization
To minimize the variance $\sum(\bar{a} - a_i)^2$, elements must be as close to the mean as possible. Since we can perform an arbitrary number of transfers, the resulting sequence should be monotonically non-decreasing. We use a monotonic stack to maintain segments of equal average value. If a new element (or segment) has a lower average than the top of the stack, we merge them and recalculate the combined average.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct Block {
long long total_sum;
long long count;
};
int main() {
int n;
cin >> n;
vector<int> vals(n);
for (int &x : vals) cin >> x;
stack<Block> s;
for (int x : vals) {
long long cur_sum = x, cur_count = 1;
while (!s.empty() && cur_sum * s.top().count < s.top().total_sum * cur_count) {
cur_sum += s.top().total_sum;
cur_count += s.top().count;
s.pop();
}
s.push({cur_sum, cur_count});
}
// Output calculation logic based on average blocks...
return 0;
}
Weighted Inversion Pairs
Calculating the cost of sorting through swaps can be modeled by finding how many smaller elements exist to the right of each element $a_i$. The contribution of $a_i$ is defined as $a_i \times (\text{count of smaller elements}) + (\text{sum of those smaller elements})$. Two Binary Indexed Trees (BIT) are used: one to track the frequency of values and another to track the sum of values encountered.
#include <iostream>
#include <vector>
using namespace std;
template<typename T>
struct FenwickTree {
int limit;
vector<T> tree;
FenwickTree(int n) : limit(n), tree(n + 1, 0) {}
void add(int idx, T val) {
for (; idx <= limit; idx += idx & -idx) tree[idx] += val;
}
T query(int idx) {
T res = 0;
for (; idx > 0; idx -= idx & -idx) res += tree[idx];
return res;
}
};
int main() {
int n; cin >> n;
vector<int> a(n);
int max_val = 0;
for (int &x : a) {
cin >> x;
max_val = max(max_val, x);
}
FenwickTree<long long> sum_bit(max_val), count_bit(max_val);
for (int x : a) {
sum_bit.add(x, x);
count_bit.add(x, 1);
}
long long total_cost = 0;
for (int x : a) {
total_cost += count_bit.query(x - 1) * x + sum_bit.query(x - 1);
sum_bit.add(x, -x);
count_bit.add(x, -1);
}
cout << total_cost << endl;
return 0;
}
Maximum Latency Optimization
In scenarios where we need to minimize the maximum time (latency), binary search on the result is an effective strategy. For a given threshold $mid$, we check if its possible to satisfy all interval constraints. For segments exceeding $mid$, we calculate the intersection of their intervals. If the remaining lengths after considering this intersection are within $mid$, the threshold is valid.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool is_feasible(int mid, int n, const vector<pair<int, int>>& intervals) {
int left_bound = 0, right_bound = n;
for (auto& p : intervals) {
if (p.second - p.first > mid) {
left_bound = max(left_bound, p.first);
right_bound = min(right_bound, p.second);
}
}
int overlap = max(0, right_bound - left_bound);
for (auto& p : intervals) {
if (p.second - p.first - overlap > mid) return false;
}
return true;
}
int main() {
int n, m; cin >> n >> m;
vector<pair<int, int>> data(m);
int high = 0;
for (auto& p : data) {
cin >> p.first >> p.second;
high = max(high, p.second - p.first);
}
int low = 0, result = high;
while (low <= high) {
int mid = low + (high - low) / 2;
if (is_feasible(mid, n, data)) {
result = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
cout << result << endl;
return 0;
}
State-Based Boss Battles using Dijkstra
We can model a boss battle as a graph where each node represents the boss's current health. An attack $a_i$ transitions the boss from health $H$ to $\max(0, H - a_i)$. The edge weight is the attack damage $b_{new_H}$ received at the resulting health state. Finding the minimum damage to defeat the boss is equivalent to finding the shortest path from health $M$ to health $0$.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long INF = 1e18;
void solve_dijkstra() {
int n, m; cin >> n >> m;
vector<int> attacks(n), boss_dmg(m + 1);
for (int &x : attacks) cin >> x;
for (int i = 1; i <= m; ++i) cin >> boss_dmg[i];
vector<long long> min_dmg(m + 1, INF);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
min_dmg[m] = 0;
pq.push({0, m});
while (!pq.empty()) {
auto [d, curr_hp] = pq.top(); pq.pop();
if (d > min_dmg[curr_hp]) continue;
for (int pwr : attacks) {
int next_hp = max(0, curr_hp - pwr);
int damage_taken = boss_dmg[next_hp];
if (min_dmg[next_hp] > d + damage_taken) {
min_dmg[next_hp] = d + damage_taken;
pq.push({min_dmg[next_hp], next_hp});
}
}
}
cout << min_dmg[0] << endl;
}
Character Segregation Cost
To arrange a string such that all digits are on one side and alphabets on the other, we evaluate two target configurations: digits-left/alphabets-right and vice-versa. The cost for each case is the number of characters that must be changed or moved to achieve the target state.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
int n; cin >> n;
string s; cin >> s;
int total_digits = 0, total_alphas = 0;
for (char c : s) {
if (isdigit(c)) total_digits++;
else total_alphas++;
}
int cost1 = 0;
for (int i = 0; i < total_digits; ++i) {
if (!isdigit(s[i])) cost1++;
}
int cost2 = 0;
for (int i = 0; i < total_alphas; ++i) {
if (isdigit(s[i])) cost2++;
}
cout << min(cost1, cost2) << endl;
return 0;
}
Time Analysis in Problem Solving
When tasks are completed in an arbitrary order, but completion times are cumulative, we extract the duration of each task by subtracting the end time of the previous task. The total time spent is the sum of these derived durations, plus any static penalties associated with the number of tasks.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n; cin >> n;
vector<int> timestamps(n);
for (int &t : timestamps) cin >> t;
int elapsed = 0, total_score = 0;
for (int t : timestamps) {
int duration = t;
for (int other : timestamps) {
if (other < t) duration = min(duration, t - other);
}
elapsed += duration;
total_score += elapsed;
}
for (int i = 0; i < n; ++i) {
int penalty; cin >> penalty;
total_score += penalty * 20;
}
cout << total_score << endl;
return 0;
}