Saturday, April 11, 2015

Google Codejam 2015 Qualification Round : Part 4: C small

Part 1: Problem D in Emily

Part 2: Problem A in unnamed language

Part 3: Problem B in Julia

C small

Problem statement

Unlike the other Small problems I didn't really think of a solution of this right away. I had to take a day to do it.

The trick to the problem is that we can find in `O(n)` the product of the `x` first left-most numbers (for all `x`). And the same for the right-most numbers. So imagine if we had a substring `[a,b]`. If left[a-1] is equal to `i` and right[b+1] is `k` then all that we need to learn is if the substring is equal to `j`. If we can answer that question in `O(n^2)`, we have the whole problem solved. And we totally can answer that question! We just need to start with an `a`, then `b = a` and calculate the product for `b = a`, then it is easy to calculate the product when `b = a + 1`, just multiply one more number. And so and so for `b = a + 2`, etc.

The only extra complication is doing the multiplication with `i`, `j`, `k` and the signs... Well, really there are 8 distinct numbers, and we can easily index them and make a table, multiplying this index with this other index yields this other index...

So I tried free pascal. I used to code in Pascal, and I hated it. Now I don't really remember much. So I guess it counts? I had to relearn Pascal a bit. But I reached a solution... which failed. And then it failed again and again... I really thought the problem was in that big hardcoded matrix, and spent hours trying to think of a mistake there. Turns out that free Pascal's Strings are limited to 255 characters (What the hell, free pascal?). You have to use AnsiString for limitless strings.

program C;

function solution(s : AnsiString): String;
   CONST_I = 2;
   CONST_J = 4;
   CONST_K = 6;
   i, j, n, left, curr : Integer;
   right : Array[0..100000] of Integer;
   t : Array[0..7,0..7] of Integer = (
   inputInts: Array[0..99999] of Integer;
    function ch2index(ch: Char): Integer;
        ch2index := CONST_K;
        if ch = 'i' then ch2index := CONST_I;
        if ch = 'j' then ch2index := CONST_J;        

    n := Length(s);
    solution := 'NO';
    for i:=1 to n do begin
        inputInts[i - 1] := ch2index(s[i]);
    right[n] := 0;
    for i := n - 1 downto 0 do begin
        right[i] := t[inputInts[i]][right[i+1]];
    left := 0;
    for i := 0 to n-1 do begin
        curr := 0;
        for j := i to n-1 do begin
            curr := t[curr][inputInts[j]];
            if (left = CONST_I) and (curr = CONST_J) and (right[j+1] = CONST_K) then begin
                solution := 'YES';
        left := t[left][inputInts[i]];

   X, L : Integer;
   w : AnsiString;
   ww : AnsiString;
   T : Integer;
   i,j : Integer;
    for i := 1 to T do begin
        ww := '';
        for j := 1 to X do begin
            ww := ww + w;
        writeln('Case #',i,': ', solution(ww) );

The end

I qualified! This was a lot more fun and far more stressful than usual.

No comments :