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

×

CNTDSETS - Editorial

2
1

PROBLEM LINK:

Practice
Contest

Author: Mugurel Ionut Andreica
Tester: Mahbub
Editorialist: Jingbo Shang

DIFFICULTY:

Hard

PREREQUISITES:

Combination, Inclusion–exclusion principle, Euler's theorem

PROBLEM:

Find out how many distinct integer point sets are there in N dimension with diameter D. Diameter is defined as the maximum range of the point set among N dimensions. And two point sets are treated as same if and only if they can be coincided after translation (adding some offset).

EXPLANATION:

First of all, we need to make our goal clearer. Because of the restriction of D, we can assume all points are in the cube of [0, D]^N. And, to eliminate the duplicated point set, we can force that the zeros in all dimensions should be reached by at least one point in the chosen point set (can be several points to cover different dimensions). Further, to make sure the diameter is exactly D, we need there exists one dimension, whose D is reached by some point.

After writing this clearer goal, you may find it is still complicate. Let's see a simpler version:

Replace the restriction of diameter = D of diameter <= D.

If we can solve this simpler version, the original problem can be solved too -- using the answer of <= D minus the answer of <= D - 1. Therefore, let's focus on the simpler one:

How many point sets are there, satisfying (1) points are in [0, D]^N; (2) zeros in all dimensions are reached by some point (can be several points to cover different dimensions).

Intuitively, this problem can be solved by Inclusion–exclusion principle. Follow the same notations in wiki, let's define Ai as the event of the zero of i-th dimension has NOT been reached. And then, the number of point sets that zeros from at least k dimensions have NOT been reached equals:

C(N, k) * 2^(D^k * (D + 1)^(N-k))

We can prepare the C(N, k), which is the combination number, in O(N^2) time. Via Euler's Theorem, we can calculate D^k * (D + 1)^(N-k) module phi(10^9 + 7) (equals to 10^9 + 6, denote as PHI).

Therefore, we can calculate the summation of the following term from k = 0 to k = N in O(NlogPHI) time. The log comes from the fast power module.

(-1)^k * C(N, k) * 2^(D^k * (D+1)^(N-k))

In summary, we can solve this problem in O(N^2 + T * N log PHI) time, T is the number of test cases. Furthermore, if we calculate the combination number by factorials (Buffer all factorials in an array. The division can be handled in O(log PHI) time since the 10^9+7 is a prime), the time complexity can be controlled within O(T * N log PHI).

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 13 Jan '14, 15:11

shangjingbo's gravatar image

3★shangjingbo ♦♦
161446375
accept rate: 0%

edited 22 Apr '15, 18:14

admin's gravatar image

0★admin ♦♦
19.8k350498541

can you please explain (d-1)^(N-k) ?? should it not be (d+1)^N-k

(14 Jan '14, 02:29) whistler2★

fixed. thanks

(14 Jan '14, 07:43) shangjingbo ♦♦3★

Help please !! I am not very confident about my Permutation&Combination knowledge but shouldn't it be

2^(D^k + (D+1)^(N-k)) instead of 2^(D^k * (D+1)^(N-1))

(14 Jan '14, 13:03) divy72★

where is N-1???

(14 Jan '14, 15:49) shangjingbo ♦♦3★

oh, D^k * (D + 1)^(N- k) is the total integral points in the cube, with k dimension of [1..D] and N-k dimension [0..D]

(14 Jan '14, 15:50) shangjingbo ♦♦3★

sorry for the late rply.. what I meant to say was shouldn't there be a + instead of * in the equation, ( 'D^k +' instead of 'D^k *' ) thanks in advance :)

(18 Jan '14, 23:43) divy72★
showing 5 of 6 show all

This editorial is awful but the description of the solution in Author's solution is much easier to understand.

link

answered 18 Dec '17, 22:21

akash_kmr's gravatar image

4★akash_kmr
284
accept rate: 20%

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,677
×1,343
×888
×65
×51

question asked: 13 Jan '14, 15:11

question was seen: 2,583 times

last updated: 18 Dec '17, 22:21