CHEFINSQ - Editorial

If Batman and Spiderman had 2 injuries each, and we had to choose 5 heroes then what?
Would the answer be 3c2?

No. Batman and Superman have 2 injuries each and Spidey, Thor, Iron, Aqua have 4 injuries each. We have to choose 5 heroes.
Batman and Spiderman are automatically chosen since they have least injuries.
We are now left with four eligible heroes and we have to choose three more. That is 4C3.

NcR means we are selecting R elements from a set of N elements.

This will help you a lot : Chef and Interesting Subsequences - CHEFINSQ || September long challenge 2019 | programming - YouTube
Happy Coding :slight_smile:

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

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[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 - #52 by nik_united
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