Hacker Cup 2013 Qualification

Facebook Hacker Cup 2013, Qualification Round

It was a 72 hours contest, and solving at least one problem was enough to qualify for next round. As expected for qualification round, problems were quite easy. Problem statements are here.

Problem A: Beautiful strings: This was the 20 points problem. Quite elementary level. Just count the occurrences of each letter, then assign highest value to most frequent one, next highest value to next most frequent one and so on..

#include <cstdio>
#include <cstring>
#include <cctype>

int main() {
    int test, cs, i, sum;
    char buff[1024];
    int cnt[26];
    //freopen("beautiful_strings.txt", "r", stdin);
    //freopen("beautiful_strings.out", "w", stdout);
    scanf("%d", &test);
    gets(buff);
    for(cs = 1; cs <= test; cs++) {
        gets(buff);
        memset(cnt, 0, sizeof cnt);
        for(i = 0; buff[i]; i++) if(isalpha(buff[i])) cnt[tolower(buff[i]) - 'a']++;
        sort(cnt, cnt + 26);
        for(sum = 0, i = 26; i; i--) sum += cnt[i-1] * i;
        printf("Case #%d: %d\n", cs, sum);
    }
    return 0;
}

Problem B: Balanced Smileys: This was the 35 points problem. Generally a simple dynamic programming problem, however can also be solved using regular expressions as the expected answer is only YES or NO. For dynamic programming approach, we only need two states, index and sum, here, index is the position in the given string, and sum is the parenthesis weight so far. To find weight, for a '(', we add +1 and for a ')' we add -1, all the other characters are balanced, hence we add 0 for those. When we find a ':' followed by any of the parenthesis, we can make two decisions, either skip next parenthesis, or account it.

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

const int MAX = 128;

char str[MAX];
int dp[MAX][MAX], len;

int solve(int pos, int sum) {
    if(pos == len) return sum;
    int &ret = dp[pos][sum];
    if(ret != -1) return ret;
    if(str[pos] == '(') ret = solve(pos + 1, sum + 1);
    else if(str[pos] == ')') {
        if(sum > 0) ret = solve(pos + 1, sum - 1);
        else ret = INT_MAX;
    }
    else if(str[pos] == ':' && pos + 1 < len && (str[pos+1] == '(' || str[pos+1] == ')')) {
        ret = min(solve(pos+2, sum), solve(pos+1, sum));
    }
    else ret = solve(pos + 1, sum);
    return ret;
}

int main() {
    int test, cs;
    //freopen("balanced_smileys.txt", "r", stdin);
    //freopen("balanced_smileys.out", "w", stdout);
    scanf("%d", &test);
    gets(str);
    for(cs = 1; cs <= test; cs++) {
        len = strlen(gets(str));
        memset(dp, -1, sizeof dp);
        if(!solve(0, 0)) printf("Case #%d: YES\n", cs);
        else printf("Case #%d: NO\n", cs);
    }
    return 0;
}

Problem C: Find the Min: 45 points problem, and supposed to be hardest in this round. By playing around with the given series (or by applying some sense of pegionhole principle) we can find that, except for the first k+1 terms, the rest of the series is consists of repeating (k+1) terms, and these k+1 values will be always in range [0, k]. So we first find first 2k+2 terms of the series, and use modular arithmetic to find the position of nth term in this series.

#include <cstdio>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

typedef __int64 i64;

const int MAX = 1 << 18;

i64 m[MAX];
set< i64 > S;
map< i64, int > M;

int main() {
    int test, cs, n, k, i;
    i64 a, b, c, r;
    //freopen("find_the_min.txt", "r", stdin);
    //freopen("find_the_min.out", "w", stdout);
    scanf("%d", &test);
    for(cs = 1; cs <= test; cs++) {
        S.clear(); M.clear();
        scanf("%d %d %I64d %I64d %I64d %I64d", &n, &k, &a, &b, &c, &r);
        b %= r, c %= r; m[0] = a;
        for(i = 1; i < k; i++) m[i] = ((b * m[i-1]) % r + c) % r;
        for(i = 0; i < k; i++) M[m[i]]++;
        for(i = 0; i <= k; i++) S.insert(S.end(), (i64)i);
        for(i = 0; i < k; i++) S.erase(m[i]);
        for(i = k; i < 2*k+2; i++) {
            m[i] = *S.begin();
            M[m[i]]++; M[m[i-k]]--;
            S.erase(S.begin());
            if(!M[m[i-k]]) S.insert(m[i-k]);
        }
        printf("Case #%d: %I64d\n", cs, m[n % (k+1) + k+1 - 1]);
    }
    return 0;
}

Solved all three, now waiting for the score, not sure if I made any stupid mistake but the algorithms look fine to me.

Edit: Yes, all three passed, looking forward to what next round brings.