Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Do a unimodular column transform: replace each interval row by its endpoint difference. The row becomes the edge vector , with vertex treated as the deleted root column.
After that transform, you are looking at directed edges on vertices. The determinant is unless those edges form a spanning tree; if they do form a tree, the determinant is . So the scary maximum is just .
Think in terms of saved cost. Rows you do not modify must be extendable to a positive tree. If you keep at most rows, the kept edges only need to be a forest: complete it to a tree, and if the sign is wrong, swap two newly chosen rows to flip it.
The only annoying cases are keeping or rows. For a tree, root it at vertex . If row corresponds to the edge whose child is , then the determinant sign is the parity of the permutation , plus one flip for every child with .
For one changed row, delete that row. The remaining forest has two components. The cofactor vector is constant on the component not containing and zero on the root component, so a replacement edge can give either or depending on which side has the smaller endpoint.
The word maximize is mostly bait here. The determinant of an interval matrix cannot get large at all.
Let be the upper-triangular prefix matrix where row has ones from to . Then the interval row equals
where means the zero vector because column is deleted. Since , determinants do not change if we replace every interval row by .
Now each row is the reduced incidence vector of an edge in a graph on vertices , directed from the smaller endpoint to the larger endpoint. A reduced incidence matrix with edges on vertices has determinant:
So . There is no hidden giant determinant. It is tree orientation bookkeeping, which is somehow worse, but at least honest.
We want minimum changed cost, so equivalently we want maximum saved cost among rows left unchanged. If a set of unchanged rows is used in the final tree, its edges must be acyclic. Thus unchanged rows must form a forest.
First handle the easy big bucket: keeping at most rows. If the kept rows form a forest, complete that forest to any spanning tree using the free row positions. There are at least two newly chosen rows. If the determinant sign is already , done. If it is , swap the intervals assigned to two newly chosen rows. The graph is still the same tree, but swapping two matrix rows flips the determinant. Therefore every forest of size at most is feasible.
The best saved cost in this bucket is exactly a maximum-weight forest with at most edges. This is the graphic matroid greedy algorithm: sort rows by decreasing , add an edge if it connects two DSU components, and stop after accepted edges.
Now only two special cases remain.
Keeping all rows means the original graph must be a tree and its determinant sign must already be positive.
To compute the sign of a tree, root it at vertex . Every edge belongs to exactly one non-root vertex: its child . Suppose row order gives child sequence . If we reorder rows by child label, row has diagonal entry when and when . The remaining parent-column terms form a nilpotent parent matrix, so they do not change the determinant. Therefore
where is the number of vertices with . This gives the full determinant sign in linear time after rooting, plus permutation parity.
Keeping exactly rows means one row is changed. Delete that row. The remaining edges must be a forest with exactly two components. Let be the component not containing the root vertex , and let the cofactor constant on be . The cofactor vector is on and on the root component, because every kept edge forces equal cofactor values inside its component.
For a replacement edge from smaller endpoint to larger endpoint :
Since vertex is in the root component and is larger than everything else, if we can always choose an edge from to . If , we need some root-side vertex smaller than some vertex of .
For an original tree, deleting edge makes the subtree of that edge's child. If the original determinant sign is , and the child-side entry of edge has sign where for and otherwise, then . We also need the maximum label in the subtree and the minimum label outside it to test whether the direction is available.
If the original graph is not connected, one changed row can only work in one situation: the graph has exactly two connected components and exactly one cycle total. Then deleting a cycle edge leaves a two-component forest. Cycle edges are found by peeling leaves. Compute for one cycle edge by replacing it with an artificial edge from the non-root component to vertex and using the tree sign formula. For the other cycle edges, the cofactor signs follow the unique cycle dependency: traverse the cycle; an edge gets the same sign if traversal matches its increasing orientation, and the opposite sign otherwise.
The final answer is the minimum among:
The complexity is per total input size because of sorting for the greedy forest, and everything else is linear. Memory is .
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct DSU {
vector<int> p, sz;
int comps = 0;
void init(int n) {
p.resize(n + 1);
sz.assign(n + 1, 1);
iota(p.begin(), p.end(), 0);
comps = n;
}
int find(int x) {
while (p[x] != x) {
p[x] = p[p[x]];
x = p[x];
}
return x;
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
comps--;
return true;
}
};
int permutationParity(const vector<int>& p) {
int n = (int)p.size();
vector<char> seen(n + 1, 0);
int cycles = 0;
for (int i = 1; i <= n; i++) {
if (seen[i]) continue;
cycles++;
int x = i;
while (!seen[x]) {
seen[x] = 1;
x = p[x - 1];
}
}
return (n - cycles) & 1;
}
struct Solver {
int n = 0, V = 0, ptr = 0;
vector<int> u, v;
vector<ll> cost;
vector<int> head, to, eid, nxt, deg0;
void init(int n_) {
n = n_;
V = n + 1;
ptr = 0;
u.assign(n, 0);
v.assign(n, 0);
cost.assign(n, 0);
head.assign(V + 1, -1);
to.assign(2 * n, 0);
eid.assign(2 * n, 0);
nxt.assign(2 * n, -1);
deg0.assign(V + 1, 0);
}
void addDir(int x, int y, int id) {
to[ptr] = y;
eid[ptr] = id;
nxt[ptr] = head[x];
head[x] = ptr++;
deg0[x]++;
}
void addEdge(int x, int y, int id) {
addDir(x, y, id);
addDir(y, x, id);
}
ll cappedForestSave() {
int cap = n - 2;
if (cap <= 0) return 0;
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return cost[i] > cost[j];
});
DSU d;
d.init(V);
ll saved = 0;
int taken = 0;
for (int id : ord) {
if (taken == cap) break;
if (d.unite(u[id], v[id])) {
saved += cost[id];
taken++;
}
}
return saved;
}
int treeSignOnly(int skip, int artId, int artU) {
vector<int> parent(V + 1, 0), child(n, 0), st;
st.reserve(V);
parent[V] = -1;
st.push_back(V);
int down = 0;
while (!st.empty()) {
int x = st.back();
st.pop_back();
if (x == V && artId != -1 && parent[artU] == 0) {
parent[artU] = x;
child[artId] = artU;
st.push_back(artU);
}
for (int e = head[x]; e != -1; e = nxt[e]) {
int id = eid[e];
if (id == skip) continue;
int y = to[e];
if (parent[y] != 0) continue;
parent[y] = x;
child[id] = y;
if (x < y) down ^= 1;
st.push_back(y);
}
}
return permutationParity(child) ^ down;
}
struct TreeData {
int signNeg = 0;
vector<int> parent, child, tin, tout, subMax, pref, suff;
};
TreeData buildTreeData() {
TreeData data;
data.parent.assign(V + 1, 0);
data.child.assign(n, 0);
data.tin.assign(V + 1, 0);
data.tout.assign(V + 1, 0);
data.subMax.assign(V + 1, 0);
vector<int> order;
order.reserve(V);
vector<pair<int, int>> st;
st.reserve(2 * V);
data.parent[V] = -1;
st.push_back({V, 0});
int down = 0;
while (!st.empty()) {
auto [x, state] = st.back();
st.pop_back();
if (state == 0) {
data.tin[x] = (int)order.size();
order.push_back(x);
data.subMax[x] = x;
st.push_back({x, 1});
for (int e = head[x]; e != -1; e = nxt[e]) {
int y = to[e];
if (data.parent[y] != 0) continue;
int id = eid[e];
data.parent[y] = x;
data.child[id] = y;
if (x < y) down ^= 1;
st.push_back({y, 0});
}
} else {
data.tout[x] = (int)order.size() - 1;
if (data.parent[x] > 0) {
data.subMax[data.parent[x]] = max(data.subMax[data.parent[x]], data.subMax[x]);
}
}
}
const int INF = 1000000000;
data.pref.assign(V + 1, INF);
for (int i = 0; i < V; i++) {
data.pref[i + 1] = min(data.pref[i], order[i]);
}
data.suff.assign(V + 1, INF);
for (int i = V - 1; i >= 0; i--) {
data.suff[i] = min(data.suff[i + 1], order[i]);
}
data.signNeg = permutationParity(data.child) ^ down;
return data;
}
ll solveCase() {
if (n == 1) return 0;
ll total = 0;
for (ll x : cost) total += x;
ll ans = total - cappedForestSave();
DSU d;
d.init(V);
for (int i = 0; i < n; i++) d.unite(u[i], v[i]);
if (d.comps == 1) {
TreeData tr = buildTreeData();
if (tr.signNeg == 0) ans = 0;
for (int id = 0; id < n; id++) {
int c = tr.child[id];
int p = tr.parent[c];
int cNeg = tr.signNeg ^ (p < c);
int outsideMin = min(tr.pref[tr.tin[c]], tr.suff[tr.tout[c] + 1]);
if (cNeg == 0 || outsideMin < tr.subMax[c]) {
ans = min(ans, cost[id]);
}
}
} else if (d.comps == 2) {
int rootComp = d.find(V);
int rootMin = INT_MAX, otherMax = -1, x0 = -1;
for (int x = 1; x <= V; x++) {
if (d.find(x) == rootComp) {
rootMin = min(rootMin, x);
} else {
otherMax = max(otherMax, x);
x0 = x;
}
}
vector<int> deg = deg0;
vector<char> removed(V + 1, 0);
deque<int> q;
for (int x = 1; x <= V; x++) {
if (deg[x] <= 1) q.push_back(x);
}
while (!q.empty()) {
int x = q.front();
q.pop_front();
if (removed[x]) continue;
removed[x] = 1;
for (int e = head[x]; e != -1; e = nxt[e]) {
int y = to[e];
if (removed[y]) continue;
deg[y]--;
if (deg[y] == 1) q.push_back(y);
}
}
vector<int> cycleEdges;
for (int id = 0; id < n; id++) {
if (!removed[u[id]] && !removed[v[id]]) {
cycleEdges.push_back(id);
}
}
if (!cycleEdges.empty()) {
int j0 = cycleEdges[0];
int c0Neg = treeSignOnly(j0, j0, x0);
vector<int> cdeg(V + 1, 0), cto1(V + 1, -1), cto2(V + 1, -1);
vector<int> cid1(V + 1, -1), cid2(V + 1, -1);
auto addCycle = [&](int x, int y, int id) {
if (cdeg[x] == 0) {
cto1[x] = y;
cid1[x] = id;
} else {
cto2[x] = y;
cid2[x] = id;
}
cdeg[x]++;
};
for (int id : cycleEdges) {
addCycle(u[id], v[id], id);
addCycle(v[id], u[id], id);
}
vector<char> lambdaNeg(n, 0);
int start = u[j0];
int cur = v[j0];
int prev = j0;
while (cur != start) {
int nextId, nextVertex;
if (cid1[cur] != prev) {
nextId = cid1[cur];
nextVertex = cto1[cur];
} else {
nextId = cid2[cur];
nextVertex = cto2[cur];
}
lambdaNeg[nextId] = (cur > nextVertex);
prev = nextId;
cur = nextVertex;
}
bool canUseNegativeCofactor = rootMin < otherMax;
for (int id : cycleEdges) {
int cNeg = c0Neg ^ lambdaNeg[id];
if (cNeg == 0 || canUseNegativeCofactor) {
ans = min(ans, cost[id]);
}
}
}
}
return ans;
}
};
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
Solver sol;
sol.init(n);
for (int i = 0; i < n; i++) {
int l, r;
ll a;
cin >> l >> r >> a;
sol.u[i] = l;
sol.v[i] = r + 1;
sol.cost[i] = a;
sol.addEdge(sol.u[i], sol.v[i], i);
}
cout << sol.solveCase() << char(10);
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct DSU {
vector<int> p, sz;
int comps = 0;
void init(int n) {
p.resize(n + 1);
sz.assign(n + 1, 1);
iota(p.begin(), p.end(), 0);
comps = n;
}
int find(int x) {
while (p[x] != x) {
p[x] = p[p[x]];
x = p[x];
}
return x;
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
comps--;
return true;
}
};
int permutationParity(const vector<int>& p) {
int n = (int)p.size();
vector<char> seen(n + 1, 0);
int cycles = 0;
for (int i = 1; i <= n; i++) {
if (seen[i]) continue;
cycles++;
int x = i;
while (!seen[x]) {
seen[x] = 1;
x = p[x - 1];
}
}
return (n - cycles) & 1;
}
struct Solver {
int n = 0, V = 0, ptr = 0;
vector<int> u, v;
vector<ll> cost;
vector<int> head, to, eid, nxt, deg0;
void init(int n_) {
n = n_;
V = n + 1;
ptr = 0;
u.assign(n, 0);
v.assign(n, 0);
cost.assign(n, 0);
head.assign(V + 1, -1);
to.assign(2 * n, 0);
eid.assign(2 * n, 0);
nxt.assign(2 * n, -1);
deg0.assign(V + 1, 0);
}
void addDir(int x, int y, int id) {
to[ptr] = y;
eid[ptr] = id;
nxt[ptr] = head[x];
head[x] = ptr++;
deg0[x]++;
}
void addEdge(int x, int y, int id) {
addDir(x, y, id);
addDir(y, x, id);
}
ll cappedForestSave() {
int cap = n - 2;
if (cap <= 0) return 0;
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return cost[i] > cost[j];
});
DSU d;
d.init(V);
ll saved = 0;
int taken = 0;
for (int id : ord) {
if (taken == cap) break;
if (d.unite(u[id], v[id])) {
saved += cost[id];
taken++;
}
}
return saved;
}
int treeSignOnly(int skip, int artId, int artU) {
vector<int> parent(V + 1, 0), child(n, 0), st;
st.reserve(V);
parent[V] = -1;
st.push_back(V);
int down = 0;
while (!st.empty()) {
int x = st.back();
st.pop_back();
if (x == V && artId != -1 && parent[artU] == 0) {
parent[artU] = x;
child[artId] = artU;
st.push_back(artU);
}
for (int e = head[x]; e != -1; e = nxt[e]) {
int id = eid[e];
if (id == skip) continue;
int y = to[e];
if (parent[y] != 0) continue;
parent[y] = x;
child[id] = y;
if (x < y) down ^= 1;
st.push_back(y);
}
}
return permutationParity(child) ^ down;
}
struct TreeData {
int signNeg = 0;
vector<int> parent, child, tin, tout, subMax, pref, suff;
};
TreeData buildTreeData() {
TreeData data;
data.parent.assign(V + 1, 0);
data.child.assign(n, 0);
data.tin.assign(V + 1, 0);
data.tout.assign(V + 1, 0);
data.subMax.assign(V + 1, 0);
vector<int> order;
order.reserve(V);
vector<pair<int, int>> st;
st.reserve(2 * V);
data.parent[V] = -1;
st.push_back({V, 0});
int down = 0;
while (!st.empty()) {
auto [x, state] = st.back();
st.pop_back();
if (state == 0) {
data.tin[x] = (int)order.size();
order.push_back(x);
data.subMax[x] = x;
st.push_back({x, 1});
for (int e = head[x]; e != -1; e = nxt[e]) {
int y = to[e];
if (data.parent[y] != 0) continue;
int id = eid[e];
data.parent[y] = x;
data.child[id] = y;
if (x < y) down ^= 1;
st.push_back({y, 0});
}
} else {
data.tout[x] = (int)order.size() - 1;
if (data.parent[x] > 0) {
data.subMax[data.parent[x]] = max(data.subMax[data.parent[x]], data.subMax[x]);
}
}
}
const int INF = 1000000000;
data.pref.assign(V + 1, INF);
for (int i = 0; i < V; i++) {
data.pref[i + 1] = min(data.pref[i], order[i]);
}
data.suff.assign(V + 1, INF);
for (int i = V - 1; i >= 0; i--) {
data.suff[i] = min(data.suff[i + 1], order[i]);
}
data.signNeg = permutationParity(data.child) ^ down;
return data;
}
ll solveCase() {
if (n == 1) return 0;
ll total = 0;
for (ll x : cost) total += x;
ll ans = total - cappedForestSave();
DSU d;
d.init(V);
for (int i = 0; i < n; i++) d.unite(u[i], v[i]);
if (d.comps == 1) {
TreeData tr = buildTreeData();
if (tr.signNeg == 0) ans = 0;
for (int id = 0; id < n; id++) {
int c = tr.child[id];
int p = tr.parent[c];
int cNeg = tr.signNeg ^ (p < c);
int outsideMin = min(tr.pref[tr.tin[c]], tr.suff[tr.tout[c] + 1]);
if (cNeg == 0 || outsideMin < tr.subMax[c]) {
ans = min(ans, cost[id]);
}
}
} else if (d.comps == 2) {
int rootComp = d.find(V);
int rootMin = INT_MAX, otherMax = -1, x0 = -1;
for (int x = 1; x <= V; x++) {
if (d.find(x) == rootComp) {
rootMin = min(rootMin, x);
} else {
otherMax = max(otherMax, x);
x0 = x;
}
}
vector<int> deg = deg0;
vector<char> removed(V + 1, 0);
deque<int> q;
for (int x = 1; x <= V; x++) {
if (deg[x] <= 1) q.push_back(x);
}
while (!q.empty()) {
int x = q.front();
q.pop_front();
if (removed[x]) continue;
removed[x] = 1;
for (int e = head[x]; e != -1; e = nxt[e]) {
int y = to[e];
if (removed[y]) continue;
deg[y]--;
if (deg[y] == 1) q.push_back(y);
}
}
vector<int> cycleEdges;
for (int id = 0; id < n; id++) {
if (!removed[u[id]] && !removed[v[id]]) {
cycleEdges.push_back(id);
}
}
if (!cycleEdges.empty()) {
int j0 = cycleEdges[0];
int c0Neg = treeSignOnly(j0, j0, x0);
vector<int> cdeg(V + 1, 0), cto1(V + 1, -1), cto2(V + 1, -1);
vector<int> cid1(V + 1, -1), cid2(V + 1, -1);
auto addCycle = [&](int x, int y, int id) {
if (cdeg[x] == 0) {
cto1[x] = y;
cid1[x] = id;
} else {
cto2[x] = y;
cid2[x] = id;
}
cdeg[x]++;
};
for (int id : cycleEdges) {
addCycle(u[id], v[id], id);
addCycle(v[id], u[id], id);
}
vector<char> lambdaNeg(n, 0);
int start = u[j0];
int cur = v[j0];
int prev = j0;
while (cur != start) {
int nextId, nextVertex;
if (cid1[cur] != prev) {
nextId = cid1[cur];
nextVertex = cto1[cur];
} else {
nextId = cid2[cur];
nextVertex = cto2[cur];
}
lambdaNeg[nextId] = (cur > nextVertex);
prev = nextId;
cur = nextVertex;
}
bool canUseNegativeCofactor = rootMin < otherMax;
for (int id : cycleEdges) {
int cNeg = c0Neg ^ lambdaNeg[id];
if (cNeg == 0 || canUseNegativeCofactor) {
ans = min(ans, cost[id]);
}
}
}
}
return ans;
}
};
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
Solver sol;
sol.init(n);
for (int i = 0; i < n; i++) {
int l, r;
ll a;
cin >> l >> r >> a;
sol.u[i] = l;
sol.v[i] = r + 1;
sol.cost[i] = a;
sol.addEdge(sol.u[i], sol.v[i], i);
}
cout << sol.solveCase() << char(10);
}
}