Problem link-https://www.codechef.com/TSCO2017/problems/TSECJ105/
Question- A teacher wants every student to work on a project. A student can work on a single project, either alone or with a partner (group of 2). The teacher is okay with any number of pairs or sole workers.
The teacher is curious to know that how many possible ways can N students form pairs or stay solo. Can you help?
Note: Since the answer can be large, print it modulo 10^9+7
Input:
2
2
3
Output:
2
4
My approach is use nc2(im getting WA),please explain your approach?
This problem can be solved using Dynamic Programming.
Let f(n) denote the numbers of ways to partition n students into sets of size 1 and 2.
Now, the n^{th} student has two options:
-
Case 1: “He stays alone” - This case doesn’t increase the number of ways. So, f(n) = f(n-1)
-
Case 2: “He pairs up” - Suppose he pairs up with i^{th} student. The remaining n-2 students can be partitioned in f(n-2) ways. But, the i^{th} student can be chosen in n-1 ways. So, f(n) = (n-1) \times f(n-2)
Thus, f(n) = f(n-1) + (n-1) \times f(n-2) for n > 1
And, the base cases are f(0) = 1,\ f(1) = 1
5 Likes
I have also used the nC2 approach here. I am getting the write answer. This is the code:
//Program
#include
using namespace std;
int fact(int);//returns factorial of a number
int comb(int, int);//returns the number of ways of selecting r students (2nd parameter) among n students (1st parameter)
int proj(int);//computes the final answer
const unsigned int M=1000000007;
int main()
{
int tc;//stores number of test cases
cin>>tc;
int arr[tc];//stores values of test cases
for(int i=0; i<tc;i++)
{
cin>>arr[i];
}
for(int i=0; i<tc;i++)
{
cout<<proj(arr[i])<<"\n";
}
return 0;
}//end of main
int fact(int num)
{
int factor;
if(num==1||num==0)
return 1;
else
{
factor=num*fact(num-1);
}
return factor;
}
int comb(int k, int r)
{
int combo;
combo=(fact(k)/(fact(r)*fact(k-r)));
return combo;
}
int proj(int t)
{
int prob=0;
for(int n=t/2, p=t; n>=1; n--, p-=2)//t is the total number of students
{
prob=(prob%M)+((n*comb(p,2))%M); //used this property of modulo: (a+b)%c=((a%c)+(b%c))%c
}
return ((prob%M)+1);// +1 for the case when all students are alone
}
Sorry this works only for very small values. There’s some problem when I run it with large values. I need to rectify that.
i also used bigintegers but nc2 doesn’t work.is my logic is correct? one more way is to find (n-((n*(n+1))/2)+1(for individual case))%1000000007.is this correct way?
please explain in detail.as iam not getting how the ways are calculated