Well if you insist on using this approach, since the constraints are small you can use arrays to compute the factorials or you could use a manual “BigInt” implementation (comes in handy) . This one seems to be feasible for the purpose: https://codeforces.com/blog/entry/16380
AC Solution using the same
1 Like
It’s not recommended to do it that way, though for the given constraints it works.
In case of n = 50 and r = 25 , you are calculating 50 * 49 * 48 * …*25 and this value is big for even long long int and so you are getting WA because of garbage value.
So here is my implementation of Combination function
Summary
long long nCr(int a, int b){
long long ans1[51] , ans2[51] ,ans3 = 1, ans4 = 1 ;
long long m = max(a-b,b);
long long n = min(a-b,b);
for(int i = a ; i > m ; i–) ans1[i] = i;
for(int j = 1 ; j <= n ; j++) ans2[j] = j;
for(int i = a ; i > m ; i–){
for(int j = n ; j > 1 ; j–){
{
for(int k = 2 ; k <= 50 ; k++){
if(ans1[i] % k == 0 && ans2[j] % k == 0){
ans1[i] = ans1[i]/k;
ans2[j] = ans2[j]/k;
}
}
}
}
}
for(int i = a ; i > m ; i–) ans3 *= ans1[i];
for(int j = 1 ; j <= n ; j++) ans4 *= ans2[j];
return(ans3/ans4);
}
2 Likes
Well written, beautiful code, this inspired me.
1 Like
Only 1 subtask failed on second list, which case might be failing for my code using DP ?
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Codechef {
public static void main(String[] args) throws IOException{
class ValueCountPair
{
int val;
int count;
public ValueCountPair(int val, int count) {
this.val = val;
this.count = count;
}
public void setCount(int count) {
this.count = count;
}
public int getCount() {
return count;
}
public int getVal() {
return val;
}
}
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while(t-- != 0)
{
String str[] = br.readLine().trim().split("\\s+");
int n = Integer.parseInt(str[0]);
int k = Integer.parseInt(str[1]);
String strs[] = br.readLine().trim().split("\\s+");
ValueCountPair cache[][] = new ValueCountPair[k+1][n+1];
int i, j;
for(i=0;i<=n;i++)
cache[0][i] = new ValueCountPair(0, 0);
for(i=1;i<=k;i++)
{
for(j=i;j<=n;j++)
{
if(i==j)
cache[i][j] = new ValueCountPair(Integer.parseInt(strs[j-1])+cache[i-1][j-1].getVal(), 1);
else
{
int newVal = Integer.parseInt(strs[j-1])+cache[i-1][j-1].getVal();
if(cache[i][j-1].getVal() == newVal)
{
if(i==1) // 4 2 2 2 2 2
{
cache[i][j] = new ValueCountPair(newVal, cache[i][j-1].getCount() + 1);
}
else
{
cache[i][j] = new ValueCountPair(cache[i][j-1].getVal(),cache[i][j-1].getCount());
cache[i][j].setCount(cache[i][j-1].getCount() + cache[i-1][j-1].getCount());
}
}
else if(cache[i][j-1].getVal() > newVal)
{
if(i!=1) // 5 4 2 3 2 3 2
cache[i][j] = new ValueCountPair(newVal, cache[i-1][j-1].getCount());
else
cache[i][j] = new ValueCountPair(newVal, 1);
}
else
{
cache[i][j] = new ValueCountPair(cache[i][j-1].getVal(),cache[i][j-1].getCount());
}
}
}
}
System.out.println(cache[k][n].getCount());
}
}
}
1 Like
Hi guys, if you’ll are pasting code in the comments, I suggest to use a hide detail to post it, for example, “[details=“Code”] Your code [/details]”, it will look much better and make the comments section easier to read
5 Likes
k > n, so we can’t form any set with k many elements and so the output should be 0 right?
1 Like
That’s right 
blah 20 characters blah
1 Like
But in problem it is given that k<=n right ?? How is K>n even possible in input ?
1 Like
Where does it say that?
In the constraints only, it is given right ?
Whoops - yes, you’re right - didn’t see that there
1 Like
@ssjgz When can we expect to see your editorial style documentation for FUZZYLIN? I really want to go through your explanation. 
Oops - completely forgot about that 
I’ve got quite a lot going on IRL at the moment, so it might have to wait until after the weekend.
It won’t be any better than the official Editorial explanation though, I don’t think.
2 Likes
No problem. 
I’d still love to take a look at your editorial. Take your time. I just wanted to make sure that it’s coming. Thank you once again for the other editorials too! Cheers! 
2 Likes
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: CodeChef: Practical coding for everyone
Let me know if something’s not clear.
14 Likes