CHEFINSQ - Editorial

[abhi123_ahuja]

can someone tell why i am getting WA for this code?

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t, k, j, i, t1, x, count, limit, rest, n, sum, sum1, ans, y, k1;
//cout<<"enter t ";
cin>>t;
while(t>0)
{
//cout<<"enter n and k ";
cin>>n>>k;

	int arr[n], count=0, limit=1;
	
	//cout<<"enter values"<<endl;
	for(i=0; i<n; i++)
	 cin>>arr[i];
	
	ans = 0;
	sort(arr, arr+n);
	for(i=0; i<k; i++)
	 ans = ans+arr[i];
	
	for(y=1; y<=k; y++)
	{
		for(i=0; i<=n-k; i++)
		{
			sum = 0;
			x=i;
			for(j=0; j<y; j++)
			{
				//cout<<"i: "<<i<<" x: "<<x<<endl;
				sum = sum+arr[x++];
			}
			 
			if(sum > ans)
			{
				//cout<<"count: "<<count<<" limit: "<<y<<" sum: "<<sum<<" OUTER BREAK"<<endl;
				break;
			}
			 
			rest = k-y;
			
			if(rest > 0)
			{
				t1 = y>1 ? x+1 : x;
				for(t1; t1<n; t1++)
				{
					x = t1;
					sum1 = sum;
					for(k1=0; k1<rest; k1++)
					{
						//cout<<"i: "<<i<<" x: "<<x<<endl;
						sum1 = sum1+arr[x++];
					}
					 
					if(sum1 == ans)
					{
						count++;
						//cout<<"count: "<<count<<" limit: "<<y<<" sum: "<<sum1<<" INNER"<<endl;
					}
					else
					{
						//cout<<"count: "<<count<<" limit: "<<y<<" sum: "<<sum1<<" INNER BREAK"<<endl;
						break;
					}
				}		
			}		 
		}		
	}
	cout<<count<<endl;
	
	t--;
}
return 0;

}

[div_bargali]

Let the maximum element among the KKK smallest elements of the array be ZZZ , and let the number of times it occurs among the KKK smallest elements of the array be YYY. Also, let cnt(i)cnt(i)cnt(i) indicate the number of times element iii occurs in the given array. Then the answer is (cnt(Z)Y)\binom{cnt(Z)}{Y}(Ycnt(Z)​)

I don’t understand. Wouldn’t the answer of (cnt(Z)Y)\binom{cnt(Z)}{Y}(Ycnt(Z)​) be equal to 1 each time? Since cnt(Z) = Y.

[batman7084]

can anyone explain the solution to me in more simple approach . Its hard to understand the problem solution just by some language…please help it can be very helpful…explain the above algorithm by an example

[dardev]

@batman7084
Let me simplify the problem statement for you.

You have seven fighters - Superman, Batman, Spiderman, Thor, Iron Man, Aquaman, Flash.

Unfortunately all your fighters are injured. Superman has 1 injury, Batman has 2 injuries, Spiderman, Thor, Iron, Aqua have 4 injuries each, and Flash has 7 injuries.

You have to select 4 fighters, the ONLY criteria is that they have the least number of injuries.

How many ways can you do it in?
Well, you HAVE to select Superman and Batman, that’s a no brainer since they have least injuries.
So you have two spots left and four fighters to choose from - Spiderman, Thor, Iron, Aqua have 4 injuries each. Flash cannot be selected since he has maximum injuries.

So you have to select 2 players from those 4. This can be done in 4c2 ways. This is ONE part of the problem. But there is a catch here…

How to solve 4c2. Well, we can rewrite it as 4!/2!.2! and solve it as 6. But the problem is that if we have to select 25 fighters from 50. It becomes 50c25. Which is 50!/(25!.25!). 50! is too large to store. So the solution is to use dynamic programming and pascal’s triangle to arrive at 50c25.
For this, we use the recursive principle nCr = (n-1)C(r-1) + (n-1)Cr

We start with DP[0][0] as 1.
DP[1][0] = 1 and DP[1][1] = 1.
Dp[2][0] = 1 and DP[2][2] = 1. DP[n][0] = 1 and DP[n][n] = 1. Here is the code block for that:

for(i=0;i<51;i++)
{
   DP[i][0] = 1;
   DP[i][i] = 1;    
}

Next we apply recursion+memoisation to get DP[2][1] = DP[1][0]+DP[1][1]; DP[3][1] = DP[2][0]+DP[2][1]; DP[3][2] = DP[2][1]+DP[2][2] etc. Here is the code block for that:

for(i=2;i<51;i++)
{
    for(j=1;j<i;j++)
    {
        DP[i][j] = DP[i-1][j-1] + DP[i-1][j]; 
    }
}

Here is my implementation: CodeChef: Practical coding for everyone
Let me know if something’s not clear.

[angelite]

Can Someone what is wrong in this code…as getting WA for all test cases

#include<bits/stdc++.h>
using namespace std;
int factorial(int n)
{
return (n==1 || n==0) ? 1: n * factorial(n - 1);
}
int main() {
int t;
cin>>t;
while(t>0)
{
int i,n,k,s,e;
cin>>n>>k;
if(k<=n)
{
int arr[n];
for(i=1;i<=n;i++)
{
cin>>arr[i];
}
sort(arr+1,arr+n);
int a=arr[k];
for(i=1;i<=k;i++)
{if(a==arr[i])
{s=i;break;}
}
for(i=n;i>0;i–)
{
if(a==arr[i])
{e=i;break;
}
}
int result=1;
if(s==e)
cout<<1<<endl;
else{
if(k==s)
cout<<e-s+1<<endl;
else{
int f=k-s+1;
int digit=e-s+1;
for(i=0;i<f;i++)
result=result*(digit-i);
cout<<(result)/factorial(f)<<endl;}
}

    }
    t--;
}
 return 0;

}

[syntaxhacker]

format code

[Tutorial] CoLoR format the Code!

Really quick tutorial for all forum members who dont know how to color format code like this which i learned from another site. just use 3 backticks ``` before and after the code and your code looks like this CPP : #include <iostream> using namespace std; int main() { for(int i=0 ; i < 10 ;++i) { cout << i <<" - hello world\n"; } return 0; } Python : # Python 3 program to find # factorial of given number def factor…

as if its getting wa for all cases means your logic is wrong.

[batman7084]

thank you man… i mean the way you explained me the problem is fabulous.

[dardev]

You are very welcome! Your name inspired the example, by the way!

[prakash_6605]

#include<bits/stdc++.h>
using namespace std
int minsub(int a[],int n,int k,int sum){
priority_queue p;
int c=0;
int s=0;
for(int i=0;i<=n-k;i++){
s=0;
int fix=a[i];
for(int j=i+1;j<n;j++){
if(p.size()<k-1){
s=s+a[j];
p.push(a[j]);
if(p.size()==k-1){

        if(s+fix==sum)
        { 
            c++;}
    }
    }
    else{
        
        if(p.top()>=a[j]){
           
            int t=p.top();
           
            p.pop();
            s=s-t;
            p.push(a[j]);
            s=s+a[j];
            if(s+fix==sum){

           
            c++;
            }
        }
    }
}

while(!p.empty()){
    p.pop();
}

}
return c;
}
int main(){
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
int a[55];
priority_queue pq;
for(int i=0;i<n;i++){
cin>>a[i];
pq.push(a[i]);
if(pq.size()>k)pq.pop();
}
int s=0;
while(!pq.empty()){
s=s+pq.top();
pq.pop();
}

cout<<minsub(a,n,k,s)<<endl;

}
}
What wrong on this code, first i have solved this problem using recursion(subtask 1 passed) and now i am solving using priority queue, and none of task are passing
logic:- i am taking a fix variable and inserting k-1 values in priority queue and whenever there is a update i am checking its sum, plss help

[syntaxhacker]

Check with accepted solutions

[prakash_6605]

i have done that , but i first want to know ,why this code is not running, i want you all to check it and tell me the error.

[syntaxhacker]

Your code is getting TLE verdict which means time limit error you need to optimize it

[prakash_6605]

no its not getting TLE its getting WA.

[syntaxhacker]

CodeChef: Practical coding for everyone then whats this

[prakash_6605]

This a recursive approach , which i attempted first and it gave TLE.
Now i am talking about another approach which i have tried , the link to solution is

CodeChef: Practical coding for everyone

[tiu1998]

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

Why is the code not working? How to take testcases as input? I am confused. Please help.

[syntaxhacker]

Thats not the link of the solution

[prakash_6605]

CodeChef: Practical coding for everyone , sorry here is the solution

[syntaxhacker]

try this case -

1
1 1
9

Output should be 1 as there’s only single subsequence 9 which is the min sum . you program gives 0 . as your code gives WA verdict for all cases your logic might be wrong

[prakash_6605]

Ok thanku ,I have removed that error , but still its givin WA. so can you pls tell me whats wrong with my logic
https://www.codechef.com/viewsolution/26717653