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](https://codeforces.net/contest/1903/problem/F)↵
↵
↵
Problem summary:↵
↵
↵
Given a set of edges connecting two nodes, we must take at least one node from each edge's end.↵
↵
Let the taken nodes to be $a_{1}, a_{2}, ..., a_{p}$ in sorted order. ↵
↵
**Maximize** $\min_{1 \leq i \leq p-1}(|a_{i}-a_{i+1}|)$. If $p=1$, the value would be $N$.↵
↵
Again, attempt the problem yourself before continue reading this blog.↵
↵
↵
↵
<spoiler summary="Prerequisites">Binary search, standard 2-SAT, segment tree</spoiler>↵
↵
↵
↵
<spoiler summary="If you don't know the second tag in the Prerequisites"> There are many blogs about 2-SAT (and Tarjan). Read the next paragraph if you are like me and don't get how to build the graph. You can search up the internet for it. ↵
↵
A good blog in Chinese: [link](https://www.mina.moe/archives/11387). I read like 4-5 blogs and websites to learn about it but still don't get how the graph is built. The blog provides an excellent description, "A directed edge from A to B means that if we choose A then we **must** choose B, but when we choose B, we **don't necessary** choose A." </spoiler>↵
↵
<spoiler summary= "first observation"> 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 [user:Um_nik,2023-12-13] first XD. </spoiler>↵
↵
<spoiler summary= "second observation">↵
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>↵
↵
<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.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "optimization">↵
We notice that the bottleneck of this solution would be on the $2nd$ case. What should we do to optimize it? What if we took ranges to represent them into nodes? Then, what is the trick to make as few ranges we can? Then we can notice that we can use **ranges in segment tree** to represent a **node**! ↵
↵
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.↵
</spoiler>↵
↵
[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<int> s;↵
int dfn[NN], low[NN], timer, cnt, col[NN];↵
bool vis[NN];↵
vector<int> G[NN];↵
vector<int> 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();↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
↵
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.↵
</spoiler>↵
↵
Tips for implementation: ↵
↵
<spoiler summary ="Tips">↵
We can represent $i'$ as node with index $i + N$, also $tr_{L,R}$ with index $p$ in the segment tree with node with index $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).↵
</spoiler>↵
↵
Thank you so much for reading until here. Hope you guys learnt something from this blog.
↵
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](https://codeforces.net/contest/1903/problem/F)↵
↵
↵
Problem summary:↵
↵
↵
Given a set of edges connecting two nodes, we must take at least one node from each edge's end.↵
↵
Let the taken nodes to be $a_{1}, a_{2}, ..., a_{p}$ in sorted order. ↵
↵
**Maximize** $\min_{1 \leq i \leq p-1}(|a_{i}-a_{i+1}|)$. If $p=1$, the value would be $N$.↵
↵
Again, attempt the problem yourself before continue reading this blog.↵
↵
↵
↵
<spoiler summary="Prerequisites">Binary search, standard 2-SAT, segment tree</spoiler>↵
↵
↵
↵
<spoiler summary="If you don't know the second tag in the Prerequisites"> There are many blogs about 2-SAT (and Tarjan). Read the next paragraph if you are like me and don't get how to build the graph. You can search up the internet for it. ↵
↵
A good blog in Chinese: [link](https://www.mina.moe/archives/11387). I read like 4-5 blogs and websites to learn about it but still don't get how the graph is built. The blog provides an excellent description, "A directed edge from A to B means that if we choose A then we **must** choose B, but when we choose B, we **don't necessary** choose A." </spoiler>↵
↵
<spoiler summary= "first observation"> 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 [user:Um_nik,2023-12-13] first XD. </spoiler>↵
↵
<spoiler summary= "second observation">↵
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>↵
↵
<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.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "optimization">↵
We notice that the bottleneck of this solution would be on the $2nd$ case. What should we do to optimize it? What if we took ranges to represent them into nodes? Then, what is the trick to make as few ranges we can? Then we can notice that we can use **ranges in segment tree** to represent a **node**! ↵
↵
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.↵
</spoiler>↵
↵
[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<int> s;↵
int dfn[NN], low[NN], timer, cnt, col[NN];↵
bool vis[NN];↵
vector<int> G[NN];↵
vector<int> 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();↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
↵
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.↵
</spoiler>↵
↵
Tips for implementation: ↵
↵
<spoiler summary ="Tips">↵
We can represent $i'$ as node with index $i + N$, also $tr_{L,R}$ with index $p$ in the segment tree with node with index $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).↵
</spoiler>↵
↵
Thank you so much for reading until here. Hope you guys learnt something from this blog.
