This is my personal note and might be some kind of user editorial/learning material for some people. This is the second episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), which are completely solved by myself without looking at the editorial, that are both interesting and educational. If you want to motivate me to write a continuation (aka note 3), a significant upvote from you would be well appreciated!

Problem link

Lets get back to the problem. A wise man once said: "When you see a problem that maximize minimum ... or minimize maximum ... , it's $$$99.999\%$$$ binary search."

By observation this problem has a : $$$true, ..., true, false, ..., false$$$ scenario. I think this is quite easy to find out this pattern. If you can't see this pattern, try learning binary search problems from Um_nik first XD.

Now we need to write a check function to check if the graph satisfies a value $$$k$$$ to have $$$min$$$ $$$\geq$$$ $$$k?$$$

From here onwards we will let $$$A$$$ $$$=$$$ we choose node $$$A$$$, $$$A'$$$ $$$=$$$ we don't choose A.

Then, we can observe that we have 2 cases:

<spoiler summary:" Case 1"> $$$1st$$$ case : each edge must have one end chosen.

To solve this we build an edge from $$$u'$$$ -> $$$v$$$ for each $$$u$$$ and all $$$v \in neighbours(u)$$$. When we choose to not take $$$u$$$, we must take $$$v$$$.

<spoiler summary:" Case 2"> $$$2nd$$$ case (harder) : $$$min \geq k$$$

If we took some node $$$i$$$, then we cannot take $$$\forall j \in [i-k+1,i+k-1]\backslash{i}$$$. This is because if we took any $$$j$$$ in that range, $$$abs(i-j)<k$$$ so $$$min\geq k$$$ will not be satisfied.

Hence we need to build an edge from $$$i$$$ -> $$$j'$$$ for $$$\forall j \in [i-k+1,i+k-1]\backslash{i}$$$. Then we just run a standard 2-SAT program with tarjan to make sure $$$\forall i \in [1,N], i$$$ and $$$i'$$$ don't belong to the same strongly connected component (or called $$$SCC$$$).

This reduces the problem to $$$O(N^2logN)$$$. Not good enough to pass this task. Try to optimize it yourself before looking at the optimizations done.

Ok, let us define $$$tr_{L,R}$$$ to be the node that represents range $$$[L,R]$$$.

Let us redo $$$2nd$$$ case. We need to build an edge from $$$i$$$ -> $$$tr_{i-k+1,i-1}'$$$ and $$$i$$$ -> $$$tr_{i+1,i+k-1}'$$$. We also need to add edges from $$$tr_{L,R}$$$, $$$tr_{L,R}'$$$ -> $$$tr_{L, mid}'$$$ and $$$tr_{L,R}'$$$ -> $$$tr_{mid+1, R}'$$$. This is because if we don't want to take $$$[L,R]$$$, we also must not take $$$[L, mid]$$$ and $$$[mid+1, R]$$$. If we want to take $$$tr'_{i, i}$$$, we must also satisfy $$$i'$$$, meaning we also need to add edge from every $$$tr'_{i, i}$$$ to $$$i'$$$.

After we did this, just run tarjan and compute all SCCs. If an $$$i$$$ and $$$i'$$$ belongs to the same SCC, answer will be NO because how can you take $$$i$$$ and not take $$$i$$$ at the same time?

Otherwise, the answer is YES.

(AC code)[https://codeforces.net/contest/1903/submission/236990689] <spoiler summary:"Code"> ```cpp //闲敲棋子落灯花//

include <bits/stdc++.h>

using namespace std; using i64 = long long;

const int NN = 6e5 + 500; stack s; int dfn[NN], low[NN], timer, cnt, col[NN]; bool vis[NN]; vector G[NN]; vector Neo[NN]; void tarjan(int u) { vis[u] = true; low[u] = dfn[u] = ++timer; s.push(u); for (auto v : Neo[u]) { if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (vis[v]) { low[u] = min(low[u], dfn[v]); } } if (low[u] == dfn[u]) { cnt++; while (1) { int x = s.top(); s.pop(); vis[x] = false; col[x] = cnt; if (x == u) break; } } }

int N, M; void add_edge(int x, int y) { Neo[x].push_back(y); return; } void build(int p, int l, int r) { if (l == r) { add_edge(p + 2 * N, l + N); return; } int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); add_edge(p + 2 * N, (p << 1) + 2 * N); add_edge(p + 2 * N, (p << 1 | 1) + 2 * N); return; } void add(int p, int l, int r, int ql, int qr, int x) { if (ql <= l && r <= qr) { add_edge(x, p + 2 * N); return; } int mid = (l + r) >> 1; if (ql <= mid) add(p << 1, l, mid, ql, qr, x); if (qr >= mid + 1) add(p << 1 | 1, mid + 1, r, ql, qr, x); return; } bool check(int k) { if (k == 1) return true; for (int i = 0; i <= 2 * N; i++) Neo[i].clear(); for (int i = 1; i <= N; i++) for (auto& v : G[i]) add_edge(i + N, v);

for (int i = 1; i <= N; i++) {
    int L = max(1, i - k + 1), R = i - 1;
    if (L <= R) add(1, 1, N, L, R, i);
    L = i + 1; R = min(N, i + k - 1);
    if (L <= R) add(1, 1, N, L, R, i);
}
while (s.size()) s.pop();
timer = 0, cnt = 0;
for (int i = 1; i <= 6 * N; i++)
    low[i] = dfn[i] = vis[i] = 0;

for (int i = 1; i <= 6 * N; i++)
    if (!dfn[i])
        tarjan(i);

for (int i = 1; i <= N; i++)
    if (col[i] == col[i + N])
        return false;
return true;

} void solve() { cin >> N >> M; for (int i = 0; i <= 6 * N; i++) { G[i].clear(); Neo[i].clear(); } for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } build(1, 1, N); int l = 1, r = N; while (l < r) { int mid = (l + r + 1) >> 1; if (check(mid)) l = mid; else r = mid — 1; } cout << l << '\n'; return; }

int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

int T; cin >> T;
while (T--) {
    solve();
}

} ```

Comment on this problem and my feelings:

<spoiler summary:"Feelings"> This is the first time I saw a 2-SAT problem. Bruh I literally spent 1.5 hours to just read on 2-SAT. But the problem is amazing and interesting. Mixture of ideas (2-SAT, binary search and segment tree) was insane. Also, I submitted like 7 times like a dumbass before ACing.

Tips for implementation:

<spoiler summary:"Tips"> We can represent $$$i'$$$ as node with id $$$i + N$$$, also $$$tr_{L,R}$$$ with index $$$p$$$ in the segment tree with node with id $$$p+2*N$$$ for simpler implementation. Remember to clear all edges and the edges created from the previous check function (got like 4 WAs for this).