PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Shresth Walia
Tester: Tester’s name
Editorialist: Abhishek Chopra
DIFFICULTY:
Medium
PREREQUISITES:
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;
}
