GCJ 2012 - Recycled Numbers

Below is the problem statement for 'Recycled Numbers' from 'Google Code Jam - 2012':

Problem Statement
-----------------

Do you ever become frustrated with television because you keep seeing the same things, recycled over and over again? Well I personally don't care about television, but I do sometimes feel that way about numbers.

Let's say a pair of distinct positive integers (n, m) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order. For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits in order to be a recycled pair. Neither n nor m can have leading zeros.

Given integers A and B with the same number of digits and no leading zeros, how many distinct recycled pairs (n, m) are there with A ≤ n < m ≤ B? Input ----- The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing the integers A and B. Output ------ For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1), and y is the number of recycled pairs (n, m) with A ≤ n < m ≤ B. Limits ------ 1 ≤ T ≤ 50. A and B have the same number of digits. Small dataset ------------- 1 ≤ A ≤ B ≤ 1000. Large dataset ------------- 1 ≤ A ≤ B ≤ 2000000. Sample Input ------------ 4 1 9 10 40 100 500 1111 2222 Sample Output ------------- Case #1: 0 Case #2: 3 Case #3: 156 Case #4: 287



For the above problem, a normal solution works for the small input datasets, but for larger input datasets, a bit of optimization has to be done. Below is the solution for the above problem, in Java.

GCJ 2012 - Dancing With Googlers

Below is the problem statement for 'Dancing With Googlers' from 'Google Code Jam - 2012':


Problem Statement
----------------------

You're watching a show where Googlers (employees of Google) dance, and then each dancer is given a triplet of scores by three judges. Each triplet of scores consists of three integer scores from 0 to 10 inclusive. The judges have very similar standards, so it's surprising if a triplet of scores contains two scores that are 2 apart. No triplet of scores contains scores that are more than 2 apart.

For example: (8, 8, 8) and (7, 8, 7) are not surprising. (6, 7, 8) and (6, 8, 8) are surprising. (7, 6, 9) will never happen.

The total points for a Googler is the sum of the three scores in that Googler's triplet of scores. The best result for a Googler is the maximum of the three scores in that Googler's triplet of scores. Given the total points for each Googler, as well as the number of surprising triplets of scores, what is the maximum number of Googlers that could have had a best result of at least p?

For example, suppose there were 6 Googlers, and they had the following total points: 29, 20, 8, 18, 18, 21. You remember that there were 2 surprising triplets of scores, and you want to know how many Googlers could have gotten a best result of 8 or better.

With those total points, and knowing that two of the triplets were surprising, the triplets of scores could have been:

10 9 10 6 6 8 (*) 2 3 3 6 6 6 6 6 6 6 7 8 (*)

The cases marked with a (*) are the surprising cases. This gives us 3 Googlers who got at least one score of 8 or better. There's no series of triplets of scores that would give us a higher number than 3, so the answer is 3.

Input
-----

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing integers separated by single spaces. The first integer will be N, the number of Googlers, and the second integer will be S, the number of surprising triplets of scores. The third integer will be p, as described above. Next will be N integers ti: the total points of the Googlers.

Output
------

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the maximum number of Googlers who could have had a best result of greater than or equal to p.

Limits
------

1 ≤ T ≤ 100. 0 ≤ S ≤ N. 0 ≤ p ≤ 10. 0 ≤ ti ≤ 30. At least S of the ti values will be between 2 and 28, inclusive.

Small dataset
-------------

1 ≤ N ≤ 3.

Large dataset
-------------

1 ≤ N ≤ 100.

Sample Input
------------

4
3 1 5 15 13 11
3 0 8 23 22 21
2 1 1 8 0
6 2 8 29 20 8 18 18 21


Sample Output
-------------

Case #1: 3
Case #2: 2
Case #3: 1
Case #4: 3


Below is the solution for the above problem, in Java. In the below code, the scores are stored in the ArrayList and are sorted first, so that the least score appears first, as it stands the first chance of not crossing the limit (score p). The score is then split into a triplet, equally dividing the total score into 3 parts. The max score in the triplet is then compared to 'p', to see if it crosses 'p'. If not, the code checks if there are any surprise triplets remaining. If there are any remaining surpirse triplets, the code tries to re-adjust the triplet scores to see, if it is possible to have it as a surprise triplet. After re-adjusting, it checks if the max score is greater than or equal to 'p'. If so, it adds to the result count.

GCJ 2012 - Speaking In Tongues

Below is the problem statement for 'Speaking In Tongues' from 'Google Code Jam - 2012':

Problem Statement
-----------------

We have come up with the best possible language here at Google, called Googlerese. To translate text into Googlerese, we take any message and replace each English letter with another English letter. This mapping is one-to-one and onto, which means that the same input letter always gets replaced with the same output letter, and different input letters always get replaced with different output letters. A letter may be replaced by itself. Spaces are left as-is.

For example (and here is a hint!), our awesome translation algorithm includes the following three mappings: 'a' -> 'y', 'o' -> 'e', and 'z' -> 'q'. This means that "a zoo" will become "y qee".

Googlerese is based on the best possible replacement mapping, and we will never change it. It will always be the same. In every test case. We will not tell you the rest of our mapping because that would make the problem too easy, but there are a few examples below that may help.

Given some text in Googlerese, can you translate it to back to normal text?

Solving this problem
--------------------

Usually, Google Code Jam problems have 1 Small input and 1 Large input. This problem has only 1 Small input. Once you have solved the Small input, you have finished solving this problem.

Input
-----

The first line of the input gives the number of test cases, T. T test cases follow, one per line.
Each line consists of a string G in Googlerese, made up of one or more words containing the letters 'a' - 'z'. There will be exactly one space (' ') character between consecutive words and no spaces at the beginning or at the end of any line.

Output
------

For each test case, output one line containing "Case #X: S" where X is the case number and S is the string that becomes G in Googlerese.

Limits
------

1 ≤ T ≤ 30.
G contains at most 100 characters.
None of the text is guaranteed to be valid English.

Sample Input
------------

3
ejp mysljylc kd kxveddknmc re jsicpdrysi
rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd
de kr kd eoya kw aej tysr re ujdr lkgc jv

Sample Output
-------------

Case #1: our language is impossible to understand
Case #2: there are twenty six factorial possibilities
Case #3: so it is okay if you want to just give up

The above problem is not a difficult one, but framed in a intelligent way, that it tests your readability and how smartly you implement your solution. Based on the 'sample input' and 'sample output', I built a small dictionary (char-char mapping) and solved the problem, as through the below code: