http://uva.onlinejudge.org/external/110/11076.html
You are given an sequence of \(n (1\leqslant n\leqslant12)\) digits, your task is to return the summation of all the unique permutations of those digits.
For example given the digits \({1, 2, 3}\) the sum of all the permutations is \(1332\):
\(123 + 213 + 132 + 231 + 312 + 321 = 1332\)
In order to understand the solution of the problem the reader should be familiar with the idea of permutations with repetitions.
The first question we should ask ourselves, it's possible to solve this problem using the brute force approach under the 3 seconds time limit constraint? The answer is no, the reason is simple, we are given at most 12 digits and 20,000 test cases. In the worst case scenario we have \(20,000 \cdot 12! = 9,580,032,000,000\), that is a pretty big number.
After realized that brute force is not feasible we should take a more clever approach. To simplify things a little bit I am going to divide the solution in the following two cases:
(1) All the digits in the sequence are unique.
A really important observation is that all the digits appear the same number of time for any position. Let's consider the initial example where the digits are \({1, 2, 3}\):
All the permutations gave us the following set:
\(\left \{ 123, 213, 132, 231, 312, 321 \right \}\)
If we put attention we can see that all the digits appear the same number of times (2 times) in each of the positions hundreds, tens and ones. The following example mark with red the hundreds positions:
\(\left \{ {\color{Red}1}23, {\color{Red}1}32 \right \}, \left \{ {\color{Red}2}13, {\color{Red}2}31 \right \},\left \{ {\color{Red}3}12, {\color{Red}3}21 \right \}\)
Another important detail to notice is once you fixed some arbitrary digit in certain position (e.g. ones, tens, hundreds, ...), the number of times that digit is going to occupied that position is \((n - 1)!\), where \(n\) is the length of the target sequence. Now let's denote \(S_{A_{k}}\) as the sum of all the positions that the \(A_{k}\) digit can occupied in all the unique permutations of the sequence, for each of the digits we got the following:
To get our result we just need to add up the partials sum of each element in the sequence: Generalizing the results obtained in the previous steps we have: Do not get confused by the formula \(\frac{10^{n} - 1}{9}\) this formula gave us the elements in the sequence \(\{0,1,11,111, ...\}\) (you can check this sequence in the OEIS website) .
(2) There is one or more digits repeated in the sequence.
The only difference between this case and the previous one is that now we need to eliminate the repetitions. Let's denote \(f(A_{k})\) as the frequency of the digit \(A_{k}\) in the sequence \(A\). We got the following expression:
Notice that because we can have repetitions the total sum \(S\), is restricted just to the unique elements of the sequence \(A\), this is why we introduce a variable \(j\) where \(1 \leqslant j \leqslant n \). We can also observe that the cases where each digit appear only one time, all the frequencies are going to gave us a product of 1, this means that the first formula is just one special case of the second one, knowing this we can forget about the first one and generalize both cases with the current formula.
If we implement the ideas set out above we are going to end up with an algorithm with overall time complexity of \(O(n)\).
You are given an sequence of \(n (1\leqslant n\leqslant12)\) digits, your task is to return the summation of all the unique permutations of those digits.
For example given the digits \({1, 2, 3}\) the sum of all the permutations is \(1332\):
\(123 + 213 + 132 + 231 + 312 + 321 = 1332\)
In order to understand the solution of the problem the reader should be familiar with the idea of permutations with repetitions.
The first question we should ask ourselves, it's possible to solve this problem using the brute force approach under the 3 seconds time limit constraint? The answer is no, the reason is simple, we are given at most 12 digits and 20,000 test cases. In the worst case scenario we have \(20,000 \cdot 12! = 9,580,032,000,000\), that is a pretty big number.
After realized that brute force is not feasible we should take a more clever approach. To simplify things a little bit I am going to divide the solution in the following two cases:
(1) All the digits in the sequence are unique.
A really important observation is that all the digits appear the same number of time for any position. Let's consider the initial example where the digits are \({1, 2, 3}\):
All the permutations gave us the following set:
\(\left \{ 123, 213, 132, 231, 312, 321 \right \}\)
If we put attention we can see that all the digits appear the same number of times (2 times) in each of the positions hundreds, tens and ones. The following example mark with red the hundreds positions:
\(\left \{ {\color{Red}1}23, {\color{Red}1}32 \right \}, \left \{ {\color{Red}2}13, {\color{Red}2}31 \right \},\left \{ {\color{Red}3}12, {\color{Red}3}21 \right \}\)
Another important detail to notice is once you fixed some arbitrary digit in certain position (e.g. ones, tens, hundreds, ...), the number of times that digit is going to occupied that position is \((n - 1)!\), where \(n\) is the length of the target sequence. Now let's denote \(S_{A_{k}}\) as the sum of all the positions that the \(A_{k}\) digit can occupied in all the unique permutations of the sequence, for each of the digits we got the following:
To get our result we just need to add up the partials sum of each element in the sequence: Generalizing the results obtained in the previous steps we have: Do not get confused by the formula \(\frac{10^{n} - 1}{9}\) this formula gave us the elements in the sequence \(\{0,1,11,111, ...\}\) (you can check this sequence in the OEIS website) .
(2) There is one or more digits repeated in the sequence.
The only difference between this case and the previous one is that now we need to eliminate the repetitions. Let's denote \(f(A_{k})\) as the frequency of the digit \(A_{k}\) in the sequence \(A\). We got the following expression:
Notice that because we can have repetitions the total sum \(S\), is restricted just to the unique elements of the sequence \(A\), this is why we introduce a variable \(j\) where \(1 \leqslant j \leqslant n \). We can also observe that the cases where each digit appear only one time, all the frequencies are going to gave us a product of 1, this means that the first formula is just one special case of the second one, knowing this we can forget about the first one and generalize both cases with the current formula.
If we implement the ideas set out above we are going to end up with an algorithm with overall time complexity of \(O(n)\).
No comments:
Post a Comment