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!
Prerequisites for this problem: Binary search, standard 2-SAT, segment tree
Wow, this problem took me around 4 hours. Thinking about the solution took me 1 hour and coding it out took 1.5 hour. You wonder where is the other 1.5 hour? Well, I knew 2-SAT was a thing but I didn't really know the concept behind it (I only knew it works in a choosing "this" and cannot choose "that" scenario from CPH).
A good blog in Chinese: link. 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."
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:
$$$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$$$.
$$$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.
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.
(AC code)[]
Comment on this problem and my 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:
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).
