×

# GERALD05 - Editorial

Author: Gerald Agapov
Tester: Tasnim Imran Sunny
Editorialist: Jingbo Shang

Medium

# PREREQUISITES:

Dynamic Programming, Combinatorics

# PROBLEM:

Given a lot of objects, grouped by the positive rang. F(N) determines the number of different object with rang N. Find out the number of different multisets whose sum of rangs are S.

# EXPLANATION:

First of all, we need to solve this basic problem: there are n different types of objects. Each object has infinity copies. How many different multisets which contains exactly m objects. (Denote this solution as G(n, m))

This problem is equivalent to the number of integer solutions of the equation x1 + x2 + ... + xn = m, where 0 <= xi.

We can plus n on both sides of the equation. And then, every solution is equivalent to insert n - 1 break points into m + n -1 gaps. Therefore, the answer is C(m + n - 1, n - 1). Here C is the Combination function.

Based on this, we can solve this problem using dynamic programming. Use f[i][j] to stand for the number of different multisets which contain the objects with rang between 1 and i and their rang-sum is j. The update rule is like the following:

  f[i][j] * G(F(i + 1), k) --->  f[i + 1][j + k * (i + 1)]


Since the modulo is a prime, we can perform the integer division via some multiplication (based on the Fermat's little theorem, which is a special case of Euler Theorem). And also, k is small here. we can calculate the G(,) function in O(k) time. Because (S / 1)^2 + (S / 2)^2 + (S / 3)^2 + ... (S / S)^2 is in O((logS)^2), the total time complexity is O(S^2(logS)^2).

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

19.8k350498541
accept rate: 35%

 0 Can anyone explain the solution clearly? answered 23 Dec '13, 01:25 350●1●6●12 accept rate: 6% Could you please figure out some clear questions rather than just asking generally? (23 Dec '13, 11:00) I couldn't follow starting from this statement: Use f[i][j] to stand for the number of different multisets... Can you explain from there? What exactly is the update rule? And what is 'k' in the update rule? (23 Dec '13, 11:42) 1 We try to solve this problem via dynamic programming (here, it is actually a recursion). "Update rule" in here is to do some summation over k. k is the number of objects we selected into our multiset with rang i + 1 , which is enumerated when update (i.e. summation). (23 Dec '13, 14:11)
 0 Somebody please explain Dynamic Programming part more clearly answered 29 Dec '13, 03:23 1●1●2 accept rate: 0% 2 There are two ways to describe a Dynamic Programming. I think you must be familiar with this way, like f[i][j] = max { ... } or f[i][j] = \sum { ... } Right? But we can treat this problem from the reverse way: use ... ---make max operation with----> f[i][j] or ... ---add to---> f[i][j] Using this way, could you try to understand the editorial again? Thanks! (01 Jan '14, 14:35) can you please use an example to explain this. take any one of the test case. (02 Jan '14, 20:35)
 0 I dont know why they even write editorials like this! I do not understand it ! Not written clearly , when turning to author and tester's code, they have used so many Pre processor directives ! Are they writing these codes for us or are they playing!! answered 09 Jun '15, 13:52 2★xlee 13●1 accept rate: 0%
 0 can u please explain - We can plus n on both sides of the equation. And then, every solution is equivalent to insert n - 1 break points into m + n -1 gaps. Therefore, the answer is C(m + n - 1, n - 1). answered 26 Feb '16, 17:49 3★glow 63●12 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,684
×2,598
×2,172
×892
×6

question asked: 23 Dec '13, 00:15

question was seen: 4,941 times

last updated: 26 Feb '16, 17:49