GERALD05 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

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.

3 Likes
2

Can anyone explain the solution clearly?

3

Could you please figure out some clear questions rather than just asking generally?

4

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?

5

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).

1 Like
6

Somebody please explain Dynamic Programming part more clearly

7

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!

2 Likes
8

can you please use an example to explain this. take any one of the test case.

9

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!!

10

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).