Solutions to Facebook Hackercup. Feel free to fork and make improvements! I didn't really take much time to write this, so help on clarifying the text is very much appreciated!

balanced_smileys.cpp

#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <list>
#include <stack>
#include <set>

#define SMILEY '&' // :)
#define FROWNY '*' // :(

using namespace std;

char line[150];
int len;

bool parse(int p, int depth)
{
    for (; p < len; p++) {
        switch(line[p]) {
            case '(':
                depth++;
                break;
            case ')':
                if (depth <= 0) {
                    return false;
                }
                depth--;
                break;
            case SMILEY: // :)
                if (depth <= 0) {
                    // just use as smiley
                    break;
                } else {
                    // two options:
                    // - use as smiley
                    // - use as ')'
                    return parse(p + 1, depth) || parse(p + 1, depth - 1);
                }
                break;
            case FROWNY: // :(
                // two options:
                // - use as frowny
                // - use as '('
                return parse(p + 1, depth) || parse(p + 1, depth + 1);
                break;
        }
    }
    if (depth != 0) {
        return false;
    }
    return true;
}

// replace stuff
bool replace_stuff()
{
    bool correct = true;
    // copy line
    char stuff[150];
    strcpy(stuff, line);

    // fill the string first, with null bytes
    for (int i = 0; i < 150; i++) {
        line[i] = '\0';
    }

    // do stuffz
    int stuffLen = strlen(stuff);
    int j = 0;

    bool colon = false;

    for (int i = 0; i < stuffLen; i++) {
        switch (stuff[i]) {
            case ':':
                colon = true;
                break;
            case '(':
                if (colon) {
                    line[j++] = FROWNY;
                    colon = false;
                } else {
                    line[j++] = stuff[i];
                }
                break;
            case ')':
                if (colon) {
                    line[j++] = SMILEY;
                    colon = false;
                } else {
                    line[j++] = stuff[i];
                }
                break;
            default:
                colon = false;
                // do nothing, everything here is just stuff we do not need
                /*
                if (colon) {
                    newStuff[j++] = ':';
                    colon = false;
                }
                newStuff[j++] = stuff[i];
                */
                // check if correct char
                if (!stuff[i] == ' ' && !(stuff[i] >= 'a' && stuff[i] <= 'z')) {
                    correct = false;
                }
                break;
        }
    }
    return true;
}

void run(int cas)
{
    cin.getline(line, 150);
    // remove stuff we do not need
    bool ans = replace_stuff();

    // init vars
    len = strlen(line);

    //cerr << "LN: " << line << endl;

    ans = ans && parse(0, 0);

    cout << "Case #" << cas << ": ";
    if (ans) {
        cout << "YES";
    } else {
        cout << "NO";
    }
    cout << endl;
}

int main()
{
    char bla[10];
    int t;
    cin >> t;
    // ignore first line
    cin.getline(bla, 10);

    for (int i = 0; i < t; i++) {
        run(i + 1);
    }
    return 0;
}

beautiful_strings.cpp

#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <list>
#include <stack>
#include <set>

#define CHARS 26
#define LOW 'a'
#define HIGH 'z'
#define LOW_UPPER 'A'
#define HIGH_UPPER 'Z'

using namespace std;

char num[CHARS];

void reset()
{
    for (int i = 0; i < CHARS; i++) {
        num[i] = 0;
    }
}

// method to find the highest num
int findHighest()
{
    int highest = 0;
    for (int i = 1; i < CHARS; i++) {
        if (num[highest] < num[i]) {
            highest = i;
        }
    }
    return highest;
}

void run(int cas)
{
    reset();
    char line[550];

    cin.getline(line, 550);

    for (int i = 0; i < strlen(line); i++) {
        if (line[i] <= HIGH_UPPER && line[i] >= LOW_UPPER) {
            // uppercase, convert to lower
            //cerr << "char: " << line[i] << endl;
            line[i] -= LOW_UPPER;
            line[i] += LOW;

            //cerr << "converted: " << line[i] << endl;
        }

        if (line[i] >= LOW && line[i] <= HIGH) {
            // count this one
            num[line[i] - LOW]++;
        }
    }

    int ans = 0;

    // loop 26 times, decrease the beauty each time
    for (int b = 26; b >= 1; b--) {
        int highest = findHighest();
        ans += num[highest] * b;
        num[highest] = 0;
    }

    cout << "Case #" << cas << ": " << ans << endl;
}

int main()
{
    char bla[10];
    int t;
    cin >> t;
    // ignore first line
    cin.getline(bla, 10);

    for (int i = 0; i < t; i++) {
        run(i + 1);
    }
    return 0;
}

Facebook Hackercup Solutions.md

Disclaimer: I have no idea if this are indeed the correct answers. I just solved the exercises like this. I think that they are right though.

I have added my own code to this gist. It is ugly as hell, just like you can expect from code created in a contest like this.

Beautiful Strings

Difficulty: easy

It is simple to see that a greedy solution is good enough.

My algorithm for this:

• Count the number of times every char appears and initialize the answer to 0, and set x to 26
• Find the char that occurs the most, multiply by x, add to the answer.
• Set the number of occurences of that char to 0 (so we will not see it as the most occuring char again).
• Decrease x by 1
• Repeat until x is 0

Balanced Smileys

Difficulty: Moderate

This problem is a lot harder than Beatiful Strings. But with some insight, you should see that both emoticons (frowny face and smiley face) give you a choise when you encounter them. For the frowny face this is to either see it as a frowny face or as a '(' And for the smiley face this is to either see it as a smiley face or as a ')'. The truth is that it is impossible to know which to choose if you scan the string from the front to the back.

Thus, we need to scan the search space for this problem for a possible solution. To explain the concept, we will construct a 'decision tree' for the following example:

:( unhappy? or happy! :))

In the decision tree, every left child of a node, means we take it as its original form. And every right child means that we take it as a paren.

(take as emoticon)           :(          (take as parenthesis)
                           /    \
                          :)    :)
                         /  \  /  \
                         n  n  y  n

The string is only valid when we take the frowny face as a paren, and the smiley face as a smiley face.

While parsing the string, we ignore every char exept for ':' (which indicates a smiley), '(' and ')'. We keep a 'depth' parameter that keeps the depth of the nesting of parenthesis. And whenever we find a smiley, we recursively call the parse method twice. One time we do not adjust the depth (we take the emoticon as emoticon), and the second time we do adjust the depth (we take the emoticon as parenthesis).

Simplified version of my algorithm for this problem, implemented in C++:

// line : input
// p : pointer to current position in line
bool parse(int p, int depth)
{
    for (; p < len; p++) {
        switch(line[p]) {
            case '(':
                depth++;
                break;
            case ')':
                if (depth <= 0) {
                    return false;
                }
                depth--;
                break;
            case SMILEY: // :)
                if (depth <= 0) {
                    // just use as smiley
                    break;
                } else {
                    // two options:
                    // - use as smiley
                    // - use as ')'
                    return parse(p + 1, depth) || parse(p + 1, depth - 1);
                }
                break;
            case FROWNY: // :(
                // two options:
                // - use as frowny
                // - use as '('
                return parse(p + 1, depth) || parse(p + 1, depth + 1);
                break;
        }
    }
    if (depth != 0) {
        return false;
    }
    return true;
}

Find The Min

Difficulty: Moderate / Hard

In this problem it is very important that you read carefully. I've heard some people that looked over the fact that for m[i], you only need to look at the previous k values of m. Not all previous values.

First we have to calculate the sequence using the given PRNG. There is no smart way around this, it is just a means of delivering large input without producing an input file that is very large (which might give problems on slow connections).

When we have generated the first k values, it is time to tackle the problem itself. It is not very hard to generate value m[i] using the previous k values. What I did, is put all the previous values in a Binary-Search-Tree, and calculate the next value. Then I would pop the first value from the queue, and remove it from the Binary-Search-Tree.

Continously generating the next value is really easy, and will work perfectly for low values of n. However, when n gets larger, this will get painfully slow (and easily make your program run longer than 6 minutes). But, with some insight, we can see that the values of m[i] (with i > k), will repeat themselves every k+1 values. Thus now it is a matter of generating the first 2k+1 values. And then we give the value at position k + (n-2) % (k - 1) as the answer.

find_the_min.cpp

#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>
#include <queue>
#include <list>
#include <stack>
#include <set>

#define PRECISION 0xFFFFFFFF


using namespace std;

deque<long> m;
map<long,int> ma;

void printm(int k)
{
    cerr << k << ": [";
    cerr << m[0];

    for (int i = 1; i < k; i++) {
        cerr << ", " << m[i];
    }

    cerr << "]" << endl;
}

bool find(long num)
{
    return ma.find(num) != ma.end();
}

// add to 'm'
void add(long num)
{
    m.push_back(num);
    if (find(num)) {
        ma[num] = ma[num] + 1;
    } else {
        ma.insert(pair<long,int>(num, 1));
    }
}

// pop the front
long pop_front()
{
    long front = m.front();
    m.pop_front();
    if (find(front)) {
        if (ma[front] - 1 == 0) {
            ma.erase(front);
        } else {
            ma[front] = ma[front] - 1;
        }
    }
    return front;
}

void run(int cas)
{
    m.clear();
    ma.clear();
    long n, k, a, b, c, r;
    cin >> n >> k;
    cin >> a >> b >> c >> r;

    // calculate m upto k
    add(a);
    for (int i = 1; i < k; i++) {
        long next = (b * m[i-1] + c) % r;
        add(next);
    }

    // find the first value
    long next = 0;
    while (find(next)) {
        next++;
    }

    add(next);
    pop_front();

    //printm(k);

    bool change = true;

    for (int j = 0; change && j <= (n - 1) / (k + 1) && j <= PRECISION; j++) {
        change = false;
        next = 0;
        // get the next k + 1 values
        for (int i = 0; i < k + 1; i++) {
            //next = 0;
            // find the next value
            while (find(next)) {
                next++;
            }

            add(next);
            // remove the front, and take it as next when lower than current next
            long front = pop_front();
            if (front < next) {
                next = front;
            }
        }
        //printm(k);
        //cerr << "B: " << j << endl;
    }

    //printm(k);

    int find = (int) ((n - 2) % (k + 1));

    cout << "Case #" << cas << ": " << m[find] << endl;
}

int main()
{
    int t;
    cin >> t;

    for (int i = 0; i < t; i++) {
        run(i + 1);
    }
    return 0;
}

I think you have a typo in your tree for part 2?

Second problem can be solved way easier in O(n) by keeping track of minimal and maximal level of nesting we are at: https://gist.github.com/4660602

The code for first two problems in Haskell is a real beauty and really concise:

BeautifulStrings.hs

--Returns the frequency for each element in the input
frequencies xs = Map.elems $ Map.fromListWith (+) [(toLower c, 1) | c <- xs]

--Returns the maximum beauty value for an input string
beauty = sum . weight . sortDesc . frequencies . filter isLetter where
  weight = zipWith (*) [26,25..1]
  sortDesc = sortBy (flip compare)

BalancedSmileys.hs

isBalanced = isBalanced' 0

isBalanced' count _ | count < 0 = False
isBalanced' count [] = count == 0
isBalanced' count (':' : ')': rest) = isBalanced' count rest || isBalanced' count (')':rest)
isBalanced' count (':' : '(': rest) = isBalanced' count rest || isBalanced' count ('(':rest)
isBalanced' count ('(' : rest) = isBalanced' (count + 1) rest
isBalanced' count (')' : rest) = isBalanced' (count - 1) rest
isBalanced' count (c: rest) 
  | isLetter c || c == ' ' || c == ':' = isBalanced' count rest
isBalanced' _ _ = False

This was my Haskell for the first problem, maybe not quite as elegant :P

import qualified Data.Map as DM
import Data.List
import Data.Char
import Data.Function
import Control.Monad

freqMap fqmap [] = fqmap
freqMap fqmap (x:xs) = 
        case DM.lookup (toLower x) fqmap of 
            (Just r) -> freqMap (DM.insert (toLower x) (r+1) fqmap) xs
            Nothing -> freqMap (DM.insert (toLower x) 1 fqmap) xs

bnums = [26,25..1]

beauties fqmap = sum [k*b | ((c,k),b) <- zip (reverse (sortBy (compare `on` snd) $ DM.toList fqmap)) bnums]

genBeauties = beauties . (freqMap DM.empty) . (filter isLetter)

3rd solution seems to have an issue with repeated elements in the LCG, you might want to look into it.

snarl • check min-pieter
    big
 ⎻⎻⎻⎻⎻⎻⎻⎻⎻
Case #1: 488

---
Case #1: 488

    breaker
 ⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻
Case #1: 1
Case #2: 0
Case #3: 3
Case #4: 4
Case #5: 0
Case #6: 1
Case #7: 0
Case #8: 3
Case #9: 4
Case #10: 0
Case #11: 1

---
Case #1: 1
Case #2: 2
Case #3: 3
Case #4: 4
Case #5: 0
Case #6: 1
Case #7: 2
Case #8: 3
Case #9: 4
Case #10: 0
Case #11: 1
doesn't match

    full
 ⎻⎻⎻⎻⎻⎻⎻⎻⎻⎻
^C
snarl • cat tests/min/breaker.in 
11

5 4   0 0 0 1
6 4   0 0 0 1
7 4   0 0 0 1
8 4   0 0 0 1
9 4   0 0 0 1
10 4  0 0 0 1
11 4  0 0 0 1
12 4  0 0 0 1
13 4  0 0 0 1
14 4  0 0 0 1
15 4  0 0 0 1
snarl • 

Try ":(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:())))))))))))))))))))))))))))))))))" as an input to balanced smileys.

http://ideone.com/eDMpd3 Solves #2 in O(n)

Does that Haskell solution work for this input: "(:))" ?

tjeezy, I get False, which seems like the correct answer. Actually, I guess you could interpret it as a smiley, so no, it doesn't work.

hex539, nice catch. It's not actually because of repeated elements (those are counted correctly) but rather an off-by-one in the main loop.

Can be fixed by:

1. getting rid of the "find the first value" computation
2. not popping after finding the last value

so that before printing the answer, our deque contains elements m[k] through to m[2k] (inclusive), which is (k+1) elements in all.

Then the answer is just m[n % (k+1)] (simplified from m[(n - 1 - k) % (k+1)])

EDIT: I missed one thing (which does indeed have to do with repeated numbers): we have to check that find(front) is false before doing next = front

Some other notes:

At least for me, "long" is still 32-bits so others trying this out may need to change to "long long". You only need it when computing b * m[i-1] + c though.

It gets slow if next = front decreases next by a lot, but it can be avoided by not forgetting how far we got with next. IOW we add(front) if it is less than next, but after that we'll continue increasing next from where we left off (until we get interrupted by another small front). That way we do O(k) work in total.

@pedrosorio: Yeah, I have noticed that problem by now. Apparently facebook did not include that in the test cases. But I think memoization would be enough to solve that problem.