PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: saad muhammed junayed
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
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[100005];
ll evn[100005];
ll twoPower[100005];
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[0] = 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[123456],gg[123456];
signed main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int i;
two[0]=1;
f(i,1,123456){
two[i]=two[i-1]*2;
two[i]%=mod;
}
gg[1]=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[2];//C[0] -> No of nodes at even depth
long validPairs = 0, numberOfNodes = 1;
c[0] = 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;
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 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());}
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. 