gXa's blog

Math/DP Question
By gXa, history, 7 years ago, In English

You are given N candies and K boxes. You need to find the number of ways to divide N candies in K boxes such that each box should have one candy and you should not count repetitive sequences. The boxes and candies are identical.

Is there any question similar asked before?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Would you consider 2 + 2 + 1, and 1 + 2 + 2 as different sequences for N = 5, k = 3 ?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I believe you are asking for the number of partitions of a number into k parts.

Let us denote this number by f(n, k).

Now, there are two possibilities — Either there is some box which has exactly one candy or every box has more than one candy.

If the smallest number of candies in any box is 1. Then the problem reduces to finding f(n — 1, k — 1).

Otherwise, let every box have at least one candy. Then we place one candy in each of the k boxes, and now distribute the remaining (n — k) candies into k boxes. This is given by f(n — k, k)

f(n, k) = f(n — 1, k — 1) + f(n — k, k)

I hope this helps.

f(0, k) = 0, for all k f(1, 1) = 1 f(n, 1) = f(n, n) = 1, for all n

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You want all boxes to have at least 1 candy. Then you can remove this restriction by simply subtracting K from N. Now the problem is simply to find the number of combinations with repeatings. This count is equal to C(n + k - 1, k - 1), where C(n, k) is the number of ways to chose k out of n values. You can find an easy explanation by googling "combinations with repeatings", or I can explain it if you want (googling will be faster).

This problem if I'm not mistaken was asked in Codechef long challenge in the beginning of 2017.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How would it take into account "no repetitive sequences", as u may count 1, 4 and 4, 1 as same sequences.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    N = 5, K = 2

    N -= K => 3

    3+1 C 1 => 4 ways

    1 4

    2 3

    Only correct ones, so answer should be two

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Simply divide the answer by K! or smth like that.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am unable to get your k! part.

        Can u plz provide problem link? I'll try to figure out myself.

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can u plz help?

        → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But, the boxes are indistinguishable !

    → Reply