PROBLEM LINK:
Practice
Contest
Video Editorial
Setter: Sawarnik
Tester: Yash Chandnani
Editorialist: Ishmeet Singh Saggu
DIFFICULTY:
Easy
PREREQUISITES:
Combinatorics, Binary Exponentiation, Modular Inverse.
PROBLEM:
You have to make a graph with N vertices and M edges. The graph follows the condition :
- For each vertex from i, where 2 \leq i \leq N, A_i is defined such that the shortest path between node 1 and i is A_i and there is no other path with the same length as the shortest path.
EXPLANATION:
The first observation is that as there exists a path between node 1 and other nodes with length A_i so the graph is connected. So first let us consider N-1 edges and try to make all possible trees (connected graph with N nodes and N-1 edges is called a tree) following the condition specified in the problem.
Now note, if a node X has a path from node 1 of length A_X then it should be connected to a node with a node whose length from node 1 is A_x-1. (Using this condition you have to handle the test cases where there is no node which has the shortest path of length L and has nodes with length L+1 or L+2 or L+3 ... in that case the answer will be 0). So we will add nodes in the increasing order of length of the shortest path i.e. first we will compute the ways to add nodes with the length of the shortest path 1, then 2 then 3 … soon. You can compute the number of ways in the following manner.
- There is only 1 node whose shortest path length is 0 which is the node 1 itself.
- We will initialize our answer variable with 1 as there is only 1 way to put node 1.
- Now suppose there are num_{L-1} nodes with shortest path length equal to L-1. Then the number of ways to add the node with shortest path length =L will be num_{L-1} as I can connect this node with any one of the num_{L-1} nodes(
that's why you have to add nodes in increasing order of there shortest path length) and we will multiply num_{L-1} with our answer variable. - In this way you can compute the number way to add N-1 edges to the graph.
Now we will try to add remaining edges to the graph. You will note one thing that is the problem statement it is mentioned that shortest path between node 1 and node i is unique and all other paths are of greater length. If you rephrase this condition it means that you can only add the remaining edges only between nodes that have the same shortest path length.(Why? because suppose if you add an edge between nodes with shortest path length L and L+1 then the node which already has the shortest path with length L+1 will now have 2 shortest path which violates the uniqueness condition and if you add an edge between nodes of shortest path length L and L+x where x > 1, then the node with the shortest path of length L+x will have a new shorter path of length L+1, again violating the condition). Now to further compute the answer we will compute the number of ways to form a pair of nodes that are there such that both nodes of the pair has same length. This can be done by adding together N \choose 2(number of ways to choose 2 objects out of N objects) for all the lengths of the shortest path.
long long node_pairs = 0;
for(int i = 1; i <= N-1; i ++) {
long long count = shortest_path_length[i].size();
node_pairs += ((count * (count-1)) / 2);
}
Firstly let us handle the corner test case where number of pairs is less than the number of extra edges i.e. M-(N-1) > numOfPairs then the answer will be 0 as we can’t add multiple edges between same pair. Otherwise, the number of ways to add these M-(N-1) edges will be numOfPairs \choose M-(N-1). To compute its modulo you will need the knowledge of modular inverse. And we will multiply it with our answer variable to get the final answer. Now you might think that the magnitude of numOfPairs can be quite large and to compute its factorial will result in TLE. so it can be computed efficiently as
- let quantity M-(N-1) = X
- numOfPairs \choose M-(N-1) = \frac{numOfPairs!}{(numOfPairs-X)! * (X)!}
- numOfPairs \choose M-(N-1) = \frac{numOfPairs!}{(numOfPairs-X)!} * \frac{1}{X!}
- \frac{numOfPairs!}{(numOfPairs-X)!} = ((numOfPair-X+1) * (numOfPair-X+2) \dots * (numOfPairs)). It will have M-(N-1) number of terms which can be computed in timelimit.(don’t forget to do modulo when you are multiplying else will result in overflow).
- \frac{1}{X!} % mod can be computed using modular inverse.
TIME COMPLEXITY:
- Time complexity per test case is O(N+M).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const int mod = 1e9 + 7;
const int mxn = 2e5;
int power (int a, int b)
{
int res = 1;
while (b > 0) {
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int ncr (int e, int m)
{
int x = 1;
FOR (i, 1, m) x = x*i % mod;
x = power(x, mod - 2);
FORD (i, e, e - m + 1) x = x*i % mod;
return x;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
m -= n - 1;
int a[n + 1], freq[n] = {1};
FOR (i, 2, n) cin >> a[i], freq[a[i]]++;
int ans = 1;
FOR (i, 2, n) ans = ans * freq[a[i] - 1] % mod;
int edges = 0;
FOR (i, 1, n - 1) edges += freq[i]*(freq[i] - 1)/2;
if (edges < m) {cout << 0 << endl; continue;}
ans = ans * ncr(edges, m) % mod;
cout << ans << endl;
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int i = a; i <= (n); ++i)
#define repD(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
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||g==EOF){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
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,' ');
}
ll inv[2000009];
const ll mod = 1000000007; // faster if const
void pre(){
inv[0]=inv[1]=1;
repA(i,2,2000000){
inv[i] = mod-(mod/i)*inv[mod%i]%mod;
}
repA(i,2,2000000){
inv[i]=inv[i-1]*inv[i]%mod;
}
}
ll sumn=0,summ=0;
ll modpow(ll a, ll e) {
if (e == 0) return 1;
ll x = modpow(a * a % mod, e >> 1);
return e & 1 ? x * a % mod : x;
}
ll C(ll n,int r){
if(n<0||r>n) return 0;
ll ans = 1;
repA(i,1,r){
ans=ans*((n+1-i)%mod)%mod;
}
return ans*inv[r]%mod;
}
void solve(){
int n=readIntSp(2,1e5);
int m=readIntLn(n-1,min(200000ll,1ll*n*(n-1)/2));
sumn+=n,summ+=m;
vi cnt(n,0);
rep(i,n-2){
int x = readIntSp(1,n-1);
cnt[x]++;
}
rep(i,1){
int x = readIntLn(1,n-1);
cnt[x]++;
}
cnt[0]++;
int tot = 1;
ll fns=1,z=0;
repA(i,1,n-1){
tot+=cnt[i];
fns=fns*modpow(cnt[i-1],cnt[i])%mod;
z += 1ll*cnt[i]*(cnt[i]-1)/2;
if(tot==n) break;
}
fns=fns*C(z,m-n+1)%mod;
cout<<fns<<'\n';
}
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
pre();
int n=readIntLn(1,1000);
rep(i,n) solve();
assert(getchar()==EOF);
assert(sumn<=200000);
assert(summ<=200000);
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
long long MOD = 1e9+7;
long long BinaryExponentiation(long long num, long long raise, long long modulo) {
long long result = 1;
while(raise > 0) {
if(raise & 1) result = (result * num) % modulo;
num = (num * num) % modulo;
raise = (raise >> 1);
}
return result;
}
void solveTestCase() {
int N, M;
cin >> N >> M;
vector<vector<long long>> distance(N); // distance[i][j], represent a node which is at distance i from 1.
distance[0].push_back(1); // as node 1 is at 0 distance from itself.
for(int i = 2; i <= N; i ++) {
int node_dist; // A[i]
cin >> node_dist;
distance[node_dist].push_back(i);
}
bool pos = true;
long long ans = 1;
// first we will try to compute the number of ways to make the tree with the condition of A[i].
for(int i = 1; i <= N-1; i ++) {
if(distance[i].size()) {
ans = (ans * BinaryExponentiation(distance[i-1].size(), distance[i].size(), MOD));
}
if((distance[i].size()) && (!distance[i-1].size())) {
// if there are some nodes at distance i and there are no node at distance i-1 which is not possible.
pos = false;
}
ans = (ans % MOD);
}
if(!pos) {
cout << 0 << endl;
return;
}
// Now note, for the remaining edges we can only add those only between nodes which have same distance from the node 1, to satisfy the condition in the question.
long long node_pairs = 0;
for(int i = 1; i <= N-1; i ++) {
long long count = distance[i].size();
node_pairs += ((count * (count-1)) / 2);
}
// Computing nCr, where n = node_pairs and r = M-(N-1).
if(M-(N-1)) {
M -= (N-1);
// We will compute the ways to choose remaining edges.
if(node_pairs < M) {
ans = 0;
}
else {
long long ways;
long long num = 1, den = 1;
for(long long i = node_pairs-M+1; i <= node_pairs; i ++) {
num *= i;
num %= MOD;
}
for(long long i = 1; i <= M; i ++) {
den *= i;
den %= MOD;
}
ways = num * BinaryExponentiation(den, MOD-2, MOD); // ways = num/den, where 1/den = BinaryExponentiation(den, MOD-2, MOD), inverse modulo.
ways %= MOD;
ans = (ans * ways) % MOD;
}
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int testCase;
cin >> testCase;
for(int i = 1; i <= testCase; i ++) {
solveTestCase();
}
return 0;
}
Video Editorial
Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. 
