CHEFINSQ - Editorial

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[101]={0};
int c[101]={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;
}

}

Reply

int main(void) {
	int t,l;
	long double fact[51]={1};
	scanf("%d",&t);
	for(l=1;l<=50;l++)
	    fact[l]=l*fact[l-1];
	while(t--)
	{
	    int i,n,k,a[50],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],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[30]);
	    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][0] = 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 :stuck_out_tongue:

As a hint:

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

1 Like

Sorry, forgot about you :slight_smile:

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 :stuck_out_tongue: )

Please format your code, or link to a solution :slight_smile:

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.
Please help by explaining.

EDIT :slight_smile:
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 :slight_smile:

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 eraseing 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. :frowning:


#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[50];
    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 :wink:

Thanks bro. How foolish of me xD. I was thinking only for a pair of two case.

1 Like

Thank you so much bro… Your explanation is fantastic.

1 Like

You are welcome!

1 Like

Is it necessary to scan using scanf instead of cin and print using printf instead of cout? If yes why? If not so, then why it is wrong answer each time?