Facebook Hacker Cup 2012: Alphabet Soup Solution


This code appeared in the Facebook Hacker Cup 2012 – Qualification Round

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 Sample Input
5
WELCOME TO FACEBOOK HACKERCUP
CUP WITH LABEL HACKERCUP BELONGS TO HACKER
QUICK CUTE BROWN FOX JUMPS OVER THE LAZY DOG
MOVE FAST BE BOLD
HACK THE HACKERCUP

Sample Output
Case #1: 1
Case #2: 2
Case #3: 1
Case #4: 0
Case #5: 1

My Solution

A rather simple problem. I believe even a naive approach where you store all the letters and then go picking one by one forming the desired string until you can’t form no more would be fast enough.

I figured it would be easier to simply find the minimum of all the letters you need to form HACKERCUP (diving C by 2 as it appears twice).

#include <iostream>
#include <cstdio>

int main(){
    int t,i;
    int alphabet[26];
    int letters[8] = {0,2,4,7,10,15,17,20};
    char c;
    int min;

    scanf("%d",&t);
    getchar();

    for (i=0;i<t;i++){
        min=1000;
        for (int x=0;x<26;x++)
            alphabet[x]=0;

        while((c=getchar())!=10){
            if (c==' ')
                continue;
            else{
                alphabet[c-65]++;
            }
        }

        alphabet[2] = alphabet[2]/2;

        for (int j=0;j<8;j++){
            if (alphabet[letters[j]]<min)
                min=alphabet[letters[j]];
        }

        printf("Case #%d: %d",i+1,min);
        if (i<t-1)
            printf("n");

    }
    return 0;
}


2 thoughts on “Facebook Hacker Cup 2012: Alphabet Soup Solution

  1. harry

    I coudnt understand the logic behind the values in the array “letters”. How are u computing the values 0,2,4,7,10,. ??

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *