CHEFINSQ - Editorial

editorial
, , , ,
65

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

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:

67

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

1 Like
68

Thank you so much bro… Your explanation is fantastic.

1 Like
69

You are welcome!

1 Like
70

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?

71

No :slight_smile:

Impossible to say without seeing your code - please either paste your formatted code or link to your submission :slight_smile:

1 Like
72

This is the link of unaccepted one CodeChef: Practical coding for everyone
And this is the solution of accepted one CodeChef: Practical coding for everyone

Btw thanks for reply :blush:

1 Like
73

Here, you’re not clearing arr between testcases, so it just keeps getting longer and longer.

Move the

	vector<int> arr;

from line 13 to (say) line 23, and it should work, I think.

1 Like
74

Thanks dear!
Again a silly mistake.

1 Like
75

My Solution:

#include
#include
#include
/**

  • Represents a sequence.
    /
    class Sequence {
    std::vector seq;
    public:
    Sequence(std::vector);
    Sequence() {};
    ///Returns all subsequences of seq as a vector of vectors
    std::vector<std::vector> subsequences();
    ///Returns all subsequences with size length of seq as a vector of vectors
    std::vector<std::vector> subsequences(int length);
    };
    /    *
  • Represents a single test case.
    */
    class TestCase {
    int N, K;
    Sequence A;
    public:
    TestCase() {}
    TestCase(int seq_size, int interesting_seq_size, Sequence);
    void test();
    };

///Constructor for Sequence
Sequence::Sequence(std::vector sequence) : seq(sequence) {}

std::vector<std::vector> Sequence::subsequences()
{
int subseq_count = pow(2, seq.size());
std::vector<std::vector> subseq;
for(int i = 0; i < subseq_count; i++)
{
std::vector temp;
for(int j = 0; j < seq.size(); j++)
{
if(i & (1 << j))
{
temp.push_back(seq[j]);
}
}
subseq.push_back(temp);
}
return subseq;
}

std::vector<std::vector> Sequence::subsequences(int length)
{

std::vector<std::vector<int>> sub_seqs = subsequences();
std::vector<std::vector<int>> result;
for(std::vector<int> sub_seq : sub_seqs)
{
    if(sub_seq.size() == length) result.push_back(sub_seq);
}
return result;

}
///Constructor for TestCase
TestCase::TestCase(int seq_size, int interesting_seq_size, Sequence sequence)
{
if(interesting_seq_size < 1 || interesting_seq_size > seq_size || seq_size > 20)
{
std::cerr << “N or K constraint violated. \n Allowed: N[1-20], K [1-N]”;
throw std::exception();
}
N = seq_size;
K = interesting_seq_size;
A = sequence;
}
void TestCase::test()
{
//Get all subsequences with length K of Sequence A for the current test case
std::vector<std::vector> int_seqs = A.subsequences(K);

//Get the sum of each sequence with length K
std::vector<int> int_seq_sums;
for(std::vector<int> int_seq : int_seqs)
{
    int seq_sum = 0;
    for(int n : int_seq)
    {
        seq_sum += n;
    }
    int_seq_sums.push_back(seq_sum);
}
//Get the minimum value from sums
int min = int_seq_sums[0];
for(int sum : int_seq_sums)
{
    if(sum < min) min = sum;
}

 
int final_count = 0;
//If the sum of the sequence is min, increment count
for(int i = 0; i < int_seq_sums.size(); i++)
{
    if(int_seq_sums[i] == min) final_count++;
}
//Print Count
std::cout << std::endl << final_count;

}
int main()
{
int test_case_count_T;
int interesting_seq_size_K;
int seq_size_N;

std::cin >> test_case_count_T;
if(test_case_count_T < 1 || test_case_count_T > 10)
{
    std::cerr << "Bad value for test case: " << test_case_count_T << "\n Allowed[1-10]";
    throw std::exception();
}
TestCase* tc = new TestCase[test_case_count_T];
for(int i = 0; i < test_case_count_T; i++)
{
    std::cin >> seq_size_N >> interesting_seq_size_K;
    std::vector<int> sequence_A;
    for(int j = 0; j < seq_size_N; j++)
    {
        int num;
        std::cin >> num;
        if(num < 1 || num > 100)
        {
            std::cerr << "Bad value for sequence: " << num << "\nAllowed[1-100]";
        }
        sequence_A.push_back(num);
    }
    tc[i] = TestCase(seq_size_N, interesting_seq_size_K, Sequence(sequence_A));
    tc[i].test();
}

delete[] tc;

}

76

i have gone through a different approach of taking all the possible sub set and counting there sum and storing it in vector after i have sorted the vector and then counted the minimum sum frequency;
#include<bits/stdc++.h>
using namespace std;
int main(){
int t,cnt=0;
cin>>t;
int l=0;
vectorv;
while(t–){
int n,k,minn=0,count=0;
cin>>n>>k;
int a[n];
int n1=(1<<n)-1;
for(int i=0;i<n;i++){
cin>>a[i];
}

for(int i=0;i<=n1;i++){
	int temp=i,j=0,count=0;;
	while(temp>0){
		count+=(temp&1);
		temp=temp>>1;
			} temp=i;
			if(k>n)
			k=n;
			if(count==k){
				l++;
				while(temp>0){
					if(temp&1){
					//	cout<<a[j];
					minn+=a[j];}
					j++;
					temp=temp>>1;	
					}
					v.push_back(minn);

				}  minn=0;
			}
}cnt=0;
sort(v.begin(),v.end());
for(auto c:v){
	if(c==v[0]){
		cnt++;
	}
}
cout<<cnt<<endl;

return 0;
}

77

/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby,
C#, VB, Perl, Swift, Prolog, Javascript, Pascal, HTML, CSS, JS
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <stdio.h>
#include <math.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#define M 1000000007
long long int a[60];
long long int combination (long long int a,long long int b);
int main()
{
long long int t,n,k,i,count,result;
scanf("%lli",&t);
while(t–){
count=0;
scanf("%lli %lli",&n,&k);
for(i=0;i<n;i++)
scanf("%lli",&a[i]);
mergeSort(a,0,n-1);
i=0;
while(a[k-1]==a[k+i]){
count++;
i++;
}
count=count+k;
result=combination(count,k);
//for(i=0;i<n;i++)
// printf("%lli “,a[i]);
//printf(”\n");
printf("%lli\n",result);
}
return 0;
}
void merge(long long int arr[], long long int l, long long int m,long long int r)
{
long long int i, j, k;
long long int n1 = m - l + 1;
long long int n2 = r - m;

/* create temp arrays */
long long int L[n1], R[n2]; 

/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++) 
    L[i] = arr[l + i]; 
for (j = 0; j < n2; j++) 
    R[j] = arr[m + 1+ j]; 

/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray 
j = 0; // Initial index of second subarray 
k = l; // Initial index of merged subarray 
while (i < n1 && j < n2) 
{ 
    if (L[i] <= R[j]) 
    { 
        arr[k] = L[i]; 
        i++; 
    } 
    else
    { 
        arr[k] = R[j]; 
        j++; 
    } 
    k++; 
} 

/* Copy the remaining elements of L[], if there 
   are any */
while (i < n1) 
{ 
    arr[k] = L[i]; 
    i++; 
    k++; 
} 

/* Copy the remaining elements of R[], if there 
   are any */
while (j < n2) 
{ 
    arr[k] = R[j]; 
    j++; 
    k++; 
}

}

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(long long int arr[], long long int l, long long int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
long long int m = l+(r-l)/2;

    // Sort first and second halves 
    mergeSort(arr, l, m); 
    mergeSort(arr, m+1, r); 

    merge(arr, l, m, r); 
}

}
long long int combination (long long int a,long long int b){
if(b==0)
return 1;
if(b==a)
return 1;
return combination(a-1,b-1)+ combination(a-1,b);
}
whats the problem in this code

78

@div_bargali
no bcoz cnt(Z) is total number of times it occurs nd Y is no. of times it occurs in length of k.
so u can choose any Y no. of Z.

82

@twishabansal If you want to post your code without the forum software mangling it, see here or (better!) link to your submission (you can find the list of your submissions for this Problem here) :slight_smile:

2 Likes
83

Thank you!

1 Like
84

What’s the error in this?

d = {0:1}
def fact(n):
    if n not in d:
        d[n] = fact(n-1)*n
    return d[n]    

t = int(input())
for i in range(t):
    c = 0
    n,k = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    z = A[k-1]
    r = A.count(z)
    y = k - A[:k].count(z)
    print(int(fact(r)/(fact(y)*fact(r-y))))
85

Try running it with this randomly-chosen testcase; it should give you a runtime error with a helpful message:

1
20 11
25 29 55 48 42 31 46 2 20 8 13 12 50 30 24 15 41 5 19 55
2 Likes
86 
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static double factorial(int n)
	{
		double f=1;
		for(int i=n;i>=1;i--)
		{
			f=f*i;
		}
		return f;
	}

	public static void main(String[] args) throws Exception
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int t=Integer.parseInt(br.readLine());
		while(t-->0)
		{
			String s1[]=br.readLine().trim().split(" ");
			int n=Integer.parseInt(s1[0]);
			int k=Integer.parseInt(s1[1]);
			String s2[]=br.readLine().trim().split(" ");
			int a[]=new int[s2.length];
			for(int i=0;i<s2.length;i++)
				a[i]=Integer.parseInt(s2[i]); 
			Arrays.sort(a);
			int c1=0,c2=0;
			for(int i=0;i<k;i++)
			{
				if(a[i]==a[k-1])
					c1++;
			}
			c2=c1;
			for(int i=k;i<n;i++)
			{
				if(a[i]==a[k-1])
					c2++;
			}
			double c2f=factorial(c2);
			double c1f=factorial(c1);
			double cm=factorial(c2-c1);
			System.out.println((long)(c2f/(c1f*cm)));
			
		}
		
	}
}

Task 3,4 and 6 IN SUBTASK 2 IT IS SHOWING WRONG ANSWER
PLEASE HELP TO FIND MISTAKES IN CODE

87

nice…