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
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
for i := 1 to T do begin
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.