PROBLEM LINK:
Practice - Hopscotch Tree Game
Contest: CTWJ2022 – [Come to Win the Coding Jallikattu]
Author: [ Meenaksshi S ](meenaksshi | CodeChef User Profile for Meenaksshi S | CodeChef)
Tester: [ Meenaksshi S ](meenaksshi | CodeChef User Profile for Meenaksshi S | CodeChef)
Editorialist: [ Meenaksshi S ](meenaksshi | CodeChef User Profile for Meenaksshi S | CodeChef)
DIFFICULTY:
MEDIUM
PREREQUISITES:
Math, Trees, Probability, BFS, Data Structures, Graphs, Mathematics, Algorithms, Graph Algos, Traversals
PROBLEM:
A Directed rooted tree is given. Hema is starting from the root node, it takes one second for her to go to any of the child nodes. Find the probability that Hema is on a given node K after a very long time. [Consider infinite time]
QUICK EXPLANATION:
After infinite time, Hema will be present on any of the leaf nodes only. So, the probability that Hema is present on any of the internal nodes will be 0.
\textbf{Algorithm}:
Create the adjacency list for all the nodes present in the tree and find the parent of each node. Starting from node K, find the product of the number of child nodes for each of its ancestors. Reciprocate this result and print the answer.
\textbf{Pseudo-code}:
ans = 1
node = k
while (node!=1)
{
node = par[node];
if (node == 1)
ans *= sizeof(adj[node]) // number of child nodes of root –> size of adj[node]
else
ans *= (sizeof(adj[node]) - 1)// number of child nodes–> size of adj[node]
// subtract 1 – because the parent of this node shouldn’t be considered.
}
print (1/ans)
EXPLANATION:
The nodes of a tree can be classified into 2 types. So, there are two cases:
\textbf{Case 1}: K is an internal node. In this case, print 0 as the answer. As time is infinite, Hema will never stop at a non-leaf node, it would’ve reached some leaf.
\textbf{Case 2}: K is a leaf node.
Here, we have to calculate the probability of choosing the ancestor of K at each level in the tree, and finally multiply all these probabilities to get the final result.
\textbf{Code}:
#include "bits/stdc++.h"
using namespace std;
#define endl '\n'
#define rep(i, a, b, inc) for(long long i = a; i < b; i += inc)
#define REP(i, n) rep(i, 0, n, 1)
#define pb push_back
typedef long long ll;
typedef long double ld;
vector<ll> adj[(ll)(1e6) + 1];
ll par[(ll)(1e6) + 1] = {0};
bool vis[(ll)(1e6) + 1];
void dfs(ll v)
{
vis[v] = 1;
for (auto u : adj[v])
{
if (!par[u])
par[u] = v;
if (!vis[u])
dfs(u);
}
}
ld solve(ll n)
{
ll k, u , v;
cin >> k;
REP(i, n - 1)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// Adjacency list stores all the neighbouring nodes of each of the nodes in the tree.
if (n == 1 && k == 1) return 1; // if there is only one node ( which is the root), Hema will stay on the same node after infinite time, hence the probability is 1.
if (adj[k].size() != 1 || k == 1) return 0; // Probability that Hema is present at the root node is 0 when the root has children.
dfs(1); // Perform dfs on the root node to find and store the parent of each node.
ll node = k, ans = 1;
while (node != 1) // starting from node k, traverse through each of its ancestors in the tree
{
node = par[node];
if (node == 1)
ans *= (adj[node].size());// number of child nodes of root –> size of adj[node]
else
ans *= (adj[node].size() - 1); )// number of child nodes –> size of adj[node]
// Subtract 1 - the parent of this node shouldn’t be considered.
}
return 1.0 / ans; // return the reciprocal of the product.
}
int main()
{
ld n, c;
cin >> n;
c = solve(n);
cout << fixed << setprecision(6) << c << endl; // round the answer to 6 decimal places
return 0;
}
SOLUTIONS:
Setter's Solution
n,k=map(int,input().split())
g=[[] for _ in range(n)]
p=[-1]*n
for _ in range(n-1):
u,v=map(int,input().split())
g[u-1].append(v-1)
g[v-1].append(u-1)
p[0],q=1,[0]
while len(q):
u=q.pop(0)
c=0
for v in g[u]:
c+=1 if p[v]==-1 else 0
for v in g[u]:
if p[v]==-1:
q.append(v)
p[v]=p[u]/c
if c>0:
p[u]=0
print(round(p[k-1],6))
Tester's Solution
def dfs(node,e,v,p,leaf):
v[node]=True
for i in e[node]:
if not v[i]:
p[i]=node
leaf[node]=False
dfs(i,e,v,p,leaf)
n,k=map(int,input().split())
e=[[]for i in range(n)]
for i in range(n-1):
u,v=map(int,input().split())
e[u-1].append(v-1)
e[v-1].append(u-1)
par=[-1 for i in range(n)]
vis=[False for i in range(n)]
leaf=[True for i in range(n)]
dfs(0,e,vis,par,leaf)
res=0
if leaf[k-1]:
node=par[k-1]
ans=1
while node!=-1:
if node==0:
ans=ans*(len(e[node]))
else:
ans=ans*(len(e[node])-1)
node=par[node]
res=1/ans
print('%.6f'%res)
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define endl '\n'
#define rep(i, a, b, inc) for(long long i = a; i < b; i += inc)
#define REP(i, n) rep(i, 0, n, 1)
#define pb push_back
typedef long long ll;
typedef long double ld;
vector<ll> adj[(ll)(1e6) + 1];
ll par[(ll)(1e6) + 1] = {0};
bool vis[(ll)(1e6) + 1];
void dfs(ll v)
{
vis[v] = 1;
for (auto u : adj[v])
{
if (!par[u])
par[u] = v;
if (!vis[u])
dfs(u);
}
}
ld solve(ll n)
{
ll k, u , v;
cin >> k;
REP(i, n - 1)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
if (n == 1 && k == 1) return 1;
if (adj[k].size() != 1 || k == 1) return 0;
dfs(1);
ll node = k, ans = 1;
while (node != 1)
{
node = par[node];
if (node == 1)
ans *= (adj[node].size());
else
ans *= (adj[node].size() - 1);
}
return 1.0 / ans;
}
int main()
{
ld n, c;
cin >> n;
c = solve(n);
cout << fixed << setprecision(6) << c << endl;
return 0;
}