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;
}