Part 2: Problem A in unnamed language

## C small

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.

## No comments :

Post a Comment