PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Nishan Singh
Tester & Editorialist: Taranpreet Singh
DIFFICULTY
Medium
PREREQUISITES
Implementation, Union Disjoint set
PROBLEM
A kingdom organized in form of N cities numbered from 1 to N connected via roads to form a tree structure. This tree is rooted at city 1, the capital city, where king resides. A city is called leaf, if it is not capital, and it has exactly one adjacent city. There is huge reward on assassination of king residing in capital city.
From each leaf city, an assassin starts its journey towards capital. Each assassin moves one city near to the capital each day. If two assassin’s arrive at same city on same day, they make a pact not to attack each other, and split the reward. Every day, if some assassin B lies on path of assassin A, assassin A uses his magical power to kill assassin B. After all magic powers are used, each assassin, who is attacked, dies. Now, the remaining assassin moves. Suppose assassin A just used his magical power to kill someone. Then among cities of all assassins he killed, he shall move to the city nearest to the kingdom next day. If some assassin can be killed by multiple assassins, they shall do it together, assuming neither of them can kill each other.
You need to find out which the day some assassin reaches capital city, and the set of assassins who reaches the capital city together.
QUICK EXPLANATION
- Simulate the process in terms of maintaining alive assassin locations, the groups formed with respect to time.
- Use union-disjoint sets to maintain groups of assassins who have formed a pact.
EXPLANATION
Since this is mostly a simulation problem, it’d just require us to process the whole sequence of actions happening according to the statement.
Subtask 1
Here N \leq 2000. And within N days, all assassins can reach capital city, so if we can simulate each day in O(N) time, it is sufficient to pass this subtask.
Let us break down what happens each day in sequence it happens.
- Each assassin moves to its next node (either parent node, or location of some assassin killed in previous move)
- Checking if some assassin is at capital city, we find the set of assassins reaching capital and print the time and set.
- If not, let’s merge the assassins at the same node into a single node. This can be done using Union disjoint sets, using one node as representative of each group.
- Magical power is used now, So all assassins, which have some other assassin in their subtree die.
- Now, for each alive assassin, we need to locate the farthest ancestor which had an assassin before magical power is used today, to maintain next_u, the location assassin at city u shall move on next day.
This sequence of operation repeats every day, until some assassin reaches capital.
To simulate this, we need to maintain union-disjoint sets, so as to easily maintain groups of assassins who made pact. That way, if representative node reaches capital, all nodes have reached capital.
We also need to maintain next_u which, for each day, determines the location, where the assassin standing at node u shall move on next day. If we process the last two steps in a DFS style manner, passing location of farthest ancestor from top to down, and killing assassins in bottom up manner, simulation can run in O(N) or O(N*log(N)) depending upon implementation per day.
Hence, overall time complexity is O(N^2*log(N)) per test case.
Complete Solution
The complete solution would be several observations on above solution.
Observation 1: If d is the earliest day when some assassin enters node u, then the last day some assassin enters node u is either d or d+1
Proof:
- If there are no assassin’s in subtree of u excluding the ones on node u, the last day some assassin was on node u is day d
- Otherwise all assassins who would kill the assassin on node u on day d, arriving on node u on day d+1. Hence, there’s no more assassin in subtree of node u after day d+1
Hence, on day d, we shall invoke a method called process on node u, that would carry out the application of magic power, and updating the next array for all nodes in subtree of node u. process(u) is invoked on day d.
Observation 2: When processing node u, if there are multiple assassins in subtree of node u, they all shall be merged on next day, since they all arrive on node u on next day. Hence, all those can be merged, either during DFS, or during next day.
Observation 3: If multiple nodes are to processed on some day, it is sufficient to process the nodes in the increasing order of their depths
Proof: Let’s assume assassins A on city a and B on city b are on path of assassin C at node c, and assassin A is closer to capital city. If we process node B first, we’d first update next_c = b, then later need to update next_c = a since C shall go to city a on next day. In this case, assassin C had to be processed twice, once for assassin B and once for assassin A.
To avoid that, we process all the cities containing assassins closer to capital first. When process(a) is called, it recursively processes nodes b and c too. So, later, we’d not need to process city b again. Hence, each city would be processed only once.
During process(u), we don’t need to enter subtrees of nodes already processed.
Hence, all process calls combined takes O(N) iterations. Each assassin enters an unvisited node every time, or the one visited on previous day, hence the total number of jumps by assassins is bounded by 2*N
Hence, if implemented correctly, the time complexity should be O(N*log(N)) due to min-heap used to process nodes in order of depth. If you can claim any O(N) solution, do comment.
Challenge
Try making tests for this problem, to fail sub-optimal solutions. There are many hack solutions due to the structure of the problem.
Some hacks:
- Stopping when only one group of assassins is alive
- All alive assassins are at same depth
- Not using path compression or weighted union in union disjoint sets.
Try finding hacks, or prove their time complexity.
TIME COMPLEXITY
The time complexity is O(N*log(N)) per test case.
SOLUTIONS
Setter's Solution
//Complete solution
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
/* #include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree
<T, null_type, less<T>,
rb_tree_tag,tree_order_statistics_node_update>;
*/
#define rep(i,k,n) for(int i = k; i < n; i++)
#define per(i,k,n) for(int i = k; i >= n; i--)
#define repp(i,a,n,k) for(typeof(a) i=a;i!=n;i+=k)
//#define int long long
#define all(a) a.begin(),a.end()
#define pb push_back
typedef long long ll;
typedef long double ldl;
typedef pair<int, int> ii;
typedef pair<int,ii > iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<char> vchar;
#define fill(a,b) memset(a, b, sizeof(a))
#define setbits(x) __builtin_popcountll(x)
#define debug(a) cout<<#a<<": ";for(auto i:a)cout<<i<<" ";cout<<'\n';
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define me max_element
#define INF 1000000000
//#define mod 998244353
#define mod 1000000007
//#define endl "\n"
const int MaxN = 2e5+10;
vi gr[MaxN];
bool vis1[MaxN];
bool vis2[MaxN];
vi gr_final[MaxN];
bool vis_final[MaxN];
ii ti[MaxN];
int dep[MaxN];
int dfs1(int n, int depth){
vis1[n]=1;
dep[n]=depth;
//if(depth>85000)cout << depth << endl;
if(gr[n].size()==1 && n!=1){
ti[n] = {0,0};
//cout << n << endl;
return ti[n].ss;
}
int mi = INF, ma = 0;
for(auto i : gr[n]){
if(!vis1[i]){
int tmp = dfs1(i, depth+1);
ma = max(ma,tmp+1);
mi = min(mi,tmp+1);
}
}
ti[n] = {mi, mi + (mi!=ma)};
//if(depth>0)cout << depth << endl;
return ti[n].ss;
}
multiset<pair<int, ii> > X;
int flag = 0;
void dfs2(int n, int pa){
vis2[n]=1;
int mi = INF;
pair<int, ii> tmp = *X.begin();
if(ti[n].ss == tmp.ff){
gr_final[tmp.ss.ss].pb(n);
gr_final[n].pb(tmp.ss.ss);
// cout << "Connect: " << tmp.ss.ss << " " << n << endl;
}else if(flag ==1){
gr_final[n].pb(pa);
gr_final[pa].pb(n);
//cout << "Connect: " << pa << " " << n << endl;
}
X.insert({ti[n].ff, {dep[n],n}});
for(auto i : gr[n]){
if(!vis2[i]){
flag = (ti[n].ff==ti[n].ss);
//cout << ti[n].ff << " " << ti[n].ss << endl;
dfs2(i, n);
}
}
X.erase({ti[n].ff, {dep[n],n}});
}
int anss = INF;
vi ans;
void dfs_final(int n, int x){
if(vis_final[n])return;
vis_final[n]=1;
//if(n==3956){
// cout << gr_final[3956].size() << endl;
// }
if((gr_final[n].size()==1 && n!=x) || (gr_final[n].size()==0) || ((gr_final[n].size()==1 && gr_final[n][0]==1))){
ans.pb(n);
}
for(auto i : gr_final[n]){
if(i!=1)dfs_final(i,x);
}
}
void solve(){
flag = 0;
X.clear();
anss =INF;
ans.clear();
int n;
cin >> n;
rep(i,0,n+2){
gr[i].clear();
gr_final[i].clear();
vis1[i] = vis2[i] = vis_final[i] = 0;
}
rep(i,1,n){
int a1, b1;
cin >> a1 >> b1;
gr[a1].pb(b1);
gr[b1].pb(a1);
}
dfs1(1,0);
// cout << 11 << endl;
dfs2(1, 0);
int mi = INF;
for(auto i : gr[1]){
if(ti[i].ss<mi){
mi = ti[i].ss;
}
}
for(auto i : gr[1]){
if(mi==ti[i].ss){
dfs_final(i, i);
//cout << i << endl;
anss = ti[i].ss;
}
}
sort(all(ans));
cout << ans.size()<< " " << anss+1 << endl;
rep(i,0,ans.size()){
cout << ans[i];
if(i!=ans.size()-1)cout << " ";
}cout << endl;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//cout << fixed;
//cout <<setprecision(6);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("ans2.txt", "w", stdout);
#endif
int test=1; cin >> test; while(test--)
solve();
}
Tester's Solution
import java.util.*;
import java.io.*;
class KKLING{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
int[] from = new int[N-1], to = new int[N-1];
for(int i = 0; i< N-1; i++){
from[i] = ni()-1;
to[i] = ni()-1;
}
int[][] tree = make(N, from, to);
int[] par = new int[N], d = new int[N];
int[] location = new int[N];//location of ith assassin, or -1 if i is not an assassin, or i is dead
int[] node = new int[N];//id of assassin on ith node, or -1 if no assassin on ith node
Arrays.fill(location, -1);
Arrays.fill(node, -1);
precalc(tree, par, d, location, 0, -1);
for(int i = 0; i< N; i++)if(location[i] != -1)node[location[i]] = i;
int[] set = java.util.stream.IntStream.range(0, N).toArray();//Maintaining sets of assassins
PriorityQueue<int[]> q = new PriorityQueue<>((int[] i1, int[] i2) -> {
if(d[i1[1]] != d[i2[1]])return Integer.compare(d[i1[1]], d[i2[1]]);
return Integer.compare(i1[1], i2[1]);
});
for(int i = 0; i< N; i++)if(location[i] != -1)q.add(new int[]{i, i});
boolean[] processed = new boolean[N];
int winTime = -1;
for(int time = 1; time <= N; time++){
for(int[] pair:q){
location[pair[0]] = -1;
node[pair[1]] = -1;
}
//Min-heap to fetch assassin with location closest to root
PriorityQueue<int[]> nq = new PriorityQueue<>((int[] i1, int[] i2) -> {
if(d[i1[1]] != d[i2[1]])return Integer.compare(d[i1[1]], d[i2[1]]);
return Integer.compare(i1[1], i2[1]);
});
//Moving to next[u], if u is location (par is eqivalent to next array)
//pair[0] -> assassin ID
//pair[1] -> location
for(int[] pair:q)nq.add(new int[]{pair[0], par[pair[1]]});
q.clear();
//Merging assassins at same node
int prevAssassin = -1, prevNode = -2;
while(!nq.isEmpty()){
int[] pair = nq.poll();
if(pair[1] == prevNode){
set[find(set, pair[0])] = find(set, prevAssassin);
}else {
prevNode = pair[1];
prevAssassin = pair[0];
q.add(new int[]{pair[0], pair[1]});
location[pair[0]] = pair[1];
node[pair[1]] = pair[0];
}
}
//Checking if some assassin is at node 0 (0-based indexing)
if(node[0] != -1){
winTime = time;
break;
}
//Processing all nodes having assassins in order of their depths
while(!q.isEmpty()){
int[] pair = q.poll();
if(processed[pair[1]])continue;//this node is already processed
process(nq, tree, processed, par, location, node, pair[1], par[pair[1]], pair[0]);
}
q = nq;
}
List<Integer> ans = new ArrayList<>();
for(int i = 0; i< N; i++)if(find(set, i) == find(set, node[0]))ans.add(1+i);
pn(ans.size()+" "+winTime);
for(int x:ans)p(x+" ");pn("");
}
//Processing nodes
boolean process(PriorityQueue<int[]> q, int[][] tree, boolean[] processed, int[] par, int[] location, int[] node, int u, int p, int ancestor) throws Exception{
boolean contains = false;//Determining if there's any assassin in subtree of node u except at node u
for(int v:tree[u]){
if(v == p || processed[v])continue;
contains |= process(q, tree, processed, par, location, node, v, u, ancestor == -1?node[u]:ancestor);
processed[v] = true;
}
if(contains && node[u] != -1){
//Subtree of node u contains an assassin, so assassin at current node dies
location[node[u]] = -1;
node[u] = -1;
}
if(ancestor != -1 && node[u] != -1){
//Current assassn survived, and there's some ancestor killed on same day
//or node u itself, if no assassin in subtree of u
if(ancestor != node[u])par[u] = location[ancestor];
q.add(new int[]{node[u], u});
}
return contains || node[u] != -1;
}
void precalc(int[][] tree, int[] par, int[] d, int[] location, int u, int p){
par[u] = p;
location[u] = u;
for(int v:tree[u])if(v != p){
location[u] = -1;
d[v] = d[u]+1;
precalc(tree, par, d, location, v, u);
}
}
int[][] make(int N, int[] from, int[] to){
int[] cnt = new int[N];
for(int x:from)cnt[x]++;
for(int x:to)cnt[x]++;
int[][] g = new int[N][];
for(int i = 0; i< N; i++)g[i] = new int[cnt[i]];
for(int i = 0; i< N-1; i++){
g[from[i]][--cnt[from[i]]] = to[i];
g[to[i]][--cnt[to[i]]] = from[i];
}
return g;
}
int find(int[] set, int u){return set[u] == u?u:find(set, set[u]);}
static void dbg(Object... o){System.err.println(Arrays.deepToString(o));}
//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 KKLING().run();
new Thread(null, new Runnable() {public void run(){try{new KKLING().run();}catch(Exception e){e.printStackTrace();System.exit(1);}}}, "1", 1 << 28).start();
}
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;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
Similar Approach
