L - スケジュール調整 / Schedule Adjustment Editorial by admin
gpt-5.3-codexOverview
Each presenter chooses a start time from 2 options, so the overall problem is a “binary selection” problem.
We reduce “can we make the start time difference at least \(K\) for every pair?” to a decision problem, and use 2-SAT + binary search to find the maximum \(K\), then construct the lexicographically smallest string that satisfies that \(K\).
Analysis
What we want to maximize in this problem is: - The absolute difference of start times for each specified pair \((U_j, V_j)\) - The minimum value \(f(S)\) of these differences
In other words, we want to make the “minimum difference” as large as possible, so we can typically use the following approach:
- “Does there exist an \(S\) satisfying \(f(S) \ge K\)?” as a decision problem
- If feasible, increase \(K\); if not, decrease \(K\)
This works because of monotonicity (binary search is applicable).
1. Transforming into a Decision Problem
Let the choice of presenter \(i\) be a variable \(x_i \in \{0,1\}\).
- \(x_i=0\) : time \(A_i\)
- \(x_i=1\) : time \(A_i + D_i\)
For a fixed \(K\), we examine all 4 combinations \((x_u, x_v)\) for each pair \((u,v)\).
If for some combination
[
|t_u - t_v| < K
]
then that combination is “forbidden”.
“Forbid \((x_u=su)\) and \((x_v=sv)\)” can be expressed as a logical formula:
[
\neg(x_u=su \land x_v=sv)
\equiv (x_u\ne su)\ \lor\ (x_v\ne sv)
]
This is one clause of a 2-CNF.
Collecting all forbidden conditions gives us a 2-SAT instance, which can be checked for satisfiability in linear time.
2. Why a Naive Solution is Infeasible
Brute force requires \(2^N\) possibilities, which is impossible for \(N \le 2000\).
Also, trying \(K\) from 0 upward is impractical since the range is on the order of \(10^9\).
Therefore, we combine:
- Decision: 2-SAT (polynomial time)
- Optimization: Binary search (\(\log\) iterations)
to achieve an efficient solution.
3. Constructing the Lexicographically Smallest \(S\)
After finding the maximum \(K\), we determine characters from left to right.
- First, tentatively set \(S_i=0\) and check “is it solvable with this prefix fixed?” using 2-SAT again
- If solvable, fix it as 0 (we want the lexicographically smallest)
- If not, set it to 1
Repeating this for \(i=1..N\) yields the lexicographically smallest string satisfying \(f(S)=K\).
(The greedy approach of always choosing 0 when possible is correct)
Algorithm
- Read input.
- If \(M=0\), there are no constraints, so output \(K=0\), \(S=00\cdots0\).
- Define
feasible(K, prefix):- Create a 2-SAT instance.
- If a prefix (first few characters fixed) is given, add unit clauses.
- For each edge \((u,v)\) and each \((su,sv)\in\{0,1\}^2\):
if \(|t_u(su)-t_v(sv)|<K\), add a forbidden clause. - Return true if the 2-SAT is satisfiable.
- Maximize \(K\) using binary search.
- For the obtained \(K\), determine each digit by checking feasibility with
0preferred, constructing the lexicographically smallest string.
- Output \(K\) and \(S\).
Complexity
- For one call to
feasible:
- Number of variables: \(N\), number of clauses: at most 4 per edge, so \(O(M)\)
- 2-SAT decision is \(O(N+M)\)
- Number of variables: \(N\), number of clauses: at most 4 per edge, so \(O(M)\)
- Binary search takes about \(\log_2(2\times10^9)\approx 31\) iterations
- Lexicographic construction requires \(N\) additional decision calls
Overall:
- Time complexity: \(O((\log V + N)\,(N+M))\) (where \(V\approx 2\times10^9\))
Effectively closer to \(O(N(N+M))\) (the \(N\) decision calls dominate)
- Space complexity: \(O(N+M)\) (2-SAT graph)
Implementation Notes
When converting “forbidden combinations” to clauses, correctly add: [ (x_u\ne su)\lor(x_v\ne sv) ] (In code, this is
add_or(u, su^1, v, sv^1)).Use
long longfor absolute value comparisons (times can be up to approximately \(2\times10^9\)).For lexicographic minimization, the order of “try 0 at each position and adopt if feasible” is important.
Handling
M=0as a special case avoids unnecessary decision calls and is safer.Source Code
#include <bits/stdc++.h>
using namespace std;
struct TwoSAT {
int n;
vector<vector<int>> g, rg;
vector<int> comp, order, used, assignment;
TwoSAT(int n = 0) { init(n); }
void init(int n_) {
n = n_;
g.assign(2 * n, {});
rg.assign(2 * n, {});
}
// var i, value v (false=0, true=1) -> node id
int id(int i, bool v) const { return 2 * i + (v ? 1 : 0); }
void add_imp(int a, int b) {
g[a].push_back(b);
rg[b].push_back(a);
}
void add_or(int i, bool vi, int j, bool vj) {
// (x_i==vi) OR (x_j==vj)
int a = id(i, vi), na = id(i, !vi);
int b = id(j, vj), nb = id(j, !vj);
add_imp(na, b);
add_imp(nb, a);
}
void add_unit(int i, bool vi) {
// (x_i == vi)
add_imp(id(i, !vi), id(i, vi));
}
bool satisfiable() {
int V = 2 * n;
used.assign(V, 0);
order.clear();
order.reserve(V);
for (int s = 0; s < V; s++) if (!used[s]) {
// iterative DFS for postorder
vector<pair<int,int>> st;
st.push_back({s, 0});
used[s] = 1;
while (!st.empty()) {
int v = st.back().first;
int &it = st.back().second;
if (it < (int)g[v].size()) {
int to = g[v][it++];
if (!used[to]) {
used[to] = 1;
st.push_back({to, 0});
}
} else {
order.push_back(v);
st.pop_back();
}
}
}
comp.assign(V, -1);
int cid = 0;
for (int idx = V - 1; idx >= 0; --idx) {
int s = order[idx];
if (comp[s] != -1) continue;
queue<int> q;
q.push(s);
comp[s] = cid;
while (!q.empty()) {
int v = q.front(); q.pop();
for (int to : rg[v]) {
if (comp[to] == -1) {
comp[to] = cid;
q.push(to);
}
}
}
cid++;
}
assignment.assign(n, 0);
for (int i = 0; i < n; i++) {
if (comp[id(i,0)] == comp[id(i,1)]) return false;
assignment[i] = (comp[id(i,1)] > comp[id(i,0)]) ? 1 : 0;
}
return true;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<long long> A(N), D(N);
for (int i = 0; i < N; i++) cin >> A[i] >> D[i];
vector<pair<int,int>> edges;
edges.reserve(M);
for (int j = 0; j < M; j++) {
int u, v;
cin >> u >> v;
--u; --v;
edges.push_back({u, v});
}
if (M == 0) {
cout << 0 << "\n";
cout << string(N, '0') << "\n";
return 0;
}
auto feasible = [&](long long K, const vector<int>* fixedPrefix = nullptr, int prefLen = 0) -> bool {
TwoSAT sat(N);
if (fixedPrefix) {
for (int i = 0; i < prefLen; i++) {
sat.add_unit(i, (*fixedPrefix)[i] == 1);
}
}
for (auto [u, v] : edges) {
long long tu[2] = {A[u], A[u] + D[u]};
long long tv[2] = {A[v], A[v] + D[v]};
for (int su = 0; su < 2; su++) {
for (int sv = 0; sv < 2; sv++) {
if (llabs(tu[su] - tv[sv]) < K) {
// forbid (u=su and v=sv): (!u=su) OR (!v=sv)
sat.add_or(u, su ^ 1, v, sv ^ 1);
}
}
}
}
return sat.satisfiable();
};
long long lo = 0, hi = 2000000001LL; // [lo, hi)
while (hi - lo > 1) {
long long mid = (lo + hi) >> 1;
if (feasible(mid)) lo = mid;
else hi = mid;
}
long long K = lo;
vector<int> pref(N, 0);
for (int i = 0; i < N; i++) {
pref[i] = 0;
if (!feasible(K, &pref, i + 1)) {
pref[i] = 1;
}
}
string S;
S.reserve(N);
for (int i = 0; i < N; i++) S.push_back(char('0' + pref[i]));
cout << K << "\n" << S << "\n";
return 0;
}
This editorial was generated by gpt-5.3-codex.
posted:
last update: