Let's consider the calculation for the number of four-vertex subgraphs with at least x specific edges, denoted as f_x. Using the principle of inclusion-exclusion, the count of subgraphs with no edges at all is f_0 - f_1 + f_2 - f_3 + f_4 - f_5 + f_6. Meanwhile, the count of subgraphs with all six edges present is simply f_6. The difference we need is therefore the sum f_0 - f_1 + f_2 - f_3 + f_4 - f_5. Thus, the task reduces to computing f_0 through f_5.
Counting subgraphs on four vertices is straightforward for all patterns except the complete graph K_4. Established methods for counting triangles, quadrilaterals, and K_4 missing one edge can be effectively combined.
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef __int128 big_int;
big_int comb_4(ll n) { return (big_int)n * (n-1) * (n-2) * (n-3) / 24; }
big_int comb_3(ll n) { return (big_int)n * (n-1) * (n-2) / 6; }
big_int comb_2(ll n) { return (big_int)n * (n-1) / 2; }
int main() {
int vertex_cnt, edge_cnt;
cin >> vertex_cnt >> edge_cnt;
vector<vector<int>> graph(vertex_cnt + 1);
vector<int> deg(vertex_cnt + 1, 0);
vector<pair<int, int>> edges(edge_cnt);
for (int i = 0; i < edge_cnt; ++i) {
int u, v;
cin >> u >> v;
edges[i] = {u, v};
graph[u].push_back(v);
graph[v].push_back(u);
deg[u]++; deg[v]++;
}
big_int total = comb_4(vertex_cnt);
total -= (big_int)edge_cnt * comb_2(vertex_cnt - 2);
big_int temp_sum = 0;
for (auto &[u, v] : edges) {
temp_sum += (big_int)(deg[u] + deg[v] - 2) * (vertex_cnt - 4);
total -= (big_int)(deg[u] - 1) * (deg[v] - 1);
}
total += comb_2(edge_cnt) + (temp_sum / 2);
for (int v = 1; v <= vertex_cnt; ++v) {
total -= comb_3(deg[v]);
}
vector<vector<int>> directed_adj(vertex_cnt + 1);
vector<int> timestamp(vertex_cnt + 1, 0);
vector<int> pos_in_list(vertex_cnt + 1, 0);
int current_time = 0;
for (int v = 1; v <= vertex_cnt; ++v) {
current_time++;
int idx = 0;
for (int neighbor : graph[v]) {
if (deg[neighbor] > deg[v] || (deg[neighbor] == deg[v] && neighbor > v)) {
directed_adj[v].push_back(neighbor);
timestamp[neighbor] = current_time;
pos_in_list[neighbor] = idx++;
}
}
vector<int> edge_counter(idx, 0);
idx = 0;
for (int w : directed_adj[v]) {
int local_idx = 0;
for (int z : directed_adj[w]) {
if (timestamp[z] == current_time) {
total += deg[v] + deg[w] + deg[z] - vertex_cnt;
total -= edge_counter[idx]++;
total -= edge_counter[pos_in_list[z]]++;
}
local_idx++;
}
idx++;
}
}
if (total < 0) total = -total;
// Output logic for __int128 would be needed here.
return 0;
}
This is a standard problem that can be solved by coordinate compression followed by Boruvka's algorithm.
Why did I need to write a brute-force checker to debug this?
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int INF = 0x3f3f3f3f;
struct Edge { int u, v, w; };
int find_root(vector<int>& parent, int x) {
while (parent[x] != x) parent[x] = parent[parent[x]], x = parent[x];
return x;
}
int distance_on_line(const vector<int>& coords, int l, int r) {
if (l > r) swap(l, r);
return coords[r - 1] + 1 - coords[l];
}
void solve_case() {
int original_n, m;
cin >> original_n >> m;
vector<Edge> edges(m);
vector<int> points;
for (int i = 0; i < m; ++i) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
points.push_back(edges[i].u);
if (edges[i].u > 1) points.push_back(edges[i].u - 1);
points.push_back(edges[i].v);
if (edges[i].v > 1) points.push_back(edges[i].v - 1);
}
points.push_back(original_n);
sort(points.begin(), points.end());
points.erase(unique(points.begin(), points.end()), points.end());
int n = points.size();
vector<vector<pair<int, int>>> adj_list(n + 1);
vector<int> parent(n + 1);
for (int i = 1; i <= n; ++i) parent[i] = i;
ll total_cost = 0;
for (int i = 0; i < n; ++i) total_cost += points[i] - (i > 0 ? points[i-1] : 0) - 1;
for (auto &e : edges) {
int pu = lower_bound(points.begin(), points.end(), e.u) - points.begin() + 1;
int pv = lower_bound(points.begin(), points.end(), e.v) - points.begin() + 1;
adj_list[pu].emplace_back(pv, e.w);
adj_list[pv].emplace_back(pu, e.w);
}
int components_remaining = n - 1;
while (components_remaining > 0) {
vector<vector<int>> component_nodes(n + 1);
vector<int> nearest(n + 1, -1), best_edge_cost(n + 1, INF);
for (int i = 1; i <= n; ++i) {
component_nodes[find_root(parent, i)].push_back(i);
}
vector<int> prev_in_comp(n + 1, 0), next_in_comp(n + 1, 0);
vector<int> last_visitor(n + 1, -1);
for (int comp_id = 1; comp_id <= n; ++comp_id) {
if (component_nodes[comp_id].empty()) continue;
auto &nodes = component_nodes[comp_id];
sort(nodes.begin(), nodes.end());
int sz = nodes.size();
for (int j = 0; j < sz; ++j) {
int node = nodes[j];
if (j > 0 && nodes[j-1] == node - 1) prev_in_comp[node] = prev_in_comp[node-1];
else prev_in_comp[node] = node - 1;
}
for (int j = sz - 1; j >= 0; --j) {
int node = nodes[j];
if (j + 1 < sz && nodes[j+1] == node + 1) next_in_comp[node] = next_in_comp[node+1];
else next_in_comp[node] = node + 1;
}
for (int node : nodes) {
for (auto [neigh, weight] : adj_list[node]) {
if (find_root(parent, neigh) != comp_id && weight < best_edge_cost[comp_id]) {
best_edge_cost[comp_id] = weight;
nearest[comp_id] = neigh;
}
last_visitor[neigh] = node;
}
int candidate = node - 1;
while (candidate >= 1) {
if (last_visitor[candidate] == node) { candidate--; continue; }
if (find_root(parent, candidate) == comp_id) { candidate = prev_in_comp[candidate]; continue; }
int dist = distance_on_line(points, node, candidate);
if (dist < best_edge_cost[comp_id]) {
best_edge_cost[comp_id] = dist;
nearest[comp_id] = candidate;
}
break;
}
candidate = node + 1;
while (candidate <= n) {
if (last_visitor[candidate] == node) { candidate++; continue; }
if (find_root(parent, candidate) == comp_id) { candidate = next_in_comp[candidate]; continue; }
int dist = distance_on_line(points, node, candidate);
if (dist < best_edge_cost[comp_id]) {
best_edge_cost[comp_id] = dist;
nearest[comp_id] = candidate;
}
break;
}
}
}
for (int comp_id = 1; comp_id <= n; ++comp_id) {
if (nearest[comp_id] != -1) {
int root_a = find_root(parent, comp_id);
int root_b = find_root(parent, nearest[comp_id]);
if (root_a != root_b) {
parent[root_a] = root_b;
total_cost += best_edge_cost[comp_id];
components_remaining--;
}
}
}
}
cout << total_cost << '\n';
}
int main() {
int test_cases;
cin >> test_cases;
while (test_cases--) solve_case();
return 0;
}
This is an excellent problem! For speed, we outline the solution.
Assume that once two people meet, they stay together, effectively merging into a single entity with the combined burn time encreased by T.
Binary search on speed v. The problem reduces to having two queues. Each operation costs a distance to purchase the next person from a queue head, and then gains 2Tv distance. The question is whether we can empty both queues.
Consider a greedy merging strategy. If a losing move is folowed by a gaining move, inserting a move from the other queue in between is not beneficial. Thus, after merging strategies, we get two sequences: a prefix of gaining moves and a suffix of losing moves for each queue.
A key step: consider the gaining prefixes; they should be taken completely whenever possible. For the losing suffixes, think in reverse. The final cost is fixed, so starting from the end state and working backwards, we also take losing moves whenever possible. It suffices to check if we can empty both queues by greedily processing from both ends.
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
struct Move {
ll cost, gain;
Move combine(const Move& other) const {
return {max(cost, other.cost - gain), gain + other.gain};
}
};
bool can_finish(int n, int k, ll total_time, const vector<ll>& positions, ll speed) {
ll resource = (ll)n * speed - (positions.back() - positions.front());
if (resource < 0) return false;
vector<Move> left_moves, right_moves;
int left_cnt = 0, right_cnt = 0;
for (int i = k; i > 1; --i) {
ll dist = positions[i] - positions[i-1];
Move cur_move = {dist, speed - dist};
while (cur_move.gain >= 0 && left_cnt > 0 && left_moves[left_cnt-1].gain < 0) {
cur_move = left_moves[--left_cnt].combine(cur_move);
}
left_moves[left_cnt++] = cur_move;
}
for (int i = k; i < n; ++i) {
ll dist = positions[i+1] - positions[i];
Move cur_move = {dist, speed - dist};
while (cur_move.gain >= 0 && right_cnt > 0 && right_moves[right_cnt-1].gain < 0) {
cur_move = right_moves[--right_cnt].combine(cur_move);
}
right_moves[right_cnt++] = cur_move;
}
bool changed = true;
while (changed) {
changed = false;
while (left_cnt > 0 && left_moves[left_cnt-1].gain < 0 && resource - left_moves[left_cnt-1].gain >= left_moves[left_cnt-1].cost) {
resource -= left_moves[--left_cnt].gain;
changed = true;
}
while (right_cnt > 0 && right_moves[right_cnt-1].gain < 0 && resource - right_moves[right_cnt-1].gain >= right_moves[right_cnt-1].cost) {
resource -= right_moves[--right_cnt].gain;
changed = true;
}
}
int left_ptr = 0, right_ptr = 0;
changed = true;
resource = speed;
while (changed) {
changed = false;
while (left_ptr < left_cnt && left_moves[left_ptr].gain >= 0 && resource >= left_moves[left_ptr].cost) {
resource += left_moves[left_ptr++].gain;
changed = true;
}
while (right_ptr < right_cnt && right_moves[right_ptr].gain >= 0 && resource >= right_moves[right_ptr].cost) {
resource += right_moves[right_ptr++].gain;
changed = true;
}
}
return left_ptr >= left_cnt && right_ptr >= right_cnt;
}
int main() {
int n, k;
ll T;
cin >> n >> k >> T;
vector<ll> pos(n+1);
for (int i = 1; i <= n; ++i) cin >> pos[i];
ll low = 0, high = ceil(5e8 / T); // Upper bound for binary search
while (low < high) {
ll mid = (low + high) / 2;
if (can_finish(n, k, T, pos, 2 * mid * T)) high = mid;
else low = mid + 1;
}
cout << low << '\n';
return 0;
}
What bizarre pattern-based problem. Look at the constraints—it seems impossible to plan directly!
By brute-forcing small cases, a pattern emerges that maximizes the value:
**********0*
011111111111
000000******
000000000000
The principle is understandable. For instance, the string that achieves maximum matching ensures all wildcard match lengths are zero, consuming substantial energy.
The energy calculation for the lower part is straightforward and quadratic. For the upper part, using combinatorial formulas and column sum identities yields C(2n-1, n+1) + C(2n-3, n-2), solving the problem.
#include <iostream>
using namespace std;
const int MOD = 1e9+7;
long long mod_pow(long long base, long long exp, long long mod) {
long long res = 1;
while (exp) {
if (exp & 1) res = res * base % mod;
base = base * base % mod;
exp >>= 1;
}
return res;
}
int main() {
int n;
cin >> n;
if (n == 1) {
cout << "0\n0\n1\n";
} else if (n == 2) {
cout << "*0\n00\n3\n";
} else {
vector<long long> fact(2*n + 1, 1), inv_fact(2*n + 1, 1);
for (int i = 1; i <= 2*n; ++i) fact[i] = fact[i-1] * i % MOD;
inv_fact[2*n] = mod_pow(fact[2*n], MOD-2, MOD);
for (int i = 2*n; i >= 1; --i) inv_fact[i-1] = inv_fact[i] * i % MOD;
long long top_val = (fact[2*n-1] * inv_fact[n+1] % MOD * inv_fact[n-2] % MOD +
fact[2*n-3] * inv_fact[n-1] % MOD * inv_fact[n-2] % MOD) % MOD;
for (int i = 1; i <= n; ++i) cout << (i == n-1 ? '0' : '*');
cout << '\n';
for (int i = 1; i <= n; ++i) cout << (i == 1 ? '0' : '1');
cout << '\n' << top_val << '\n';
int t = (n + 1) / 2;
long long bottom_val = (t + 3) * t;
if (n & 1) bottom_val -= t + 1;
for (int i = 1; i <= n; ++i) cout << (i <= t ? '*' : '0');
cout << '\n';
for (int i = 1; i <= n; ++i) cout << '0';
cout << '\n' << bottom_val << '\n';
}
return 0;
}
This becomes tractable once you know the technique, which is quite elegant! Consider the diameter of a vertex set, which can be efficiently merged. The problem asks for the farthest pair with different colors, essentially the maximum distance between two different-colored sets. From properties of set diameters, the candidate distances are among the four endpoints of the diameters of the two sets. This information is also mergeable.
Since the information is not subtractive, maintain separate segment trees for each color to track the diameter of vertices of that color. Maintain another segment tree to handle the maximum distance between vertices of different colors. Complexity is O(n log n) with a large constant.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
struct TreeInfo {
int endpoint_a, endpoint_b;
ll max_dist;
TreeInfo(int v = 0) : endpoint_a(v), endpoint_b(v), max_dist(0) {}
TreeInfo(int a, int b, ll d) : endpoint_a(a), endpoint_b(b), max_dist(d) {}
friend TreeInfo combine(const TreeInfo &x, const TreeInfo &y) {
if (x.endpoint_a == 0) return y;
if (y.endpoint_a == 0) return x;
TreeInfo res = (x.max_dist > y.max_dist) ? x : y;
auto consider = [&](int a, int b) {
ll d = compute_distance(a, b);
if (d > res.max_dist) res = TreeInfo(a, b, d);
};
consider(x.endpoint_a, y.endpoint_a);
consider(x.endpoint_a, y.endpoint_b);
consider(x.endpoint_b, y.endpoint_a);
consider(x.endpoint_b, y.endpoint_b);
global_combine_max = max(global_combine_max, d); // Track cross-color max
return res;
}
private:
static ll global_combine_max;
static ll compute_distance(int u, int v); // Implementation depends on LCA preprocessing
};
ll TreeInfo::global_combine_max = 0;
class ColorSegmentTree {
vector<TreeInfo> tree;
int size;
void update(int idx, int node, int l, int r, int pos, int vertex_id, bool add) {
if (l == r) {
tree[node] = add ? TreeInfo(vertex_id) : TreeInfo();
return;
}
int mid = (l + r) / 2;
if (pos <= mid) update(idx, node*2, l, mid, pos, vertex_id, add);
else update(idx, node*2+1, mid+1, r, pos, vertex_id, add);
tree[node] = combine(tree[node*2], tree[node*2+1]);
}
public:
ColorSegmentTree(int sz) : size(sz), tree(4 * sz) {}
void insert(int color_id, int pos, int vertex_id) {
update(color_id, 1, 1, size, pos, vertex_id, true);
}
void remove(int color_id, int pos) {
update(color_id, 1, 1, size, pos, 0, false);
}
TreeInfo get_diameter(int color_id) { return tree[1]; }
};
// Main solution structure would involve LCA preprocessing and handling queries.