https://www.codechef.com/viewsolution/36725579
Here is my code, I tried everything but keep getting tle in the last subtask. Can anyone help me ,tell where to optimise further ?
i used bitmasking technique in finding all the subsequences and then i calculated max frequency number in all the subsequences but its passing only 1st test case of subtask1 can you tell what is wrong in my solution?
link to my solution
https://www.codechef.com/viewsolution/36804418
This is the cleanest the code and the first submission for the problem. It has O(n) space complexity.
This code look soo much like mine even the common naming scheme used like mod inverse and ncr ā¦ I hope I dont get I plag 
and I donāt even know this guy
Sureā¦
st is my Deque/queue with all distinct element present initially(sorted in reverse order)
d is my dictionary having count of all the element.
times is the array that store how many times i have taken each element.(initially all 0)
finalcount is the final ans that i will print
sum_till_now represent the total sum that we have store for each element (initially 1 for all the element present in st)
ans calculate the total case for the current case.
Idea:
if we want total no of all the cases where we choose k occurance of any element say P
(d[P]Ck) * (total Case where we have k or less occurrence of larger element)*(total case where we have strictly less than k occurrence of smaller element).
let array be {1,1,2,2,2,3,3,4} then st be like {4,3,2,1}
now for 4 if we take 1 occurrence : then ans = all cases *(1C1)
add this in sum_till_now[4] => if we take 0 or 1 occurance.
Remove 4 as it has only one occurrenceā¦(We never going to consider 2 occurrence of 4 )
Now for 3 if we consider 1 occurance: ans= (Total No. of cases of 4) *(2C1)
update sum_till_now.(Pop 3 and append at lastā¦because we need 2nd occurrence of 3 later.)
Do same for 2 and 1 for their 1st occurrenceā¦
now st after first occurrence of all ,{3,2,1}
and ans = (0 and 1occ of 4) * (0 and 1 occ of 3 ) * (0 and 1 occ of 2) * (0 and 1 occ of 1)
Now for 2 occurrence of 3
we Want (0 and 1 occ of 4) * (2 occ of 3) * (0 and 1 occ of 1 ) * (0 and 1 occ of 1).
so we need to divide ans by sum_till_now[3](which is 0 and 1 occ of 3).
and multiply ans by (2C2) .
Update sum_till_now respectively.
Take out pen and paper ā¦
Try to solve by urselfā¦
U will get thisā¦
Thanks
1 Like
I got the procedure you explained during contest
But i wasnt able to code it during contest.
Can you plzz explain how should i approach it in code.
Plzz explain in a algorithm form
I would be very thankful ā¦
Hey , I got the same logic during the contest itself but code was giving TLE at that time due to repitative calculation. I used some hashing technique to optimize those calculations. Now I am getting WA 
,can plaese review this code why I am code is giving wrong output . Here is my code>>
https://www.codechef.com/viewsolution/37005745
Thankyou !
I donāt know why I was getting wrong answer, even now!
can you provide any case where it fails, I made a bruteforce program and was getting correct answer, is there a problem with mod?
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD = 1000000007;
#define MX 500002
unsigned long long power(ll x, ll y)
{
unsigned long long res = 1;
x = x % MOD;
while (y > 0) {
if (y & 1)
res = (res * x) % MOD;
y = y >> 1; // y = y/2
x = (x * x) % MOD;
}
return res;
}
unsigned long long modInverse(ll n)
{
return power(n, MOD - 2);
}
unsigned long long NcR(ll n, ll r)
{
if (r == 0)
return 1;
unsigned long long fac[n + 1];
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = (fac[i - 1] * i) % MOD;
return (fac[n] * modInverse(fac[r]) % MOD * modInverse(fac[n - r]) % MOD) % MOD;
}
void solve(){
ll n;
cin>>n;
ll A[n+1];
for(int i=0;i<n;i++)
cin>>A[i];
ll Frq[n+1];
memset(Frq, 0 ,sizeof(Frq));
for(int i=0;i<n;i++)
Frq[A[i]]++;
ll res[n+1];
vector<ll> get[n+1];
for(ll i=1;i<=n;i++)
{
ll prev = 0;
get[i].push_back(0);
for(ll j=1;j<=Frq[i];j++){
ll nc = NcR(Frq[i], j)%MOD;
get[i].push_back( (prev + nc)%MOD);
prev += nc;
prev%=MOD;
}
}
// for(ll i=1;i<=n;i++)
// {
// for(auto x:get[i])
// cout<<x<<" + ";
// cout<<"\n";
// }
for(ll i=1;i<=n;i++)
{
ll prod;
ll rs = 0;
for(ll j = 1;j<= Frq[i];j++){
prod = NcR(Frq[i] , j)%MOD;
for(ll k = 0;k<=n;k++)
{
if(Frq[k]!=0)
{if(k < i){
ll add = 0;
add += get[k][min(j-1 , Frq[k])]%MOD;
add+=1LL;
prod *= add%MOD;
prod %=MOD;
}else if (k >i){
ll add = 0;
add += get[k][min(j , Frq[k])]%MOD;
add+=1LL;
prod *= add%MOD;
prod %=MOD;
}
}
}
rs += prod%MOD;
}
res[i] = rs%MOD;
}
for(ll i=1;i<=n;i++)
cout<<(res[i]%MOD)<<" ";
cout<<"\n";
}
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
test;
return 0;
}
Where am I going wrong for subtask 1, probably Modulo?
https://www.codechef.com/viewsolution/36854165
1 Like
say in your mentioned example if we are counting number of times 3 occurs two times ?
how are you maintaining number of elements less than 3 such that we should take only up to current choice-1 times ?
we need 3C2 * (3C0+3C1+3C2)^1 * (3C0+3C1)^1 * (4C0+4C1)^1
3C2 is for we know out of three 3ās we need 2.
(3C0+3C1+3C2)^1 we know there is one number 4 which can occur in such a way as we take up to 2 times from 3 fours still our answer will be 3 only.
(3C0+3C1)^1 we know there is 2 which should not occur two times out of 3 twoās as if it occurs two times then 2 will be the answer not 3 so we take up to 1 times
(4C0+4C1)^1 we know that out of 4 1ās we need only one occurrence as if we take 2 we know answer will be 1 and not 3
Excellent approach