CHEFINSQ - Editorial

harshadeep97 · September 25, 2019, 7:23pm

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

nik_united · September 27, 2019, 1:14pm

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

martin22 · September 27, 2019, 3:39pm

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?

ssjgz · September 27, 2019, 4:24pm

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

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?

ssjgz · September 27, 2019, 4:50pm

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 )

ssjgz · September 27, 2019, 5:15pm

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

mohitthorat · September 27, 2019, 5:21pm

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

adist98 · October 7, 2019, 11:12am

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
I got it now. Even if the values of elements are same they are considered distinct.

anon61187231 · October 12, 2019, 5:43pm

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

ssjgz · October 12, 2019, 6:11pm

Really cool use of constexpr

nik_united · October 18, 2019, 5:14pm

I rally want to know the reason for this - CHEFINSQ - Editorial - #52 by nik_united
PLLLEEEEAASSS HEEELLPPP

divine183 · October 25, 2019, 7:09pm

``#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

ssjgz · October 25, 2019, 7:19pm

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).

trushant_0123 · November 1, 2019, 4:03pm

Well done code

yato · November 9, 2019, 3:34pm

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[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;
}

ssjgz · November 9, 2019, 3:38pm

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

yato · November 9, 2019, 3:58pm

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

shrii_06 · November 18, 2019, 2:42pm

Thank you so much bro… Your explanation is fantastic.

dardev · November 19, 2019, 7:48am

You are welcome!

anon45717441 · February 3, 2020, 3:39pm

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?