PREREQUISITES:
- Basic Combinatorics
PROBLEM LINK:
PROBLEM IN SHORT:
Given a number n, how many permutations of numbers-
1,2,…,n-1,n are there such for every k < N the set of ministers sitting in the first k chairs DOES
NOT consist only of the ministers 1, 2, . . . k.
Each digit(0-9) has a cost.
What is the maximum number you can write such that the total cost incurred is less than equal to B?
The cost for each digit will be given to you.
QUICK EXPLANATION:
Let ans[n] denote the answer for that n.
Then calculate all the values till n = 4 manually.
After that
ans[5] = 5!-(ans[1]*4!+ans[2]*3!+ans[3]*2!+ans[4]*1!)
ans[6] = 6!-(ans[1]*5!+ans[2]*4!+ans[3]*3!+ans[4]*4!+ans[5]*5!)
and so on …
EXPLANATION:
Let ans[n] denote the answer for a that n
Now we can manually calculate the values till n = 4
So after doing some pen and paper work we get,
ans[1] = 1
ans[2] = 1
ans[3] = 3
ans[4] = 13
Now let’s compute ans[5] smartly without all the manual work,
So the total number of permutations not excluding the ones not allowed are 5!
Now lets keep subtracting the ones not allowed
So, the first number cannot be 1. So if the first number is 1 and the other numbers no matter
whatever they might be we have to exclude them. So, total number of permutations with first
number being 1 = 4! because we can choose the rest 4 numbers in any order.
Now the first two numbers cannot be a permutation of 1,2
which is basically 1,2 and 2,1 but we notice that we can’t subtract the permutation starting with 1,2
as we have already subtracted the ones starting with 1. So we subtract the ones starting with 2,1 and
the rest three numbers can be anything so that’s 3!.
Now the first 3 numbers can’t be a permutation of 1,2,3
So they can’t be starting with
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
We have already excluded the ones starting from 1 or 2,1
which leaves us
2,3,1
3,1,2
3,2,1
Here we also notice one thing,
that this cnt = ans[3] = 3 ([2,3,1],[3,1,2],[3,2,1])
the previous cnt was ans[2] = 1 ([2,1])
and the one before that ans[1] = 1 ([1])
and how is it exactly coming this way?
So, notice here ans[2] = count of all the permutations of length 2 such that they don’t contain 1 as
the first letter (1 was the permutation for ans[1])
and ans[3] = count of all the permutations of length 3 such that they don’t contain 1 or 2,1 at start (1
was the permutation for ans[1] and 2,1 was the one for ans[2])
also ans[4] = count of all the permutations of length 4 such that they don’t contain 1 or 2,1 or either
of ([2,3,1],[3,1,2],[3,2,1]) at start (1 was the permutation for ans[1] and 2,1 was the one for ans[2]
and the last 3 were those of ans[3])
So, let’s forget all that we have done while calculating ans[5] and let’s use this easier method. (I
was telling you the other way so as to come to this point)
Also, note that we are not double counting as while removing let’s say those of ans[2] we aren’t
removing those of ans[1] as ans[2] doesn’t include those.
So, we can define ans[5] as 5! - (ans[1]4!+ans[2]3!+ans[3]2!+ans[4]1!)
= 120-(124+16+32+131)
= 120-(24+6+6+13)
= 120-49
= 71
Bonus: Do the 2nd and 3rd part yourself.
Hope that helped.