PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Yogesh Kumar
Tester & Editorialist: Taranpreet Singh
DIFFICULTY
Medium
PREREQUISITES
Two-satisfiability, sliding window and Union Disjoint Sets.
PROBLEM
Given K lasers placed in distinct positions in coordinate plane, each laser can cover 2*D+1 points with its own position as center where D is given, either horizontally or vertically but not both.
Is it possible to assign directions to lasers such that no point is covered by more than one laser? If yes, determine one such assignment.
QUICK EXPLANATION
- If we can determine implications of direction of one laser on others, we can run two SAT on the implication graph to find valid assignment
- If two lasers not sharing row or column can cover same point when assigned different directions, they must be assigned same directions, hence, can be merged into a single component using Union Disjoint Set. In order to merge these lasers, sliding window is required. It is sufficient to merge a node with any node in all four diagonal directions.
- For lasers sharing row or column, those can lead to O(M) implications, which can be added.
EXPLANATION
Who says I cannot use a game image in an editorial?
In our problem, the laser can cover point in two opposite directions only.
For those interested, this game is called Bomberman.
Let’s first see how we can avoid lasers having a common point.
-
If two lasers are in same row or column
If the distance between them is \leq D, then both must be assigned vertical directions.
If the distance between them is \leq 2*D, then both cannot be assigned horizontal (if sharing row) or vertical (if sharing column) direction. -
If two lasers are not sharing row or column
If maximum of horizontal and vertical distance between them is \leq D, then both lasers must have same direction.
It is easy to prove for each case that a point is covered by more than once laser if any of the condition is not met.
Hence, if we find an assignment satisfying above rules, that assignment is the required answer.
Since there are K lasers, and each laser has only 2 states, and there are some implications of state of one variable over other, this is a classical Two-satisfiability problem. Unlike General Boolean Satisfiability problem, Two-satisfiability is solvable in O(N) time for N variables.
Hence, we can consider each pair of lasers, add implications according to above rules and run an instance of TwoSAT on K variables. More on 2-SAT here.
Since there are K^2 pairs, this solution shall pass only the first subtask.
Improving this
Claim: There are O(M) implications arising from lasers sharing same row or column
Proof: Consider N lasers sharing a row, in sorted order of their column. If every adjacent pair of lasers in this list do not cover a common point, then we can see that no pair of lasers would share a common point. Hence, only (N-1) pairs need to be processed.
Now, the issue are the implications arising from pairs of lasers not sharing row or column.
We can benefit from the fact that for these lasers, if they intersect when assigned opposite directions, they must be assigned same directions. Hence, we just need to merge them into a single node for all intent.
Hence, we need to merge pairs of lasers which may intersect and do not share row or column into a single component using union disjoint set and then run TwoSAT on the root nodes of these components.
For a laser at position (x, y), such lasers can lie in any of the four regions bounded by
- (x-D, y-D) and (x-1, y-1)
- (x-D, y+1) and (x-1, y+D)
- (x+1, y-D) and (x+D, y-1)
- (x+1, y+1) and (x+D, y+D)
But there are still K^2 pairs possible in some cases.
Claim: For a laser at position (x, y), consider square region bounded by cells (x-D, y-D) and (x-1, y-1). It is sufficient to merge laser (x, y) with any one laser in this region.
Proof: Consider two lasers (x1, y1) and (x2, y2) in this region. We can see that both of them would have common point with laser (x, y). Since both of them lie in a square box of size D, both of them intersect as well.
Above claim means for each laser, we need to merge it with at most 4 other lasers. Hence, the number of implications is reduced to O(K) and if we can find 4 nodes, one in each region quickly, we have effectively solved the problem.
What is left
For each laser (x, y), Find any laser in each of the four region if region contains at least 1 laser.
It can be done by maintaining a sliding window, considering lasers in sorted order of x coordinate, adding them to a structure when they enter the region and removing them from the structure as soon as they move out of the region.
The structure needs to support following queries
- Add a point (x, y)
- Remove a point (x, y)
- Given v, Find point in structure (x, y) with largest y such that y < v
- Given v, Find point in structure (x, y) with smallest y such that y > v
We can see that ordered set of pair of integers with a custom comparator can be used to support all above queries with a log factor.
Note: Subtask 2 was added only to allow slower implementations to pass
TIME COMPLEXITY
The time complexity is O(N+K*log(K)) or O(K*log(K)) depending upon implementation.
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
/* DSU start */
int par[300005];
int rnk[300005];
void make_set(int i)
{
par[i] = i;
rnk[i] = 0;
}
int find_root(int i)
{
if(i == par[i]) return i;
return par[i] = find_root(par[i]);
}
void set_union(int x, int y)
{
int a = find_root(x);
int b = find_root(y);
if(a != b)
{
if(rnk[a] < rnk[b]) swap(a,b);
par[b] = a;
if(rnk[b] == rnk[a]) rnk[a]++;
}
}
/* DSU end */
/* 2-SAT stuff start */
set<int> adj[600005];
set<int> tadj[600005];
bool vis[600005];
int comp[600005];
int ans[600005];
vector<int> order;
void dfs1(int v)
{
vis[v] = true;
for(auto x : adj[v])
{
if(!vis[x]) dfs1(x);
}
order.push_back(v);
}
void dfs2(int v, int num)
{
comp[v] = num;
for(auto x : tadj[v])
{
if(comp[x] == -1) dfs2(x,num);
}
}
/* 2-SAT stuff end */
void resetStuff(int k)
{
for(int i = 0; i < k; i++)
{
adj[2*i].clear();
adj[2*i+1].clear();
tadj[2*i].clear();
tadj[2*i+1].clear();
vis[2*i] = false;
vis[2*i+1] = false;
comp[2*i] = -1;
comp[2*i+1] = -1;
}
order.clear();
}
void solve(int tc)
{
int n,d,k;
cin>>n>>d>>k;
resetStuff(k);
map<int,vector<pair<int,int>>> forRow, forCol;
int x,y;
for(int i = 0; i < k; i++)
{
make_set(i);
cin>>x>>y;
forCol[x].push_back({y,i});
forRow[y].push_back({x,i});
}
for(auto& xx : forRow)
{
sort(xx.second.begin(), xx.second.end());
}
for(auto& xx : forCol)
{
sort(xx.second.begin(), xx.second.end());
}
// for implementing sliding window
queue<pair<int,int>> q; // x and y coordinates
multiset<pair<pair<int,int>,int>> ms; // {y, x} and index
// DSU step for combining non collinear ones that can overlap
for(auto xx : forCol)
{
while(q.size() && q.front().first < xx.first-d)
{
ms.erase(ms.upper_bound({{q.front().second,q.front().first}, -1}));
q.pop();
}
for(auto yi : xx.second)
{
auto itLower = ms.lower_bound({{yi.first-d, INT_MIN}, -1});
auto itUpper = ms.lower_bound({{yi.first+1, INT_MIN}, -1});
if(itLower != ms.end() && itLower->first.first <= yi.first-1)
{
set_union(yi.second, itLower->second);
}
if(itUpper != ms.end() && itUpper->first.first <= yi.first+d)
{
set_union(yi.second, itUpper->second);
}
}
for(auto yi : xx.second)
{
q.push({xx.first,yi.first});
ms.insert({{yi.first,xx.first},yi.second});
}
}
// applying conditions for those that are in the same row
for(auto xx : forRow)
{
for(int i = 1; i < xx.second.size(); i++)
{
int dist = xx.second[i].first - xx.second[i-1].first - 1;
if(dist >= 2*d) continue;
int a = find_root(xx.second[i-1].second);
int b = find_root(xx.second[i].second);
if(dist >= d)
{
adj[2*a].insert(2*b+1);
adj[2*b].insert(2*a+1);
tadj[2*b+1].insert(2*a);
tadj[2*a+1].insert(2*b);
}
else
{
adj[2*a].insert(2*a+1);
adj[2*b].insert(2*b+1);
tadj[2*a+1].insert(2*a);
tadj[2*b+1].insert(2*b);
}
}
}
// applying conditions for those that are in the same column
for(auto xx : forCol)
{
for(int i = 1; i < xx.second.size(); i++)
{
int dist = xx.second[i].first - xx.second[i-1].first - 1;
if(dist >= 2*d) continue;
int a = find_root(xx.second[i-1].second);
int b = find_root(xx.second[i].second);
if(dist >= d)
{
adj[2*a+1].insert(2*b);
adj[2*b+1].insert(2*a);
tadj[2*b].insert(2*a+1);
tadj[2*a].insert(2*b+1);
}
else
{
adj[2*a+1].insert(2*a);
adj[2*b+1].insert(2*b);
tadj[2*a].insert(2*a+1);
tadj[2*b].insert(2*b+1);
}
}
}
// 2-SAT starts from here
for(int i = 0; i < k; i++)
{
// proceed with only those ones that stay as roots after the DSU step
if(find_root(i) == i)
{
if(!vis[2*i])
dfs1(2*i);
if(!vis[2*i+1])
dfs1(2*i+1);
}
}
int sz = order.size();
int num = 0;
for(int i = sz-1; i >= 0; i--)
{
if(comp[order[i]] == -1)
dfs2(order[i],num++);
}
for(int i = 0; i < k; i++)
{
int rt = find_root(i);
if(comp[2*rt] == comp[2*rt+1])
{
cout<<"No\n";
return;
}
ans[i] = comp[2*rt] > comp[2*rt+1];
}
cout<<"Yes\n";
for(int i = 0; i < k; i++)
{
cout<<ans[i]<<' ';
}
cout<<'\n';
}
int main()
{
clock_t start,end;
double time_taken;
start = clock();
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("14.in","r",stdin);
freopen("14.out","w",stdout);
#endif
int tc;
cin>>tc;
for(int i = 1; i <= tc; i++)
solve(i);
end = clock();
time_taken = double(end-start)/CLOCKS_PER_SEC;
// cout<<time_taken<<" sec";
}
Tester's Solution
import java.util.*;
import java.io.*;
class HKRMAN{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), D = ni(), K = ni();
int[][] P = new int[K][];
for(int i = 0; i< K; i++)P[i] = new int[]{i, ni(), ni()};
int[] set = java.util.stream.IntStream.range(0, K).toArray();
TreeSet<int[]> before = new TreeSet<>((int[] i1, int[] i2) -> {
if(i1[2] != i2[2])return Integer.compare(i1[2], i2[2]);
return Integer.compare(i1[0], i2[0]);
}), after = new TreeSet<>((int[] i1, int[] i2) -> {
if(i1[2] != i2[2])return Integer.compare(i1[2], i2[2]);
return Integer.compare(i1[0], i2[0]);
});
TwoSAT twoSat = new TwoSAT(K);
//Merging lasers not sharing row or column
Arrays.sort(P, (int[] i1, int[] i2) -> {
if(i1[1] != i2[1])return Integer.compare(i1[1], i2[1]);
return Integer.compare(i1[2], i2[2]);
});
for(int i = 0, ii = 0, idx11 = 0, idx2 = 0; i< K; i = ii){
while(idx2 < K && P[idx2][1]-D <= P[i][1])after.add(P[idx2++]);
while(P[i][1]-P[idx11][1] > D)before.remove(P[idx11++]);
while(ii < K && P[i][1] == P[ii][1]){
after.remove(P[ii]);
ii++;
}
for(int j = i; j< ii; j++){
int[] p = P[j];
int[] p1 = before.floor(new int[]{-1, 0, p[2]}), p2 = before.ceiling(new int[]{K, 0, p[2]});
if(p1 != null && p[2]-p1[2] <= D)set[find(set, p1[0])] = find(set, p[0]);
if(p2 != null && p2[2]-p[2] <= D)set[find(set, p2[0])] = find(set, p[0]);
int[] p3 = after.floor(new int[]{-1, 0, p[2]}), p4 = after.ceiling(new int[]{K, 0, p[2]});
if(p3 != null && p[2]-p3[2] <= D)set[find(set, p3[0])] = find(set, p[0]);
if(p4 != null && p4[2]-p[2] <= D)set[find(set, p4[0])] = find(set, p[0]);
}
for(int j = i; j< ii; j++)before.add(P[j]);
}
//Handling lasers sharing a row
// Arrays.sort(P, (int[] i1, int[] i2) -> {
// if(i1[1] != i2[1])return Integer.compare(i1[1], i2[1]);
// return Integer.compare(i1[2], i2[2]);
// });
for(int i = 0, ii = 0; i< K; i = ii){
while(ii < K && P[i][1] == P[ii][1])ii++;
for(int j = i; j+1< ii; j++){
if(P[j+1][2]-P[j][2] <= D){
twoSat.set(find(set, P[j][0]), true);
twoSat.set(find(set, P[j+1][0]), true);
}else if(P[j+1][2]-P[j][2] <= 2*D){
twoSat.addImplication(find(set, P[j][0]), false, find(set, P[j+1][0]), true);
twoSat.addImplication(find(set, P[j+1][0]), false, find(set, P[j][0]), true);
}
}
}
//Handling lasers sharing a column
Arrays.sort(P, (int[] i1, int[] i2) -> {
if(i1[2] != i2[2])return Integer.compare(i1[2], i2[2]);
return Integer.compare(i1[1], i2[1]);
});
for(int i = 0, ii = 0; i< K; i = ii){
while(ii < K && P[i][2] == P[ii][2])ii++;
for(int j = i; j+1< ii; j++){
if(P[j+1][1]-P[j][1] <= D){
twoSat.set(find(set, P[j][0]), false);
twoSat.set(find(set, P[j+1][0]), false);
}else if(P[j+1][1]-P[j][1] <= 2*D){
twoSat.addImplication(find(set, P[j][0]), true, find(set, P[j+1][0]), false);
twoSat.addImplication(find(set, P[j+1][0]), true, find(set, P[j][0]), false);
}
}
}
if(twoSat.satisfiable()){
pn("Yes");
boolean[] ans = twoSat.answer();
StringBuilder o = new StringBuilder();
for(int i = 0; i< K; i++){
o.append((ans[find(set, i)]?1:0));
if(i+1 < K)o.append(" ");
}
pn(o.toString());
}else pn("No");
}
void dbg(Object... o){System.err.println(Arrays.deepToString(o));}
int find(int[] set, int u){return set[u] = set[u] == u?u:find(set, set[u]);}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new HKRMAN().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
class TwoSAT {
private final int n;
private final InternalSCC scc;
private final boolean[] answer;
private boolean hasCalledSatisfiable = false;
private boolean existsAnswer = false;
public TwoSAT(int n) {
this.n = n;
this.scc = new InternalSCC(2 * n);
this.answer = new boolean[n];
}
public void addClause(int x, boolean f, int y, boolean g) {
rangeCheck(x);
rangeCheck(y);
scc.addEdge(x << 1 | (f ? 0 : 1), y << 1 | (g ? 1 : 0));
scc.addEdge(y << 1 | (g ? 0 : 1), x << 1 | (f ? 1 : 0));
}
public void addImplication(int x, boolean f, int y, boolean g) {
addClause(x, !f, y, g);
}
public void addNand(int x, boolean f, int y, boolean g) {
addClause(x, !f, y, !g);
}
public void set(int x, boolean f){
addClause(x, f, x, f);
}
public boolean satisfiable() {
hasCalledSatisfiable = true;
int[] ids = scc.ids();
for (int i = 0; i < n; i++) {
if (ids[i << 1 | 0] == ids[i << 1 | 1]) return existsAnswer = false;
answer[i] = ids[i << 1 | 0] < ids[i << 1 | 1];
}
return existsAnswer = true;
}
public boolean[] answer() {
if (!hasCalledSatisfiable) {
throw new UnsupportedOperationException(
"Call TwoSAT#satisfiable at least once before TwoSAT#answer."
);
}
if (existsAnswer) return answer;
return null;
}
private void rangeCheck(int x) {
if (x < 0 || x >= n) {
throw new IndexOutOfBoundsException(
String.format("Index %d out of bounds for length %d", x, n)
);
}
}
private static final class EdgeList {
long[] a;
int ptr = 0;
EdgeList(int cap) {a = new long[cap];}
void add(int upper, int lower) {
if (ptr == a.length) grow();
a[ptr++] = (long) upper << 32 | lower;
}
void grow() {
long[] b = new long[a.length << 1];
System.arraycopy(a, 0, b, 0, a.length);
a = b;
}
}
private static final class InternalSCC {
final int n;
int m;
final EdgeList unorderedEdges;
final int[] start;
InternalSCC(int n) {
this.n = n;
this.unorderedEdges = new EdgeList(n);
this.start = new int[n + 1];
}
void addEdge(int from, int to) {
unorderedEdges.add(from, to);
start[from + 1]++;
this.m++;
}
static final long mask = 0xffff_ffffl;
int[] ids() {
for (int i = 1; i <= n; i++) {
start[i] += start[i - 1];
}
int[] orderedEdges = new int[m];
int[] count = new int[n + 1];
System.arraycopy(start, 0, count, 0, n + 1);
for (int i = 0; i < m; i++) {
long e = unorderedEdges.a[i];
orderedEdges[count[(int) (e >>> 32)]++] = (int) (e & mask);
}
int nowOrd = 0;
int groupNum = 0;
int k = 0;
int[] par = new int[n];
int[] vis = new int[n];
int[] low = new int[n];
int[] ord = new int[n];
java.util.Arrays.fill(ord, -1);
int[] ids = new int[n];
long[] stack = new long[n];
int ptr = 0;
for (int i = 0; i < n; i++) {
if (ord[i] >= 0) continue;
par[i] = -1;
stack[ptr++] = i;
while (ptr > 0) {
long p = stack[--ptr];
int u = (int) (p & mask);
int j = (int) (p >>> 32);
if (j == 0) {
low[u] = ord[u] = nowOrd++;
vis[k++] = u;
}
if (start[u] + j < count[u]) {
int to = orderedEdges[start[u] + j];
stack[ptr++] += 1l << 32;
if (ord[to] == -1) {
stack[ptr++] = to;
par[to] = u;
} else {
low[u] = Math.min(low[u], ord[to]);
}
} else {
while (j --> 0) {
int to = orderedEdges[start[u] + j];
if (par[to] == u) low[u] = Math.min(low[u], low[to]);
}
if (low[u] == ord[u]) {
while (true) {
int v = vis[--k];
ord[v] = n;
ids[v] = groupNum;
if (v == u) break;
}
groupNum++;
}
}
}
}
for (int i = 0; i < n; i++) {
ids[i] = groupNum - 1 - ids[i];
}
return ids;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 