You are not logged in. Please login at www.codechef.com to post your questions!

×

GERALD05 - Editorial

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

This question is marked "community wiki".

asked 23 Dec '13, 00:15

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 35%

edited 23 Dec '13, 00:43


Can anyone explain the solution clearly?

link

answered 23 Dec '13, 01:25

rushilpaul's gravatar image

4★rushilpaul
3501612
accept rate: 6%

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

(23 Dec '13, 11:00) shangjingbo ♦♦3★

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) rushilpaul4★
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) shangjingbo ♦♦3★

Somebody please explain Dynamic Programming part more clearly

link

answered 29 Dec '13, 03:23

shubhhack's gravatar image

2★shubhhack
112
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) shangjingbo ♦♦3★

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

(02 Jan '14, 20:35) shubhhack2★

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

link

answered 09 Jun '15, 13:52

xlee's gravatar image

2★xlee
131
accept rate: 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).

link

answered 26 Feb '16, 17:49

glow's gravatar image

3★glow
6312
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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