What is logic behind this problem?

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:

  1. Case 1: “He stays alone” - This case doesn’t increase the number of ways. So, f(n) = f(n-1)
  2. 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