Hi all,

Hope you are all safe with the unfortunate events occurring throughout the world.

I was solving some problems on HackerEarth's CodeArena platform (1v1 other person, 1 problem, 20 mins, who ever gets more TCs wins) , when I came across this problem (the contest has ended). I have attached the screenshot of the statement to this post.

I first attempted to use combinatorics and math to solve it, but later changed to applying DP. However, I couldn't figure out a recurrence between the states (# of objects, # of groups).

I would really appreciate it if someone could lend a helping hand with the recurrence. Also, IF there is an easy mathematical solution to the problem, please share it.

Thanks for your help and time! BC

EDIT: Sorry, I assumed that the 'Add Image' feature automatically appended the image to the post. Attached below is the image.

Sample TC: Input: 4 2

Output 3

Auto comment: topic has been updated by BinaryCrazy (previous revision, new revision, compare).Auto comment: topic has been updated by BinaryCrazy (previous revision, new revision, compare).DP[i][j] = #of ways to put 'i' objects given 'j' open groups.

You have 2 transitions:

Add the current object to an open group — DP[i + 1][j] += j * DP[i][j]

Create a new group — DP[i + 1][j + 1] += DP[i][j]

Answer is DP[N][R]

Wouldn't transition 2 be DP[i][j.+ 1] += DP[i][j]?

You do not add an object every time you create a group?

How can you have a group without an object?

I like to pretend this is some philosophical question. "But how can there be a group if there is no object"?

My username also poses an interesting philosophical question: "Is water wet?"

But, Mr. wet_water, adding an object isn't a necessary requirement for creating a group!

Can you read the problem again, it says that each group must have at least 1 person

Okay, I see!

Thanks you Mr. wet_water!

did you try to run wet_water's code? i tried but that recurrence relation didn't seem to work out. can you please help me?

edit : sorry it worked i forgot to initialise dp[1][1] as 1 before. thanks @wet_water

Really sorry but your solution seems incorrect. you can even try to submit this. what type of objects did you consider identical or distinct.if it is identical then it should be simple Stars and Bars (n-1) C (k-1) and if it different it is the case of mutual exclusion principle. please delete your post

I think this is a classic stars and bars problem, you can read an introduction of that here. https://cp-algorithms.com/combinatorics/stars_and_bars.html

The problem can be easily solved with a simple recursive DP that works in O(N*R). Here is the code: https://ideone.com/c0Hjq2

Explanation: First, lets fill all the DP array values' to -1. Start a recursive function that has two parameters

xyfor example. Letxbe the index ofN. Letybe the objects that are currently available. Ifyis less than 0, then there is no answer. So return 0.(We are building up in this type of DP). But ifxreachedn, andyis equal to 0, then the job is done and it successfully distributed all of its objects so it return 1. Otherwise, ifxreachednandyisn't equal to 0, then it didn't finish its objects so it returns 0. We will run a for loop from 1 toyand try and distribute 1 object to the current group we are one, 2 objects to the current group we are on, 3,4,... untily. We will subtract what was taken from the objects and run that recursive.Edit: Found a combination solution which is: (N-1)C(R-1)(C means combination) But notice that: You cannot divide a number with modulo. You can read more about it: Here

dp[i][j]->total number of ways to group i numbers of objects in j number of groups.

There are two possibilities either we create a new group or don't create a new group so the recurrence relation will look like this....

dp[i][j]=dp[i-1][j-1]+j*dp[i-1][j]

it is simply (n-1)C(r-1).

I think the easy mathematical solution (with using combinatorics) for this problem is: (n — 1)! / (n — r)! * (r — 1)!

The question is a bit vague. When are two ways considered different? Are the groups differentiable. If yes then the solution is the coefficient of x^n in (x+x^2+x^3+...+x^n)*(x+x^2+x^3+...+x^n)*... r times (since there are r groups and we have to distribute total n items, also the power of x starts from 1 because we have to select atleast 1 item for a group). So,

coefficient of x^n in (x+x^2+x^3+...+x^n)*(x+x^2+x^3+...+x^n)*... r times

=>coefficient of x^n in x^r*(1++x+x^2+x^3+...+x^(n-1))*(1+x+x^2+x^3+...+x^(n-1))*... r times

=>coefficient of x^(n-r) in (1+x+x^2+x^3+...+x^(n-1))*(1+x+x^2+x^3+...+x^(n-1))*... r times

=>coefficient of x^(n-r) in (1-x)^(-1)*(1-x)^(-1)*... r times

=>coefficient of x^(n-r) in (1-x)^(-r)

=>(r+n-r-1)C(n-r)

=>(n-1)C(n-r)

=>(n-1)C(r-1) (since nCr = nC(n-r))

This can also be solved using dp. The state is dp[i][g], where dp[i][g] is the solution for the subproblem items [i:n-1] with g groups remaining. So the final solution is dp[0][r] or solve(0, r). A recursive method would look like: