PERMSUBSEQ - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: anky_301
Testers: wuhudsm, satyam_343
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given an array A of size N, count the number of its subsequences that are permutations.

EXPLANATION:

Let’s count permutations of length 1, 2, 3, \ldots, N separately and add them up.

For a permutation of length K, we need to:

  • Choose exactly one 1
  • Choose exactly one 2
  • Choose exactly one 3
    \vdots
  • Choose exactly one K

There are no further restrictions, since the order of the chosen elements doesn’t matter.

In particular, if there are \text{freq}[i] occurrences of element i in the array, then the number of ways to do the above is simply \text{freq}[1] \times \text{freq}[2] \times \text{freq}[3] \times \ldots \times \text{freq}[K] = \prod_{i=1}^K \text{freq}[i].

Adding this up for all K, our final answer is thus

\sum_{K=1}^N \left(\prod_{i=1}^K \text{freq}[i]\right)

After computing the frequency array, this value is easy to compute in \mathcal{O}(N^2) time.

To optimize it, note that that we’re essentially taking prefix products of the \text{freq} array, and all of those can be computed in \mathcal{O}(N) time total once \text{freq} is known, thus solving the problem in \mathcal{O}(N).

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Setter's code (Python) 
for test_cases in range(int(input())):
    n = int(input())
    l = list(map(int , input().split()))
    m = 1000000007
    d = {}
    for i in l:
        if i in d:
            d[i]+=1
        else:
            d[i] = 1
    x = 1
    c = 0
    p = 1
    while (x in d) and d[x]>0:
        cur = ((p%m )*(d[x]%m))%m
        c += cur
        p = cur
        c = c%m
        x+=1
    print(c)
Tester's code (C++) 
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=1000000007;
const ll  INF=2147483647;
int T,n;
ll  ans,cur;
int cnt[N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) cnt[i]=0;
		for(int i=1;i<=n;i++)
		{
			int t;
			scanf("%d",&t);
			if(t<=n) cnt[t]++; 
		} 
		ans=0;cur=1;
		for(int i=1;i<=n;i++) cur=(cur*cnt[i])%TMD,ans=(ans+cur)%TMD;
		printf("%lld\n",ans);
	}
	
	return 0;
}
Editorialist's code (Python) 
mod = 10**9 + 7
for _ in range(int(input())):
    n = int(input())
    freq = [0]*(n+1)
    for x in map(int, input().split()):
        if x <= n: freq[x] += 1
    cur, ans = 1, 0
    for i in range(1, n+1):
        cur = (cur * freq[i]) % mod
        ans += cur
    print(ans % mod)
3

my approch and please I need feedback on this too on problem Permutation Subsequence
So what i did is counted there frequency
for example lets take first test case 1 2 3 2 4 → freq in sorted manner is 1 2 1 1
so all elements difference are equal to 1 or zero right
so what i did i simply outputed sum = 1 + 21 + 211 + 2111 = 1 + 2 + 2 + 2 = 7
lets take another array with elements difference are equal to 1 or zero
elements : 1 2 2 3 3 4
similarly there ans will be like i explained before
but if there is diffrence between element is greater than 1
i initialize flag variable upto that element and iterate over it
like ill just share the code and please tell me why its giving me WA on second test cases and so one

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 1000000007;

int main() {
int t;
cin>>t;
while(t–)
{
ll n;
cin>>n;
ll arr[n];
map<ll,ll>mp;
vectorv2;
ll temp[n];
ll index = -1;
ll addition = 0;
ll index2 = 0;
for(ll i = 0;i<n;i++){
cin>>arr[i];
temp[i] = arr[i];
mp[arr[i]]++;
}
sort(temp, temp+n);
for(auto x : mp){
v2.push_back(x.second);
}
for(ll i = 1;i<n;i++){
if(abs(temp[i] - temp[i-1]) > 1){
index = i;
break;
}
}
// sort(v2.begin(),v2.end());
if(index == -1){
ll product1 = 1;
ll sum1 = 0;
for(ll i = 0;i<v2.size();i++){
sum1+=v2[i] * product1;
sum1 %= MOD;
product1 *= v2[i];
product1 %= MOD;
}
cout<<sum1<<endl;
}else{
//cout<<index<<endl;
ll product2 = 1;
ll sum2 = 0;
for(ll i = 0;i<index;i++){
sum2+=v2[i] * product2;
sum2 %= MOD;
product2 *= v2[i];
product2 %= MOD;
}
cout<<sum2<<endl;
}

}
return 0;

}


getting WA what should i do
4

I was thinking this above question could have been much better if we had to count unique permutation subsequences.