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.

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)
    • You must think better, Michal…

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