muckibu.de

stuck in a geeks world

Facebook Hacker Cup 2012 – How to solve Alphabet Soup

Alphabet Soup was by far the easiest problem in the qualifiers. I am not talking implementation but about understanding the problem. In some cases the “problem designers” did a good job in confusing me for at least an hour by their style in description. In alphabet soup’s case the problem was formulated as follows:

Alfredo Spaghetti really likes soup, especially when it contains alphabet pasta. Every day he constructs a sentence from letters, places the letters into a bowl of broth and enjoys delicious alphabet soup.

Today, after constructing the sentence, Alfredo remembered that the Facebook Hacker Cup starts today! Thus, he decided to construct the phrase “HACKERCUP”. As he already added the letters to the broth, he is stuck with the letters he originally selected. Help Alfredo determine how many times he can place the word “HACKERCUP” side-by-side using the letters in his soup.

Input

The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case with a sequence of upper-case letters and spaces: the original sentence Alfredo constructed.

Output

Output T lines, one for each test case. For each case, output “Case #t: n”, where t is the test case number (starting from 1) and n is the number of times the word “HACKERCUP” can be placed side-by-side using the letters from the sentence.

Constraints

  • 1 < T ≤ 20
  • Sentences contain only the upper-case letters A-Z and the space character
  • Each sentence contains at least one letter, and contains at most 1000 characters, including spaces

To solve it, simply iterate through the characters in the string, counting how frequently each of them occurs.

Continue reading

Hacking Contest by Google, Code Jam 2012

Get seated, ready, steady.. GO. There is another annual hacking cup coming. I already pointed to the Facebook Hacker Cup a few days ago. Now it is time to announce that also Google is doing it’s annual contest in 2012.

Google Code Jam 2012

The first round starts in March 2012, so maybe you already want to lock the door for practicing.

Last year over 30,000 coders competed, be the 30,001 hacker that gets the almighty title of Code Jam Champion, and a hefty $10,000 reward.

Continue reading