Wednesday, January 30, 2013

Dual Boot Incorrect Clock


Windows / Linux dual boot incorrect system time problem

I always encounter this problem after new installation of Windows / Linux on my PC. If I switch between OSs, Windows shows GMT time instead of local time, although when I check settings, it shows me that local time setting is still OK, for example, I can still see GMT+6 is selected, but the time is wrong. I keep forgetting the fix, so I will be noting it down here for future fix.

After a little bit Google-ing, I found the reason behind this is, Linux or BSD based OSs set BIOS time to UTC / GMT, while Windows sets the clock to local time. So to fix this, either we need to tell Windows to store universal time, or tell Linux to store local time. However, seems like doing this on Windows is easier using "regedit". we will need to add a flag "RealTimeIsUniversal" so that Windows acts accordingly. There is a similar flag which can be used in Linux as well.

For windows fix: go to start menu and write "regedit" (without quotes) on the search box, and hit enter. The regedit.exe will start. Now from left side, navigate to

HKEY_LOCAL_MACHINE -> SYSTEM -> CurrentControlSet -> Control -> TimeZoneInformation
Now right click on an empty spot on the right side panel and select
New -> DWORD (32bit) Value
Give the name "RealTimeIsUniversal" (without quotes), double click on it, and give the value 1, done! Next time you start Windows after using Linux, the time setting should be fine, at least working fine for me. Also, I've picked this solution instead of changing Linux flags, because, I feel like all clocks should be set to UTC time, so that it creates no problem when using internet.


Tuesday, January 29, 2013

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.