CHEFINSQ - Editorial

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;

}

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.

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

@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: https://www.codechef.com/viewsolution/26641722
Let me know if something’s not clear.

14 Likes

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;

}

format code


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

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

1 Like

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

#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

Check with accepted solutions

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.

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

no its not getting TLE its getting WA.

https://www.codechef.com/viewsolution/26496975 then whats this :thinking:

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
https://www.codechef.com/submit/CHEFINSQ

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

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

Thats not the link of the solution

https://www.codechef.com/viewsolution/26704024 , sorry here is the solution

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

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