# STRPTRE - Editorial

Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

Easy

# PREREQUISITES:

Combinatorics, Observation

# PROBLEM:

Given a complete binary tree with depth D and N = 2^{D+1}-1 nodes, rooted at node 1. The edges connecting nodes at Odd depth to their parent are colored white, while edges connecting nodes at even depth with their parent are colored black.

A strip is a cycle where no two adjacent edges have the same color.

When choosing two distinct nodes u and v, and color c randomly equiprobably, and adding an edge from u to v with color c, find the probability of making a strip.

# QUICK EXPLANATION

• A strip can be generated only when the edge added from a node to its ancestor.
• The strip always has even length, so we can connect a node with its ancestors at an odd distance to make a strip.
• Now we just need to keep track of the number of ancestors of a node at both odd and even distance.

# EXPLANATION

Let us add nodes depth-wise and keep track of the number of good tuples (u, v, c) which generate a strip.

Lemma 1: A strip can be generated only when the edge added from a node to its ancestor.
Proof: Let’s assume a strip is generated by connecting two nodes A and B where the lowest common ancestor of A and B is C. Now, consider both children of node C. They must lie on the strip, and the edges connecting them to C are of the same color and are adjacent. This contradicts with our definition of the strip. Hence, a strip can only be generated when a node is connected to its ancestor.

Lemma 2: Node A and its ancestor node B form a strip if and only if A and B have an odd number of edges between them.
Proof: Let’s assume the distance between A and B is even. This way, the edge connecting A to its parent and the edge connecting child of B to B have the opposite color. Hence, we cannot choose any valid color for the new edge without violating strip property.

The above two lemmas give us all the information we need to count the number of good tuples (u, v, c) which generates a strip.

Consider all nodes at depth d. Say there are P such nodes, C_0 denote the number of ancestors at even depth and C_1 denote number of ancestors at odd depth. The number of valid pairs increases by 2*C_1 if the current depth is even, otherwise by 2*C_0. For each pair of nodes, the color is automatically decided. The 2 factor appears since (u, v) is different from (v, u)

The total number of ways to choose tuples is 2*N*(N-1) where N is the number of nodes. Take care of the modulo.

We can also precompute the answer in advance since it only depends upon depth D

# TIME COMPLEXITY

The time complexity is O(D) per test case if not precomputing.

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>
using namespace std;
int t, cs;
typedef long long ll;
const ll mod   = 1e9+7 ;
const int maxn = 1e5+7 ;
ll H;
ll odd;
ll evn;
ll twoPower;

ll bmod(ll x, ll n){
if(n == 0 ) return 1;
if(n == 1 ) return x%mod ;

ll ret = bmod(x, n/2);
ret = (ret * ret) % mod ;
if(n%2) ret = (ret * x) % mod ;
return ret ;
}

ll invMod(ll x){
return bmod(x, mod-2);
}
int main(){
twoPower = 1;
for(int i = 1 ; i < maxn ; i++ ) twoPower[i] = (2*twoPower[i-1]) % mod ;
cin >> t;
while(cs< t){
cs++;
cin >> H ;
odd[H] = 0;
evn[H] = 1;

ll stripCandidate = 0 ;
for(int i = H-1 ; i >= 0 ; i--){
odd[i] = (2 * evn[i+1]) % mod ;
evn[i] = (1 + 2 * odd[i+1]) % mod ;

stripCandidate += (odd[i] * twoPower[i]) % mod ;
stripCandidate %= mod ;
}
ll totalCandidate = twoPower[H+1] - 2 ;
totalCandidate *= (totalCandidate + 1 ) ;
totalCandidate %= mod ;

ll ans = stripCandidate * invMod(totalCandidate) ;
ans %= mod ;
printf("%lld\n", ans);

}

return 0 ;
}
``````
Tester's Solution
``````//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
#define int ll

int getpow(int a,int b){
int ans=1;
while(b){
if(b%2){
ans*=a;
ans%=mod;
}
a*=a;
a%=mod;
b/=2;
}
return ans;
}

int two,gg;
signed main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int i;
two=1;
f(i,1,123456){
two[i]=two[i-1]*2;
two[i]%=mod;
}
gg=0;
f(i,2,123456){
gg[i]=two[i-1]*(i/2);
gg[i]+=gg[i-1];
gg[i]%=mod;
}
int t;
cin>>t;
while(t--){
int h;
cin>>h;
h++;
int den=two[h]-1;
den*=(den-1);
den%=mod;
int num=gg[h];
den=getpow(den,mod-2);
num*=den;
num%=mod;
cout<<num<<endl;
}
return 0;
}
``````
Editorialist's Solution
``````import java.util.*;
import java.io.*;
import java.text.*;
class STRPTRE{
//SOLUTION BEGIN
int mx = (int)1e5;
long[] ans;
long MOD = (long)1e9+7;
void pre() throws Exception{
ans = new long[1+mx];
long[] c = new long;//C -> No of nodes at even depth
long validPairs = 0, numberOfNodes = 1;
c = 1;//Root
long p = 1;
for(int d = 1; d <= mx; d++){
p = (p*2)%MOD;
int dep = d%2;
c[dep]++;

validPairs = (validPairs+p*c[dep^1])%MOD;
numberOfNodes = (numberOfNodes+p)%MOD;

long numerator = 2*validPairs;
long denominator = 2*((numberOfNodes*(numberOfNodes-1)));

ans[d] = (numerator*pow(denominator, MOD-2))%MOD;
}
}
long pow(long a, long p){
long o = 1;a%=MOD;
for(;p>0;p>>=1){
if((p&1)==1)o = (o*a)%MOD;
a = (a*a)%MOD;
}
return o;
}
void solve(int TC) throws Exception{
pn(ans[ni()]);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
void run() throws Exception{
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 STRPTRE().run();
}
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());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
``````

Feel free to share your approach. Suggestions are welcomed as always. 1 Like

In the setter’s solution, what does odd[i] and even[i] represent?

odd[i] - Number of nodes at odd distance like 1, 3, 5 … from current node.
even[i] - Number of nodes at even distance like 0, 2, 3, … from current node.
Only nodes at odd distance contribute to the ans.

My solution is getting correct answer in first subtask and getting WA on all 3 parts of second subtask can someone please point out the mistake. https://www.codechef.com/viewsolution/30839028

Don’t we need to make the P and Q co-prime to each other before using the modulo multiplicative inverse of Q ? Here P/Q is the probability. An answer will be highly appreciated.

Thanks!

1 Like

No.
Take Mod=1000000007.
Consider a fraction p/q where mod does not divide q. Consider your answer to be rp/rq where mod does not divide r.
rp(rq)^{p-2} = r^{p-1}pq^{p-2}. By fermats little theorem it is equal to pq^{p-2}. So you need not worry about making them coprime.

1 Like

Got it! Thanks a lot!

I have a doubt above the denominator thing, how is it possible to take inverse mod of a very very large number of it is not in the form of a^x.

I tried with a similar approach but idk why i’m getting WA, my approach was to precompute the eventSpace array, which denotes the no. of favorable outcomes, by:

`eventSpace[i] = eventSpace[i-1] + i*pow(2, i), where i = depth of the tree & i>1`

Can anyone help me with this ?!
my code: CodeChef: Practical coding for everyone