KKLING - Editorial

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. :slight_smile:

1 Like

Very nice. In last 30 min of contest 70 peoples submit corect solution. Good peoples!!!

21 Likes

This was such an interesting problem. Such a good editorial too… I could not do the full solution but it kept me thinking everyday till the end. Greate problem @retarded_ape !

2 Likes

@taran_1407 I got O(N) solution of KKLING. Please check.

My solution finds minimum days required to solve a sub tree remembering minimum days required to solve subtree of ancestors which is my constraint to solve subtree here. We need to just add constraint on number of days a subtree should spend while solving it. And its DONE. : )

Link: CodeChef: Practical coding for everyone

2 Likes

My O(N) solution.
I first calculated the day which will be the answer. Now the problem got reduced to the fact that which assassins will not survive by that time and rest all will be included in the answer. Using a pretty cool fact that whether to visit a particular branch or not.

solution:- Here

4 Likes

:star_struck: Similar Approach

2 Likes

what does this part do in your code. What is the dp array storing exactly?
if (mp.size() > 1 && x != 1)
dp[x]++;

I just simulated efficiently, observed that an assassin who moves to a town that is not a leaf at that moment will always be killed by its descendants. So I kept checking this condition, but I couldn’t prove the actual time complexity of my solution. If someone can prove the time complexity or hack my solution if possible :smiley:

2 Likes

This question can also be solved by storing IN Time(in and out time concept) as parameter to sort nodes at which assassins are. And then Linear Algorithm to find who kills who as all nodes in subtree will be one after another after sorting. This approach will also take O(NlogN) time.

3 Likes

dp array is storing the minimum days require to reach a node by all the assassins present in the subtree of that node.

This part is based on what is given in the editorial. If all the assassin (in the subtree of x) are not reaching on the same day then it will take 1 more day for the rest of the assassin to kill the assassin that will reach first. so dp[x] = (1 + minimum time require to reach its immediate child) + (1 if they all does not reach at the same time).

2 Likes

got it. Thanks a lot.

My Solution is O(N), and it’s pretty simple I only used dfs.
but it’s pretty different from everyone’s solution here

Can anyone provide test cases for the failing items in the below submission? I have tried lots of different trees and all seem to be working fine :slightly_frowning_face:
https://www.codechef.com/viewsolution/46604947

Try this:

1
19
1 2
2 3
3 4
2 5
5 6
6 7
7 8
8 9
9 10
10 11
6 12
12 13
13 14
14 15
6 16
16 17
17 18
18 19

Expected output:

3 4
11 15 19

Thank you…

Why does smaller to large set merging not pass? Shouldn’t this be O(nlogn)? CodeChef: Practical coding for everyone

Thanks, This comment really made my day. This is the first problem I have authored so it means a lot to me ^_^.

3 Likes

really appreciable problem :+1::slightly_smiling_face:

Yes, please if someone can provide some test cases. I just saw pes2020’s solution and it has failed in exactly the same test cases as my solution. Many others may also benefit if they are failing on these test cases

I can’t understand your code but my idea ( code) was similar and had O(N) complexity + sorting at the last