Google Codejam 2013 Round 1C

Problem A. Consonants

http://code.google.com/codejam/contest/2437488/dashboard#s=p0

In brief, given a string \(S\) return the total number of substrings containing at least \(N\) consecutive consonants. The vowels are define as a, e, i, o, and u, and our consonants are the remaining 21 letters.

Let's begin by solving the small input of this problem, because the size of the string \(L\) can be at most 100. We just simple iterate over all the possibles substrings of the given string. For each substring check if contains at least one occurrence of \(N\) consecutive consonants, if that's the case we count that substring in our final answer. Things get a little bit more interesting when we are facing the large input, the size of the given string \(L\) can be at most \(10^{6}\). Clearly, the previous algorithm is not going to be fast enough. So we need a different approach to attack this problem.

First let's get some intuition with the following example:

S =  "quxrtz"
L =  6
N = 2

Imagine that we are iterating our string, until we find the substring "xr" which has \(N = 2\) consecutive consonants:

Now we should ask ourselves the following question, how many substrings  contains the string "xr"?

Listing all the substring of the given string S, we have in total 9 of them:

{"q", "u", "x", "r", "t", "z", "qu", "ux", "xr", "rt", "tz", "qux", "uxr",
"xrt", "rtz", "quxr", "uxrt", "xrtz", "quxrt", "uxrtz", "quxrtz"}

Where this answer come from? let's imagine for a second that we are building all the substrings that contains the string "xr". To do that we could either add characters to the front or to the end of "xr".

In the case of the left side we have 3 different possibilities, we can add "u", "qu" or "" (the empty string) to the front of "xr". In the same manner, in the case of the right side we also have 3 different possibilities, we can add "t", "tz" or "" (the empty string) to the end of the string "xr". By the rule of product we have \(3 \cdot  3 = 9\) substring including the string "xr".

Formalizing more the previous statement, let's call \(i\) the index of the last consonant that we found (0-based), and, let's call \(C\) the count of consecutive consonants so far. If the condition \(C \geq N\) holds, our count of substring that include this \(N\) consonants is given by the expression \((L - i) \cdot (i - N + 1)\).

There is just one problem remaining, what happen then if we apply the same method to the next N consecutive consonants:

We end up double counting some of the substrings (in red color the substrings that we have counted twice):

{"q", "u", "x", "r", "t", "z", "qu", "ux", "xr", "rt", "tz", "qux", "uxr",
"xrt", "rtz", "quxr", "uxrt", "xrtz", "quxrt", "uxrtz", "quxrtz"}

The solution to this issue is simple, instead of taking the whole left part of our string, we just take the part that we haven't count yet, we can do that by maintaining a pointer to the last \((i - N + 1)\) seen so far.

Adding this details left, we end up with the following expression \((L - i) \cdot (i - N + 1 - P)\) where \(P\) is the pointer to the last \((i - N + 1)\).

UVA 11076 - Add Again

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:

$$\\ S_{A_{1}} = 1(100) + 1(100) + 1(10) + 1(10) + 1(1) + 1(1) \\ S_{A_{1}} = 1(100 + 100 + 10 + 10 + 1 + 1) \\ S_{A_{1}} = 1(2!)(100 + 10 + 1) \\ S_{A_{1}} = 1(2!)(111)$$ $$\\ S_{A_{2}} = 2(100) + 2(100) + 2(10) + 2(10) + 2(1) + 2(1) \\ S_{A_{2}} = 2(100 + 100 + 10 + 10 + 1 + 1) \\ S_{A_{2}} = 2(2!)(100 + 10 + 1) \\ S_{A_{2}} = 2(2!)(111)$$ $$\\ S_{A_{3}} = 3(100) + 3(100) + 3(10) + 3(10) + 3(1) + 3(1) \\ S_{A_{3}} = 3(100 + 100 + 10 + 10 + 1 + 1) \\ S_{A_{3}} = 3(2!)(100 + 10 + 1) \\ S_{A_{3}} = 3(2!)(111)$$ To get our result we just need to add up the partials sum of each element in the sequence: $$\\ S = S_{A_{1}} + S_{A_{2}} + S_{A_{3}} = 1332$$ Generalizing the results obtained in the previous steps we have: $$\\ S_{A_{k}} = A_{k} (n - 1)! (\frac{10^n - 1}{9}) \\ S = S_{A_{1}} + S_{A_{2}} + ... + S_{A_{n}}$$ 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:
$$\\ S_{A_{k}} = A_{k} \frac{(n - 1)!}{f(A_{1})! \cdot f(A_{2})! \cdot ... \cdot (f(A_{k}) - 1)! \cdot ... \cdot f(A_{n})! } (\frac{10^n - 1}{9}) \\ S = S_{A_{1}} + S_{A_{2}} + ... + S_{A_{j}}$$ 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)\).

UVA 10910 - Marks Distribution

http://uva.onlinejudge.org/external/109/10910.html

You are a student that has taken a total of N subjects. In order to pass a certain subject, you need a least \(P\) marks of grade. You got a total of \(T\) marks among all your examinations. Your task is to print how many different ways you can distributed those marks among the N subjects in such way you pass all of them.

This problem can be solve with Dynamic Programming. The first thing to note is that we don't need to bother with distributions of grades were one or more grades are less than \(P\). In other words, we can assume that all the subjects start with \(P\) marks. Knowing this we just need to care in how to distributed the remaining \(T - N \cdot P\) marks left. To calculate this we are going to use top-down Dynamic Programming also known as memoization. 

The state of the DP state is simple: (current subject, remaining marks) = total number of configurations. For each subject  recursively we tried all the possible assignments of marks. Because we are counting different configurations the base case return the number 1. We use the variable res to add up all the valid configurations founded by the recursion function.