ZIO18004 - Editorial

editorial
, , , , ,
1

PROBLEM LINK: Zonal Informatics Olympiad, 2018

EDITORIALIST: Aryan Maskara

DIFFICULTY: Easy-Medium

PREREQUISITES: Permutations and Combinations and Factorials

PROBLEM STATEMENT:

You are given numbers N and K. There is a set S = {1, 2, … , n}. An ordered tuple is a subsequence of this set. Note, that we can rearrange the elements within a tuple in S.

The following are considered as 2 different tuples:

{ (1, 2), (3) } and { (2, 1), (3) }

The above implies, that rearrangement of elements within one tuple, is counted as two different valid configurations.

While, the following are the same:

{(1, 2), (3) } and { (3), (1, 2) }

The above implies, that the rearrangement of tuples in one valid configuration doesn’t count twice.

Find the different ways of partitioning the set S into ordered tuples such that no tuple has a size greater than K.

QUICK EXPLANATION:

For a tuple of size r(1 to k, as the limit can’t exceed k), we first compute nPr (n having the original meaning). This gives us the number of permutations of the tuples. Now as we have to take one tuple from size r, we have (n - r) positions to be picked, and r sizes of tuples in which we can choose from. Choose the (n - r) positions in the r sized tuples and note that tuples of the same size in a set, can’t be used as in condition 2. Likewise, you need to divide and get the correct answer.

EXPLANATION:

In this section, some symbols denote particular things. They are:

  1. r – Current size of the tuple we are considering.
  2. n – The number given to us. Same meaning as in the question.
  3. K – The other number given to us. Same meaning as in the question.
  4. aCb – The number of ways in which we can choose b elements from a elements. The formula for this is (a! / ( (a - b) ! * (b!) ) )

Where a! means n factorial, which is a * (a - 1) *… * 2 * 1.

  1. aPb – The number of ways in which we can choose b elements from a elements and rearrange it. (Rearranging a tuple counts as 2 different tuples). The formula for this is (a! / (a - b) ! )

Note: a and b are replaced by natural numbers, below, and not denoted as a and b. If you didn’t know, 0 ! is not 0, but 1.

After reading the question, we come to know that it is about arrangements. The first thing which comes to our mind when we hear “arrangements” is permutations and combinations. With this as our prerequisite, and some easy observations, we will get our answers.

Observation / Basic Idea:

  1. One mistake that 99.9% of people make when it comes to this is overcounting (i.e counting the same sequence a repeated number of times). The idea for us to encounter this is that when we choose to work on a tuple of size r, we will only consider tuples of size <= r
Proof that it will work

Suppose there is a combination which has one tuple of size 2, and one tuple of size 3. When we consider tuples of size 2, we will not take this combination into consideration as the sizes of all its tuples are not <= 2.

When we consider tuples of size 3, we will take this combination into consideration as the size of all its tuples is <= 3.

When we consider tuples of size 4, we will not consider this combination because there is no tuple of size 4. Likewise, all the other arrangements will be chosen only once.

–End of proof–

So, according to our basic idea, our aim is to consider all tuples (from 1 to k), and when considering them, we make a set which has one tuple of that size, and all the other tuples are <= the size we are considering currently.

For example, a valid configuration when we are currently considering a tuple of size 3 (N = 6) is ({1, 2, 3}, {4, 5, 6}) or ({1, 2, 4}, {5, 6}, {3}) and many more…

Now, what will be our formula?

Firstly, we have to add all the number of arrangements which we have found out are made previously for the sizes < r.

Secondly, we have to choose a tuple of size r. So there are nCr ways to choose it, and as we can rearrange it, we add nPr. (because nPr is nCr + rearranging)

Now, a valid arrangement shall contain that tuple, and many other tuples of size <= r. Suppose, for N = 4, K = 2, we have chosen a tuple of size 2. Now there are 2 elements left, and we need to choose 2 of them. As rearrangement is possible, we will multiply our answer by 2P2. On the other hand, we can’t arrange the tuples in our set, thus we divide it by 2.

Note: We multiply and divide because for each valid tuple the configuration is possible, and not only for a single one. We add the answers to all the calculations as has to be counted only once.

Now suppose N = 6, K = 2, r = 2. We choose a tuple of size 2. Now, we have 4 elements in which we can choose 2, thus we multiply our answer by 4P2. Now, we have 2 elements and we have to choose 2, thus we multiply our answer by 2P2. We can arrange the tuples of size 2 in 6 ways. Thus we divide our answer by 6, etc.

Similarly, it is not that we have to only choose a tuple of size r in our set. We can make a tuple of size 2, when r is 3. So our answer is, choose X tuples of size Ai. Ai denotes the size of the ith tuple. Here the summation of all Ai is equal to N.

Now, iterate through A which we have made, and write down the number of tuples of size B (for all B from 1 to N). We divide the answer we got by this arrangement by the factorial of the numbers written.

Example:

N = 8, K = 3.

One possible way is to choose 3 tuples of size 2, 2 tuples of size 1.

Thus whatever our answer will be, we will divide it by ( (3 !) + (2 !) )

This is because rearrangement of tuples will not count as two valid configurations, thus, there are 3 ! ways to arrange the tuples of size 2, and 2 ! ways to arrange the tuples of size 1. Thus, we divide our answer by this.

SOLVING SUBTASKS:

Subtask A

N = 4, K = 3

  1. r = 1. The number of permutations which can be made by only tuples of size 1 is 1.

Thus, answer = 1.

  1. r = 2. According to the formula we have taken out above, the answer will be:

Previous calculations + 4P2 + ( (4P2 * 2P2) / 2 !)

=> 1 + (24 / 2) + ( ( (24 / 2) * (2 / 1) ) / 2)

=> 1 + 12 + (12 * 2) / 2

=> 1 + 12 + 12

=> 25

  1. r = 3.

Answer will be:

Previous calculations + 4P3

=> 25 + (24 / 1)

=> 25 + 24

=> 49

So our final answer is 49.

Subtask B

N = 5, K = 3.

  1. r = 1. The number of permutations which can be made by only tuples of size 1 is 1.

Thus, answer = 1.

  1. r = 2. According to the formula we have taken out above, the answer will be:

Previous calculations + 5P2 + ( (5P2 * 3P2) / (2 !) )

=> 1 + (120 / 6) + ( ( (120 / 6) * ( 6 / 1 ) ) / (2 !) )

=> 1 + 20 + ( 20 * 6 / 2)

=> 1 + 20 + 60

=> 81

  1. r = 3.

Answer will be:

Previous calculations + 5P3 + (5P3 * 2P2)

=> 81 + (120 / 2) + ( (120 / 2) * (2 / 1) )

=> 81 + 60 + (60 * 2)

=> 81 + 60 + 120

=> 261

Thus, our final answer is 261.

Note: Here we did not divide by 2!, as the sizes of tuples were different, i.e one tuple was of size 2, and one of size 3.

Subtask C

N = 6, K = 3.

  1. r = 1. The number of permutations which can be made by only tuples of size 1 is 1.

Thus, answer = 1.

  1. r = 2. According to the formula we have taken out above, the answer will be:

Previous calculations + 6P2 + ( (6P2 * 4P2) / (2 !) ) + ( (6P2 * 4P2 * 2P2) / (3 !) )

=> 1 + (720 / 24) + ( (720 / 24) * (24 / 2) ) / (2 !) ) + ( ( ( 720 / 24) * (24 / 2) * (2 / 1) ) / (6) )

=> 1 + 30 + ( (30 * 12) / 2) + ( (30 * 12 * 2) / 6)

=> 31 + 180 + 120

=> 331

  1. r = 3.

Answer will be:

Previous calculations + 6P3 + ( (6P3 * 3P3) / (2 !) ) + (6P3 * 3P2)

=> 331 + 120 + ( (120 * 6) / 2) + (120 * 6)

=> 451 + 360 + 720

=> 1531

So, our final answer is 1531.

EXTRAS:

Find the answer when N = 5, K = 3 and we are not allowed to rearrange the elements in set S.

Thus, a tuple {1, 3} will not be valid here.

I hope I could make you understand the concept of this problem.

8 Likes