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
   CONST_I = 2;
   CONST_J = 4;
   CONST_K = 6;
var
   i, j, n, left, curr : Integer;
   right : Array[0..100000] of Integer;
   t : Array[0..7,0..7] of Integer = (
       (0,1,2,3,4,5,6,7),
       (1,0,3,2,5,4,7,6),
       (2,3,1,0,6,7,5,4),
       (3,2,0,1,7,6,4,5),
       (4,5,7,6,1,0,2,3),
       (5,4,6,7,0,1,3,2),
       (6,7,4,5,3,2,1,0),
       (7,6,5,4,2,3,0,1)
   );
   inputInts: Array[0..99999] of Integer;
   
    function ch2index(ch: Char): Integer;
    begin
        ch2index := CONST_K;
        if ch = 'i' then ch2index := CONST_I;
        if ch = 'j' then ch2index := CONST_J;        
    end;

begin
    
    n := Length(s);
    solution := 'NO';
    for i:=1 to n do begin
        inputInts[i - 1] := ch2index(s[i]);
    end;
    right[n] := 0;
    for i := n - 1 downto 0 do begin
        right[i] := t[inputInts[i]][right[i+1]];
    end;
    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';
            end;
        end;
        left := t[left][inputInts[i]];
    end;
end;


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

The end

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