# Google Code Jam (1B)

Purpose of this post is to summarize mistakes I made and take lessons for next time.

Qualification round was not easy, however limits were quite benevolent and thus I qualified for the next round. First (1A) attempt was not for my timezone, therefore I joined 1B.

## Problem A. Counter Culture

https://code.google.com/codejam/contest/8224486/dashboard

- First idea was BFS in graph where nodes are numbers and there are either direct (+1) or reverse (digits reverse) edges.
- I implemented and debugged the BFS (took some time).
- Realized it’s not very efficient (for input numbers > 10000).
- Then thought about it once again and it seemed to me that greedy approach is valid.
- I drafted the algo, tested in on test input until I got correct results.
- Then I felt confident enough to try the small dataset, there were some errors though…
- Fortunately, I kept the original BFS version that was correct (slow though) and I was able to find some discriminative testcases for the versions and could debug the latter version and attempt to submit both small and large input (the algo was quite fast).
- This took me 2 hours in total.

## Problem B. Noisy Neighbors

https://code.google.com/codejam/contest/8224486/dashboard#s=p1

**30 minutes remaining**- Small input was apparently suitable for brute-force solution, so I kept that on mind and decided to think about better solution.

**20 minutes remaining**- OK, I didn’t figure out anything better so at least naïve brute-force could be sufficient.
- I started implementing, from scratch (input parsing, header includes, …)

**4 minutes remaining**- I got compilable, runnable version, however it fails on the test data.
- When looking for mistakes I found some conditions that I forgot to implement (though having them on mind previously)

**30 seconds remaining**- I’m desperate, the solution is so simple and decomposed there cannot be any errors.
- It still gives wrong results, time is out, I’m angry.

**after contest**- Finally I found the mistakes:
- Off-by-one error that was caused by my insecurity about some boundaries and I thought making them larger (+1) wouldn’t change the solution. Obviously it did and without that +1 it was correct.
- I was using
`sizeof`

as if it returned size in bits instead of bytes.

- Finally I found the mistakes:

## Lessons learned

- Prepare some templates with boilerplate code (includes, usings,
`main`

) – it takes time and interrupts attention. - Better time management – 20 minutes is not enought to write and debug even simple solution (because of the stress).
- Stop refining solution that I know is inefficient and think about it once more (or have some pause, little distraction to refresh mind).
- What the heck was efficient solution for the Noisy Neighbors?
- Simple as breeze: chessboard pattern
- if
`N`

<`R*C / 2`

, I can distribute tenants without adjacency (chessboard pattern) - any neighbor that is more than the half goes to some field of the chessboard and it’s always 4 neighbors (or less on building borders)

- if
- You must think better, Michal…

- Simple as breeze: chessboard pattern

### Coding

- handy macros for debug prints
- rectangular grid via “move vectors”
- use global variables when it makes code more terse
- typedefs for common vectors (int, long long), pairs(?)
- macros for loops