Destroying Boxes with Line Bombs
Autumn Tournament (2019)
Submission name: bombs.cpp
Problem summary
On a 10⁹×10⁹ board, boxes can be destroyed and stones block fire permanently. A bomb is placed on an empty cell and fires horizontally or vertically in both directions, stopping at the first object on each ray. It destroys that box, if any. Find the minimum number of bombs and a valid ordered placement sequence destroying every box.
Input
N, then N box coordinates; M, then M stone coordinates. Coordinates are row then column.
Output
Minimum count, followed by bombs h row column in execution order: h=1 horizontal, h=0 vertical.
Constraints
1 ≤ N,M ≤ 400,000; coordinates 1..10⁹. Boxes are not on the boundary; all four neighboring cells of each box are initially empty.
Worked example
An independently prepared valid example; output follows the implementation below.
Input
2 2 2 2 4 1 5 5
Output
1 1 2 3
Solution analysis
- Sort all objects by row and column. Connect consecutive boxes on the same line when no stone separates them. Stones reset visibility. These edges define independent components: later removal of boxes can expose more pairs, but cannot join components across a permanent stone or an originally empty unrelated line. A bomb destroys at most two boxes, so a component of s boxes needs at least ceil(s/2) bombs.
- Take any spanning tree of each component and repeatedly examine a deepest internal vertex a; all its children are leaves. If it has one child b, destroy a and b immediately, leaving the rest of the tree connected. If two children b,c lie on the same axis through a, reserve a bomb for b,c until after the rest of this component is removed. Delete those leaves from the tree now. Their sightline will then be clear.
- Otherwise a has exactly two children on different axes. If a has a parent p, one child b is aligned with p−a. Destroy a and the other child c immediately, and replace tree edges p−a−b by p−b: removal of a clears this line. If a is a root, destroy it and one child; its remaining single child needs one final bomb. An isolated root also needs one bomb.
- Use two operation lists. Immediate pairs go to early; deferred leaf pairs go to late. Execute early in order, then late in reverse order. Reversal ensures every deferred pair’s center and remaining component have disappeared before that pair is shot. A queue of vertices whose children are leaves avoids recursive stack overflow. Existing non-tree edges do not invalidate any operation because every used tree sightline is clear.
- Worked example: boxes (2,2) and (2,4) are mutually visible, while stone (5,5) is irrelevant. Their component has size two, so one bomb is optimal. A horizontal bomb at (2,3), an initially empty neighbor cell, destroys both. When placing a bomb for any pair, use the empty neighbor of its first box in the direction of the second.
Why it works
Every operation removes two boxes while preserving a connected visibility tree for the remaining boxes, or finishes with one isolated box. Deferred pairs are valid after reversing their removal order. Hence each component uses exactly ceil(s/2) bombs, matching its lower bound. Bombs cannot hit two boxes from different initial components: if their line contains no stone, the chain of originally consecutive boxes already connected them. The required empty-neighbor guarantee supplies valid placement cells.
Watch out. Stones are not destroyed. Bomb order matters: deferred pairs must be executed in reverse removal order. Retain both row and column coordinates while sorting. A bomb cannot be placed on a surviving box or stone. Handle isolated components and avoid recursive DFS on a chain of 400,000 boxes.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<queue>
#include<set>
#include<utility>
#include<vector>
using namespace std;
struct Object{
int row,column,box;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<pair<int,int>>position(n);
vector<Object>objects;
for(int i=0;i<n;++i){
cin>>position[i].first>>position[i].second;
objects.push_back({position[i].first,position[i].second,i});
}
int stones;
cin>>stones;
for(int i=0;i<stones;++i){
int row,column;
cin>>row>>column;
objects.push_back({row,column,-1});
}
vector<vector<int>>graph(n);
for(int axis=0;axis<2;++axis){
sort(objects.begin(),objects.end(),[&](const Object&a,const Object&b){
if(axis==0){
return pair<int,int>(a.row,a.column)<pair<int,int>(b.row,b.column);
}
return pair<int,int>(a.column,a.row)<pair<int,int>(b.column,b.row);
});
for(size_t i=1;i<objects.size();++i){
const Object&a=objects[i-1];
const Object&b=objects[i];
bool sameLine=axis==0?a.row==b.row:a.column==b.column;
if(sameLine&&a.box!=-1&&b.box!=-1){
graph[a.box].push_back(b.box);
graph[b.box].push_back(a.box);
}
}
}
vector<int>parent(n,-2),alive(n,1);
vector<set<int>>children(n);
for(int root=0;root<n;++root){
if(parent[root]!=-2){
continue;
}
parent[root]=-1;
vector<int>stack={root};
while(!stack.empty()){
int u=stack.back();
stack.pop_back();
for(int v:graph[u]){
if(parent[v]==-2){
parent[v]=u;
children[u].insert(v);
stack.push_back(v);
}
}
}
}
queue<int>pending;
auto ready=[&](int u){
if(u<0||!alive[u]){
return false;
}
for(int v:children[u]){
if(!children[v].empty()){
return false;
}
}
return true;
};
auto schedule=[&](int u){
if(ready(u)){
pending.push(u);
}
};
for(int u=0;u<n;++u){
if(!children[u].empty()||parent[u]==-1){
schedule(u);
}
}
vector<pair<int,int>>early,late;
auto horizontal=[&](int a,int b){
return position[a].first==position[b].first;
};
while(!pending.empty()){
int a=pending.front();
pending.pop();
if(!ready(a)){
continue;
}
vector<int>leaf(children[a].begin(),children[a].end());
if(leaf.empty()){
if(parent[a]==-1){
early.emplace_back(a,-1);
alive[a]=0;
}
continue;
}
int b=-1;
int c=-1;
for(size_t i=0;i<leaf.size();++i){
for(size_t j=i+1;j<leaf.size();++j){
if(horizontal(a,leaf[i])==horizontal(a,leaf[j])){
b=leaf[i];
c=leaf[j];
}
}
}
if(b!=-1){
// Remove the center later, then these two leaves see each other.
late.emplace_back(b,c);
alive[b]=alive[c]=0;
children[a].erase(b);
children[a].erase(c);
schedule(a);
schedule(parent[a]);
continue;
}
b=leaf[0];
int p=parent[a];
if(leaf.size()==1){
early.emplace_back(a,b);
alive[a]=alive[b]=0;
if(p!=-1){
children[p].erase(a);
schedule(p);
schedule(parent[p]);
}
}
else{
c=leaf[1];
if(p!=-1&&horizontal(p,a)!=horizontal(a,b)){
swap(b,c);
}
// Keep the leaf aligned with the parent; deleting a opens their sightline.
early.emplace_back(a,c);
alive[a]=alive[c]=0;
parent[b]=p;
if(p!=-1){
children[p].erase(a);
children[p].insert(b);
schedule(p);
}
else{
schedule(b);
}
}
}
early.insert(early.end(),late.rbegin(),late.rend());
cout<<early.size()<<'\n';
for(auto[a,b]:early){
int row=position[a].first;
int column=position[a].second;
int type=1;
if(b==-1){
--column;
}
else if(horizontal(a,b)){
column+=position[b].second>column?1:-1;
}
else{
type=0;
row+=position[b].first>row?1:-1;
}
cout<<type<<' '<<row<<' '<<column<<'\n';
}
}