Minimum Artillery to Catch an Invisible Pawn
Autumn Tournament (2018)
Submission name: artillery.cpp
Problem summary
An invisible pawn occupies a vertex of a tree. Each round you shoot K chosen vertices; between rounds the surviving pawn may stay or move to a neighboring vertex. Find the minimum K that guarantees capture, regardless of its initial position and moves.
Source clarification. The exact two-state simplification uses the official up/down/normal DP and its non-leaf-root observation; up and down are equal by reversal symmetry. Editorial: https://infos.infosbg.com/files/Contests/ETI/2018/B/analyses/B2_artillery_analysis.pdf
Input
T cases. Each gives N and N−1 undirected edges with vertices numbered0…N−1.
Output
One minimum artillery count per case.
Constraints
1 ≤ T ≤10; 1 ≤ N ≤100000.
Worked example
Original statement sample.
Input
2 8 0 1 0 2 0 3 1 4 2 5 3 6 3 7 9 0 1 0 2 0 3 1 4 1 5 1 6 3 7 3 8
Output
3 2
Solution analysis
- The difficulty is preventing the pawn from reentering an already cleared branch. Root the tree at any non-leaf when N>2. For each subtree store normal, the cost to clear it, and directional, the cost to sweep through it in one chosen boundary direction. Reversing a strategy exchanges up/down sweeps, so their costs are equal on an undirected tree.
- At a vertex, one child can be processed first without keeping the root guarded, and one child last without that guard. All middle children require one extra gun at the root. Thus the two hardest children can use directional sweeps, while the third-hardest normal child determines the extra-guard bottleneck. For a one-directional sweep only one child is exceptional, leaving the second-hardest normal child as its guard bottleneck.
- Keep the three largest child normal costs. With child states(b1,d1),(b2,d2),(b3,d3), directional=max(2,d1,b2+1) and normal=max(2,d1,d2,b3+1), omitting unavailable terms. A leaf has both costs1; a one-child subtree has both max(2,d1). The baseline2 is essential: one gun cannot reliably clear even a two-vertex path when the pawn may stay.
- In the first sample, three difficult branches meet at vertex0; one must be cleared while that junction remains guarded, requiring3 guns. In the second, the two more difficult branches can be the first and last sweeps and the remaining branch is a single leaf, so2 suffice. An iterative parent order followed in reverse evaluates the DP without recursive stack overflow.
Why it works
The official subtree-clearing argument shows that branches can be processed one at a time without increasing the optimum. Only the first and last branch can avoid a permanent guard at the connecting root; directional sweeps characterize these two exceptions. Applying this necessity and the matching first/middle/last strategy gives the recurrences. Child costs ordered by normal value need only the largest three, since all lower middle branches are dominated. The editorial further shows that any non-leaf can serve as an optimal root; the N=1 and N=2 boundary cases are handled explicitly by the base transitions.
Watch out. The pawn may stay still, so parity tricks for a pawn forced to move do not apply. Shooting one branch without guarding the separator can recontaminate cleared branches. Do not report a one-extra-gun partial-scoring heuristic as exact. Respect the original0-based vertex labels.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<vector>
using namespace std;
struct Cost{
int normal=0;
int directional=0;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tests;
cin>>tests;
while(tests--){
int n;
cin>>n;
vector<vector<int>>graph(n);
for(int i=1;i<n;++i){
int u,v;
cin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int root=0;
for(int u=0;u<n;++u){
if(graph[u].size()>=2){
root=u;
break;
}
}
vector<int>parent(n,-1),order{root};
parent[root]=root;
for(int i=0;i<static_cast<int>(order.size());++i){
int u=order[i];
for(int v:graph[u]){
if(v!=parent[u]){
parent[v]=u;
order.push_back(v);
}
}
}
vector<Cost>cost(n);
for(int i=n-1;i>=0;--i){
int u=order[i];
array<Cost,3>largest{};
int children=0;
for(int v:graph[u]){
if(v==parent[u]){
continue;
}
++children;
Cost candidate=cost[v];
// Only the three hardest child states can affect the result.
for(int slot=0;slot<3;++slot){
if(candidate.normal>largest[slot].normal||
(candidate.normal==largest[slot].normal&&
candidate.directional>largest[slot].directional)){
swap(candidate,largest[slot]);
}
}
}
if(children==0){
cost[u]={1,1};
}
else if(children==1){
int result=max(2,largest[0].directional);
cost[u]={result,result};
}
else{
int directional=max({2,largest[0].directional,largest[1].normal+1});
int normal=max({2,largest[0].directional,largest[1].directional});
if(children>=3){
normal=max(normal,largest[2].normal+1);
}
cost[u]={normal,directional};
}
}
cout<<cost[root].normal<<'\n';
}
}