# Google Code Jam (2)

This was the first round when I had prepared some templates prior the contest.

My goal was to win the T-shirt, i.e. be in the first 1000 contestants. I was sligthly surprised that there were four tasks instead of ordinary three — I assigned uniformly 37 minutes per task.

## Problem A (Pegman)

I mapped the problem to a graph problem, thought I’d implement it with some
graph representation, then I realized I could use the existing grid and began
implementing. I spent inappropriate amount of time on input parsing (skipping
EOL characters using `cint >> EOL`

, which was not necessary).

After submitting the problem A, I was somewhere around 1200th place and I was a bit behind my schedule (it took me ~50 minutes).

## Problem B (Kiddie Pool)

First I didn’t like as I saw floating point numbers in the sample output, then I realized it wouldn’t be that bad. The general solution reminded me a sum of a subset problem (may be it is not), on the other hand small solution (with two pipes only) had a closed form solution. I had it almost right, except I forgot special case when there were two pipes with same temperature. That cost me few minutes.

After submitting the problem B, I was somewhere around 550th place. Simple solution took me ~25 minutes. I decided to skip problem C (it offered only a few points, I didn’t even read the task) and attempted to solve problem D.

Update 2015-08-02: Later I found out, it is actually a linear programming problem. How ignorant was I.

## Problem D (Mathdrum)

I thought even small input would be impossible to bruteforce ($4^{36} \approx 10^{21}$, actually only $3^{36} \approx 10^{17}$). However, I thought some pruned backtracking could be feasible. I spent some time implementing, however I wasn’t able to debug it to working version (I didn’t reduce no. of unique solution due to cyclic shift and for more than 2 row it ran too long and probably not correctly). I didn’t submit anything.

When deadline passed, I was 1226th and when wrong solution of large input were reconciled, I moved to 1092nd place. That’s less than 100 place from my (pre)set goal. I was never so far in GCJ before, I can be delighted by making progress since first years I participated. On the other hand, there are hundreds of better programmers.