 # CHEFINSQ - Editorial

https://www.codechef.com/submit/CHEFINSQ
pls help me with the code!

lmao … my man… you got my feelings…XD

That’s not a link to your solution https://www.codechef.com/viewsolution/26781714
My one test case is getting wrong? What is the problem with my code?

Can anyone explain why all test cases are not passed by the below mention solution.I tried my best to find the bug but failed.Below is my solution.

#include <bits/stdc++.h>

using namespace std;
long long int fact(int d,int f){
long long int res,i;
res=1;
for(i=d+1;i<=f;i++){
res=res*i;
}
return res;
}

int main() {
int t;
int k,n,i,j,ldi,lfreq;

``````long long int sum=0;
long long int ncr,d,max,min,temp;

cin>>t;
while(t--){

cin>>n>>k;
int a[n]={0};
int b={0};
int c={0};
int r=0;

for(i=0;i<n;i++){
cin>>a[i];
j=a[i];
b[j]++;
}
sort(a,a+n);
ldi=a[k-1];
lfreq=b[ldi];
for(i=0;i<k;i++){
if(a[i]==ldi){
r++;
}
}
d=lfreq-r;

if(d>r){
max=d+1;
min=r;
}else{
max=r+1;
min=d;
}
i=0;
while(max<=lfreq){
c[i]=max;
max++;
i++;
}
temp=i;
for(j=2;j<=min;j++){
for(i=0;i<temp;i++){
if(c[i]%j==0){
c[i]=c[i]/j;
break;
}
}
}

ncr=1;
for(i=0;i<temp;i++){
ncr=c[i]*ncr;
}
cout<<ncr<<endl;
}
``````

}

``````int main(void) {
int t,l;
long double fact={1};
scanf("%d",&t);
for(l=1;l<=50;l++)
fact[l]=l*fact[l-1];
while(t--)
{
int i,n,k,a,j,np=0,rp=0;
long sum=0;
long double ans=0;
scanf("%d %d",&n,&k);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(&a,0,n-1);
i=k-1;
while(i>0 && a[i]==a[i-1])
i--;
rp=k-i;//i will be the starting pos of last unique number
i=k-1;
while(i<(n-1) && a[i]==a[i+1])
i++;
np=rp+(i-(k-1));
ans=fact[np]/(fact[rp]*fact[np-rp]);//calculate this
//printf("%.0Lf ",fact);
printf("%.0Lf\n",ans);
}
return 0;
}
``````

This is the code i tried. Now i know that using double will give precision errors in case of large factorials thus giving wrong factorial values, but to my surprise the solution got accepted for all cases. I want to know why this happened? I mean how the nCr formula produced correct answer even for wrong values of factorial

hi could you please explain why did you put this k-c2 in argument of fact function and m, m1 in fact what does it mean?

It fails for the testcase:

``````1
50 40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
``````

Edit:

This line is a little suspicious:

``````    c = 0;
``````

as is the “+ 1” in

``````cout<<c[counter+1][counte]<<endl;
``````

Edit2:

I have a fixed version of your code locally, but I’m not going to post it As a hint:

What should the value of `c` be? What does your program think it is?
Why are you adding `+ 1` to `counter`?

1 Like

Sorry, forgot about you Your solution also fails for the same testcase:

``````1
50 40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
``````

(although for different reasons )

Please format your code, or link to a solution Interestingly, your solution actually passes the testcase above, though it fails this one:

``````1
40 8
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
``````

Got AC thankyou!
https://www.codechef.com/submit/complete/26804289

1 Like

Do you think the proposed solution will work for an already sorted original sequence?
The above solution works just fine for a randomly distributed original sequence but I can’t seem to wrap my head around for the case when the original sequence is already sorted.

EDIT I got it now. Even if the values of elements are same they are considered distinct.

Hello

For fun, a solution :

• Using multiset<> data structure (sorted automatically).
• Pre-compile binomial coefficient (no compute at execution).

https://www.codechef.com/viewsolution/27305064

3 Likes

Really cool use of `constexpr` 3 Likes

I rally want to know the reason for this - CHEFINSQ - Editorial
PLLLEEEEAASSS HEEELLPPP

````````#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
int main(){int T;cin>>T;
for(int z=0;z<T;z++){
int N,K,x;
cin>>N>>K;vector<int> v1,v2;
for(int i=0;i<N;i++){
cin>>x;v1.push_back(x);v2.push_back(x);
}
sort(v2.begin(),v2.end());
vector<int>::iterator it=v1.begin();
while(it!=v1.end()){
if(*it>v2[K-1])
v1.erase(it);
else
it++;
}
x=0;it=v1.begin();
while(it!=v1.end()){
if((*it==v2[K-1])&&(it!=v1.end()-1)&&(*it>*(it+1)))
x++;
if((*it==v2[K-1])&&(it==v1.end()-1))
x++;
it++;

}
cout<<x<<endl;

`indent preformatted text by 4 spaces`
v1.clear();
}
return 0;}
``````

can anyone clear me whats wrong in this code,pls

One thing that’s wrong is that you are `erase`ing an iterator (thus invalidating it) and then continuing to use that iterator, which is Undefined Behaviour.

``````while(it!=v1.end()){
if(*it>v2[K-1])
v1.erase(it);
else
it++;
}
``````

should be

``````while(it!=v1.end()){
if(*it>v2[K-1])
it = v1.erase(it);
else
it++;
}
``````

After fixing that, one random testcase that fails is

``````1
19 4
33 24 8 47 4 10 38 35 45 49 2 33 40 33 28 4 30 1 51
``````

(the answer should be `1`).

Edit:

Much more striking (and much less random) example:

``````1
10 5
3 3 3 3 3 3 3 3 3 3
``````

(the answer should be `252`).

2 Likes

Well done code

1 Like

Although I checked with all possible cases I can think of, I still get the Wrong Answer with this code. Please help me to look for its mistakes. ``````
#include<stdio.h>

int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}

int main(void)
{
int T,N,K;
int A;
int i,f,j,l;
int count,ans;
scanf("%d",&T);
for ( i = 0 ; i < T ; i++)
{
scanf("%d %d",&N,&K);
for ( f = 0 ; f < N ; f++)
{
scanf("%d",&A[f]);
}
qsort (A, N, sizeof(int), compare);
count = 1;
for ( j = 0 ; j < N - 1 ; j++)
{
if ( A[j]== A[j+1])
{
count++;
}
else
{
break;
}
}
if ( count <= K)
{
ans = 1;
}
else
{
ans = 0;
for ( l = 0 ; l < count ; l++)
{
ans += l;
}
}
printf("%d\n",ans);
}
return 0;
}

``````

Consider the testcase:

``````1
4 3
1 1 1 1
``````

(the answer should be `4`).

Edit:

Also, see my post a couple of posts above yours 