Google Code Jam Archive — Farewell Round A problems

Test set 1

For the small test set, we compare each word encoding with the other words encodings. If any of the two encodings are equal then the answer is YES. Otherwise, the answer is NO. The time complexity for encoding all the words is $$$O(L)$$$ where $$$L$$$ is the sum of the lengths of the given $$$\mathbf{N}$$$ words. Since the length of a word is at most $$$10$$$, $$$O(L)$$$ can be written as $$$O(\mathbf{N})$$$. Therefore overall time complexity for this solution is $$$O(\mathbf{N}^2)$$$ which is sufficient for the small test set.

Test set 2

The above solution is not suitable for the large test set. Instead of comparing each pair of encoded words, we can calculate encoding for each word and then use hashing or sorting algorithms to check if any two encodings are equal.

Method 1

Hashing: We use a hash table to store the encodings. Before inserting an encoding of a word, we check if it already exists there. If it already exists then the answer is YES. If we had to insert all the words encodings then all are unique and the answer is NO. The time complexity for encoding all the words is $$$O(\mathbf{N})$$$. The time complexity for checking all the words in the hash table is also $$$O(\mathbf{N})$$$. The overall time complexity of this solution is $$$O(\mathbf{N})$$$ which is sufficient for the large test set.

Sample Code(C++)

string anyCollisions(vector<string> words, vector<int> encoding) {
   unordered_set<string> encoded_words;

   for(int i = 0; i < words.size(); i++) {
     string encoded_word;
     // Calculate the encoding for the word and store in encoded_word.
     if (encoded_words.contains(encoded_word)) {
       return "YES";
     }
     encoded_words.insert(encoded_word);
   }

   // If we reach here then there are no collisions.
   return "NO";
}

Method 2

Sorting: We store the encoding for each word in an array and sort them. If any two adjacent encodings are equal then the answer is YES. Otherwise, the answer is NO. The time complexity for encoding all the words is $$$O(\mathbf{N})$$$ and for sorting it is $$$O(\mathbf{N}\log\mathbf{N})$$$. The overall time complexity of this solution is $$$O(\mathbf{N}\log\mathbf{N})$$$ which is sufficient for the large test set.

Sample Code(C++)

string anyCollisions(vector<string> words, vector<int> encoding) {
   vector<string> encoded_words;

   for(int i = 0; i < words.size(); i++) {
     string encoded_word;
     // Calculate the encoding for the word and store in encoded_word.
     encoded_words.add(encoded_word);
   }

   encoded_words.sort();
   for(int i = 0; i < encoded_words.size() - 1; i++) {
     if (encoded_words[i] == encoded_words[i+1]) {
       return "YES";
     }
   }

   // If we reach here then there are no collisions.
   return "NO";
}

Test Set 1

For Test Set 1, we can use brute force and check all possible combinations of street light locations. For each combination, we need to check if it covers the entire freeway, and if it does, we add it to the list of candidates. We then return the combination which uses the least number of street lights. This will take $$$O(\mathbf{N} \times 2^\mathbf{N})$$$.

Test Set 2

For the Test Set 2, there are two observations we can make:

The street light locations are given in sorted order

The radius of each street light is the same

Since the radius is the same, this ensures that if the left point of a street light starts before the left point of another street light, it must also end before that street light. Since the light locations are given in sorted order, we will be able to iterate through them from left to right without skipping any street lights. Our ultimate goal is to find the minimum number of street lights where the freeway is lit up. Thus we can iterate through the given street light locations from left to right, and when deciding which street light to use, we take the rightmost light that also is able to cover all area (on the left) that has not been covered yet. This greedy strategy is always an optimal one, because it always leaves the rest of the uncovered areas of the street to be as small as possible.

To do this, we can keep a counter of how many street lights we used, as well as a variable to keep track of what area has been covered so far. We can do this by saving a variable $$$curr\_rightmost\_covered$$$ for what is covered so far. Specifically, the range $$$[0, curr\_rightmost\_covered]$$$ denotes what is already covered. Everytime we see a new street light at $$$\mathbf{X_i}$$$, we check that it does not leave a gap in the uncovered area by checking if $$$\mathbf{X_i} - \mathbf{R} \le curr\_rightmost\_covered$$$. If it does leave a gap, then it means that no street light can cover that gap, so the answer is impossible. Otherwise, we check the next street light after it, $$$\mathbf{X_{i+1}}$$$, to see whether that one also leaves no gap. If so, then we would prefer to use $$$\mathbf{X_{i+1}}$$$ instead of $$$\mathbf{X_{i}}$$$ and so forth. We will need to keep checking the next street light until we see one that leaves a gap $$$\mathbf{X_{k+1}}$$$. If the next street light $$$\mathbf{X_{k+1}}$$$ does leave a gap, that means we must take $$$\mathbf{X_{k}}$$$. In that case, we update $$$curr\_rightmost\_covered$$$ to $$$\mathbf{X_{k}} + \mathbf{R}$$$ where $$$\mathbf{X_k}$$$ is the rightmost street light that leaves no gap.

When the entire freeway is covered, we can stop and return the count of how many streets lights we used. The time complexity of this solution is $$$O(\mathbf{N})$$$ for each test case.

For simplicity, let us say the positive integers to be written on the cards are represented with an array A.

Test Set 1

In this test set, since $$$\mathbf{N}$$$ is very small, we can try all possible orderings of unique values of colours and use their indices in these orderings to build candidate A arrays and find one non-decreasing A from them.

Find all the unique values of $$$\mathbf{S}$$$ using a hash set in $$$O(\mathbf{N})$$$ time. Let $$$M$$$ be the array holding the unique values.
Find all the permutations of $$$M$$$. For each permutation $$$P$$$ of $$$M$$$, follow the below logic to create A.

Initialize a hash map $$$X$$$. For each $$$P_i$$$, assign $$$X[P_i] = i$$$. Iterate through $$$\mathbf{S}$$$ and for each $$$\mathbf{S_i}$$$, assign A$$$[i] = X[\mathbf{S_i}]$$$. Once A is constructed, we can easily check whether A is non-decreasing by iterating through the array.

Return IMPOSSIBLE if none of the A arrays is non-decreasing, else return one of them as the answer. For each permutation, we take $$$O(\mathbf{N})$$$ time to check whether the array A is non- decreasing. Since there are $$$O(\mathbf{N}!)$$$ such permutations, the overall complexity of this solution is $$$O(\mathbf{N}! \times \mathbf{N})$$$.

Test Set 2

The previous algorithm would be too slow for Test Set 2, so we must find a more efficient solution.

For cards to have a possible valid A array, we can conjecture that cards with the same value should be consecutive to each other, i.e., not separated by another card of a different value.
By way of contradiction, let us suppose our above conjecture is incorrect i.e., at least one card is present with a different number between two cards with same value.
Let $$$\mathbf{S_i}$$$, $$$\mathbf{S}_j$$$, $$$\mathbf{S}_k$$$ be three values in S such that $$$ i \lt j \lt k$$$ and $$$\mathbf{S_i} = \mathbf{S}_k \ne \mathbf{S}_j $$$. Hence A$$$[i] = $$$A$$$[k] \ne$$$A$$$[j]$$$.
Since $$$\mathbf{S_i} \ne \mathbf{S}_j$$$, A$$$[i] \lt $$$A$$$[j]$$$.
Similarly, since $$$\mathbf{S}_j \ne \mathbf{S}_k$$$, A$$$[j] \lt $$$A$$$[k]$$$.
Hence, A$$$[i] \lt $$$A$$$[k]$$$ which is contradictory.
So cards with the same values should be consecutive to each other.

It follows from the above observation that we only need to consider unique values of $$$\mathbf{S}$$$. For simplicity, let $$$K$$$ be the array after removing consecutive duplicates while keeping one instance of one unique value in $$$\mathbf{S}$$$ and also keeping the order of unique elements same. Let $$$L$$$ be the array such that $$$L_i$$$ is the index position of $$$\mathbf{S_i}$$$ in $$$K$$$. We can easily see that $$$L$$$ is a non-decreasing array and the mapping between $$$\mathbf{S}$$$ and $$$L$$$ is one to one.

Initialize an A array and an empty hash set to store elements of $$$\mathbf{S}$$$ seen while iterating. Iterate through $$$\mathbf{S}$$$ from left to right and for each $$$\mathbf{S_i}$$$, find if the element appeared before in the list i.e., if the element is present in the hash set.
If the element is not present, then insert the element into the hash set and A array and continue iterating.
If the element is present in the hash set and it is equal to the previous element in $$$\mathbf{S}$$$ then continue iterating else return the answer as IMPOSSIBLE.

If we are able to successfully iterate all the way through $$$\mathbf{S}$$$, then return the A array built while iterating. Since we are iterating through $$$\mathbf{S}$$$ only once and using the hash set, the overall time complexity of this solution is $$$O(\mathbf{N})$$$.

Test Set 1

For relatively small values of $$$\mathbf{N}$$$, it suffices to simulate the program in the problem statement to generate characters accordingly and output whichever character gets generated at the $$$\mathbf{N}$$$-th position. Since each character is generated in order and no additional calculation needs to be done, the time complexity of this solution is $$$O(\mathbf{N})$$$, which suffices for Test Set 1.

Test Set 2

The solution described for Test Set 1 would fail for Test Set 2 as $$$\mathbf{N}$$$ is significantly larger here. We would need to utilize the pattern of the characters to improve on it.

One observation we can make is that if we know which iteration of Cody-Jamal's program printed out the $$$\mathbf{N}$$$-th character (let us say it is the $$$i$$$-th iteration) and how many characters were already printed before that (let us say $$$M$$$ characters were already printed before the $$$i$$$-th iteration), we can easily figure out which character is the $$$\mathbf{N}$$$-th character.

Since we know $$$M$$$, we can say that our answer is the $$$(\mathbf{N} - M)$$$-th character printed in the $$$i$$$-th iteration. Let's define $$$k = \mathbf{N} - M$$$. Clearly, if $$$k \le i$$$, the character is A, if $$$i \lt k \leq 2i$$$, the character is B and so on. Simply put, the $$$\mathbf{N}$$$-th character printed is the $$$\lceil \frac{k}{i} \rceil$$$-th letter of the alphabet, i.e. the $$$\lceil \frac{\mathbf{N} - M}{i} \rceil $$$-th letter of the alphabet. Also note that if we know $$$i$$$ alone, we can compute $$$M$$$ as $$$26 \times \sum_{j=1}^{i - 1} j$$$. All that remains is to determine $$$i$$$, which can be done in the following ways:

Linear Search

We essentially need to find the largest $$$i$$$ such that $$$M = 26 \times \sum_{j=1}^{i - 1} j \lt \mathbf{N}$$$. We can simply compute this sum in order until the point where $$$26 \times \sum_{j=1}^{i - 1} j = 13 \times i \times (i - 1) \geq \mathbf{N}$$$. The time complexity for this approach is $$$O(\sqrt{\mathbf{N}})$$$ since $$$13 \times i \times (i - 1)$$$ increases quadratically.

Binary Search

The previous approach can be sped up by utilizing the fact that $$$13 \times i \times (i - 1)$$$ monotonically increases, which allows us to binary search for $$$i$$$ instead. The bounds for $$$i$$$ to binary search on can be roughly set as 1 and $$$\mathbf{N}$$$. The time complexity in this case is $$$O(\log \mathbf{N})$$$.

Directly Calculating $$$i$$$

As mentioned earlier, we want to find the largest $$$i$$$ such that $$$13 \times i \times (i - 1) \lt \mathbf{N}$$$. Let $$$z$$$ be the positive root of the quadratic equation $$$13 \times i \times (i - 1) - \mathbf{N} = 0$$$. For $$$0 \le i \lt z$$$, the value of $$$13 \times i \times (i - 1) - \mathbf{N}$$$ is negative, after which it becomes positive. Thus, our problem reduces to finding the largest integer $$$i \lt z$$$, which is simply $$$\lceil z - 1 \rceil$$$. $$$z$$$ can be calculated using the quadratic formula as $$$\frac{13 + \sqrt{169 + 52\mathbf{N}}}{26} = \frac{1 + \sqrt{1 + \frac{4\mathbf{N}}{13}}}{2}$$$.

Test Set 1

In Test Set 1, the limits are small enough that we can try every possible string made entirely of Rs, Ps, and Ss as the destination (there are only $$$3^{10} = 59049$$$ of them). For each one, we can check pairs of adjacent letters to make sure it is valid. For the valid destinations, we can see how many changes they require, and keep a running minimum of it.

This solution could be sped up by either generating the strings in a smarter way that does not generate lots of invalid cases only to filter them out later, or by precalculating all valid strings for each length only once, and then using that list directly for each test case. However, none of this is required to pass Test Set 1.

Test Set 2

For Test Set 2 we need a completely different approach, as there are way too many strings to try. We can observe that if we choose any one person, we can always make a choice for them that is different than their neighbors (because there are $$$2$$$ neighbors and $$$3$$$ possible choices). Therefore, any time we have two adjacent equal letters with their other neighbors different, we can always fix it with a single change, and we need at least one. Generalizing that, if we have exactly $$$k$$$ consecutive letters that are equal, surrounded by different ones on both sides, we need at least $$$\lfloor k / 2 \rfloor$$$ changes, and we can do it with exactly that many by changing alternating letters. Therefore, we can add that quantity for each run of consecutive letters (remembering to consider a prefix and a suffix that are made of the same letter as a single run) to the total.

There is one case that we need to solve differently, though. Notice that our precondition above is that a run of consecutive letters is surrounded by other letters. However, if all letters in the input are the same, there is no such run! This case is simple, though, as the answer is, as hinted by Sample Case #2, $$$\lceil$$$the length of $$$\mathbf{C} / 2 \rceil$$$.