TRECYB - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Shresth Walia
Tester: Tester’s name
Editorialist: Abhishek Chopra

DIFFICULTY:

Medium

PREREQUISITES:

Expected Value, BFS

PROBLEM:

Let A be an array of N elements and let us define beauty of array as (consider 1 based indexing)

long long int beauty(int N, int A[]){
     long long int val = 0;
     for(int i = 1; i < N; i++){
           for(int j = i + 1; j <= N; j++){
                 if(a[i] < a[j]){val++;}
                 else{val--;}
           }
     }
     return val;
}

Let G be a tree with N nodes numbered from 1 to N rooted at node 1. Find the Expected Beauty of all the valid BFS(BreadthFirstSearch) of G.

QUICK EXPLANATION:

Consider any bfs ordering Q w.r.t node 1, now from the nature of function, consider two elements, Q_i, Q_j at same depth the contribution of value across all permutations will be 0, hence you just need to calculate the value of above function across different depths which can easily be done by range queries.

EXPLANATION:

To calculate the E[beauty], first we try to prove that we need not take into account for pair values at same level, in bfs.

Let’s say two elements, Q_i, Q_j are at same depth, the number of bfs permutations in which Q_i occurs before Q_j = the number of permutations in which Q_i occurs after Q_j. Hence the value is incremented and decremented equal number of times i.e 0 contribution.

Why the number of permutations are equal?

My claim is half of all the valid possible orderings will have Q_i visit before Q_j and the other half will have Q_i visit after Q_j.
Firstly let us denote the number of children of each node i by d_i. Hence total possible bfs orderings are \Pi d_i! (1 \le i \le n). If node Q_i is to be visited before Q_j we will also have to visit the ancestors of Q_i not later than Q_j. Let l be the lowest common ancestor (lca) of Q_i and Q_j and P_i, P_j be the immediate children of l such that P_i and P_j are ancestors of Q_i and Q_j respectively. There are d_l! ways of visiting children of node l and we select 2 positions and force P_i before P_j there are
\binom{d_l}{2} * (d_l -2)! ways of doing so. No matter how we permute things now on other nodes we ensure Q_i is always visited before Q_j since we also assumed they have same depth as well. Now the number of such orderings is d_1!*d_2! \dotso \binom{d_l}{2} * (d_l-2)! \dotso d_n!. Which is nothing but half of all possible bfs orderings.

Do refer to the wikipedia link of bfs, if you want to understand why making such choice at lca ensured this. If you have any difficulties feel free to ping me.

Now the problem is simply reduced to calculate the function only across different depth level in bfs tree. One way to do this is first calculate depth of each node and store them. Now iterate the node in the order of depth. For some depth d, add number of elements less than curNode - number of elements greater than curNode which are less than depth d. Update the segment tree once you iterate over all the nodes at depth d.

SOLUTIONS:

Setter's Solution
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define hackcyborg shresth_walia
#define all(a) a.begin(), a.end()
#define ll long long 
#define ld long double
#define pb push_back
#define mod 1000000007
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define ordered_set tree<int,null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
ll bp(ll a,ll b)
{
    ll res=1;
    while(b>0)
    { 
        if(b&1)
        res=(a*res)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return res;
}
vi ar[200001];
ll dep[200001]={0};
vi dp[200001];
void dfs(ll s,ll p)
{  dp[dep[s]].pb(s);
   for(auto it : ar[s])
	if(it!=p)
	{dep[it]=dep[s]+1;
	dfs(it,s);}
}
main()
{
   IO
   ll n;
   cin>>n;
   ll u,v;
   for(int x=1;x<n;x++)
   {cin>>u>>v;
   	ar[u].pb(v);}
   dfs(1,-1);
   ordered_set as;
   ll ans=0;
   for(int x=200000;x>=0;x--)
   {
   	  for(auto it : dp[x])
   	  {
   	  	  ans-=(as.order_of_key(it));
   	  	  ans+=(as.size()-as.order_of_key(it));
   	  }
   	  for(auto it : dp[x])
   	  as.insert(it);
   }
   cout<<ans<<"\n";
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
           
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
            assert(l<=x && x<=r);
            return x;
        } else {
            cerr << (int)g << "\n";
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
int main() 
{
    FIO;
    int t,n,q,k,i,j,sum_n,sum_q;
    
    t=readIntLn(1,1000);
    sum_n=0;
    sum_q=0;
    while(t--){
        n=readIntSp(1,100000);
        q=readIntLn(1,100000);
        sum_n+=n;
        sum_q+=q;
        ll arr[n+3]={0};
        while(q--){
            j=readIntSp(1,n);
            k=readIntLn(j,n);    
            arr[j]++;
            arr[k+1]--;
            arr[k+1]-=(k-j+1);
            arr[k+2]+=(k-j+1);
        }
        for(i=1;i<=n;i++)
            arr[i]+=arr[i-1];
        for(i=1;i<=n;i++)
            arr[i]+=arr[i-1];
        
        for(i=1;i<=n;i++)
            cout << arr[i] << " ";
        cout << "\n";
    }
    assert(getchar()==-1);
	assert(sum_n<=1000000);
	assert(sum_q<=1000000);
	return 0;
}  
Editorialist's Solution
#define _CRT_SECURE_NO_DEPRECATE
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include "bits/stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define int long long int
#define SYNC std::ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define FRE freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii>   vii;
//typedef tree<int, null_type, less<int>, rb_tree_tag,
//             tree_order_statistics_node_update>
//    ost;
#define rep(i,l,r)   for (int i = (l); i < (r); i++)
#define here cout << " Hey!!\n";
#define  pb push_back
#define  F  first
#define  S  second
#define all(v) (v).begin(),(v).end()
#define sz(a) (int)((a).size())
#define sq(x) ((x)*(x))
const int MOD = 1e9+7;
const int MOD1 = 998244353;
const int N = 2e5+5;
const int INF = 1000111000111000111LL;
const ld EPS = 1e-12;
const ld PI = 3.141592653589793116;

struct seg_tree 
{

    vector<int> bit;
    vector<int> a;
    int n;
    seg_tree(int n) {
        this-> n = n;
        bit.assign(4*n+1,0);
    }
    seg_tree(vector<int> a) : seg_tree(a.size())
    {
        this-> a = a;
        build(0,0,(int)a.size()-1);
    }
    int merge(int x, int y) {
        // Function to return 
        return x + y;
    }
    void build(int node, int start, int end)
    {
        if(start == end)
        {
            bit[node] = a[start];
            return;
        }
        int lch = 2*node+1;     //Left Child
        int rch = 2*node+2;     //Right Child
        int mid = (start+end)/2;
        build(lch,start,mid);
        build(rch,mid+1,end);
        bit[node] = merge(bit[lch],bit[rch]);
        return; 
    }
    void update(int node, int start, int end, int pos, int val)
    {   
        if(start==end)
        {
            bit[node] = val;
            return;
        }
        int mid = (start + end)/ 2;
        int lch = 2*node + 1;
        int rch = 2*node + 2;
        if(pos<=mid)
            update(lch,start,mid,pos,val);
        else
            update(rch,mid+1,end,pos,val);
        bit[node] = merge(bit[lch],bit[rch]);
    }
    int query(int node,int start,int end, int l, int r)
    {
        if(l>end or r<start or start>end)
            return 0;
        if(l<=start and r>=end)
            return bit[node];
        int lch = 2*node+1;     //Left Child
        int rch = 2*node+2;     //Right Child
        int mid = (start+end)/2;
        return merge(query(lch,start,mid,l,r),query(rch,mid+1,end,l,r));
    }
};

int32_t main()
{
    SYNC
    int n; cin >> n;
    vector<int> g[n];
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        u--, v--;
        g[u].pb(v);
        g[v].pb(u);
    }
    vector<int> layer(n, -1);
    vector<vector<int>> a(n);
    queue<int> Q;
    Q.push(0);
    layer[0] = 0;
    while (!Q.empty()) {
        int cur = Q.front();
        a[layer[cur]].pb(cur);
        Q.pop();
        for (auto to : g[cur]) {
            if (layer[to] == -1) {
                layer[to] = layer[cur] + 1;
                Q.push(to);
            }
        }
    }
    int beauty = 0;
    seg_tree sg(vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (auto x : a[i]) {
            beauty += sg.query(0,0,n-1,0,x-1);
        }
        for (auto x : a[i]) {
            sg.update(0,0,n-1,x,1);
        }
    }
    seg_tree _sg(vector<int>(n, 0));
    for (int i = n - 1; i >= 0; i--) {
        for (auto x : a[i]) {
            beauty -= _sg.query(0,0,n-1,0,x-1);
        }
        for (auto x : a[i]) {
            _sg.update(0,0,n-1,x,1);
        }
    }
    cout << beauty;
    return 0;
}
3 Likes

Please link the editorial on the problem page also.

Can someone please explain this a bit more. Not able to understand much.

Hey, Consider an example tree in which node 1 is at depth 0 , node 2 and 3 are at depth 1, and node 4, 5, 6 are at depth 2. Now number of all possible bfs orderings in which 4 is before 5 is same as number of all possible bfs orderings in which 4 is after 5.

Work out this example for any tree with same depth ordering I mentioned. Maybe that will give some more clue.

Try if you can deduce this if not I will add explanation in editorial. :slight_smile:

Hint

If Q_i occurs before Q_j it means we should visit Q_i first, now the ancestors of Q_i should also be visited before the ancestors of Q_j. Perform the same analysis with assumption Q_i occurs after Q_j the count of both possible permutations is same.

1 Like

For those who dont know Segment tree or are finding the code hard to understand.
I have used only array and vector.
https://www.codechef.com/viewsolution/40947602
Have fun :slight_smile:
P.S. : Just came to knew that it can get Tle’d as well

I understood what you mean to say, but not yet fully. If you could provide some mathematical proof :sweat_smile:

1 Like

Do check the editorial (updated now), I tried my best to give some mathematical proof.

4 Likes

I need help with my approach.

My approach:

Beauty = x-y
y can be seen as number of inversions

Let sz be the size of permutation
Also, x+y = sz*(sz-1)/2 (call this ‘c’ for the moment)

So, after replacing x, beauty = c-2*y
E(b) = E( c) - 2 * E(y)

E( c) = n * (n-1) / 2

E(y) = sum of inversions caused at 1 level due to another level + inversions caused at a level by elements from the same level

Since we know at all elements are unique at a level, I calculated expected value of inversions for a permutation from here.

I am getting WA with this and am unable to see any mistake in this approach.

My Code

UPD: I got my mistake. There was no mistake in the logic part, I screwed up the implementation.

P.S. I liked the problem very much. I am going to save this in my "Problems that taught me somethings list"

1 Like