| Task | #23 |
|---|---|
| Position | 4 |
| Score | 1,329 |
| Best Score | 1,209 |
| Points | 0.910 |
Problem Statement
Given a square of 10000 * 10000 uint8 elements with values 0 and 1 in STDIN. Find
and output the value of the side of the maximum square of 1’s with side n to
STDOUT, where n > 1. Example:
0, 1, 0, 1, 1
0, 1, 1, 1, 1
0, 0, 1, 0, 0
1, 0, 1, 1, 0
valid answer is
2
Input Generator
Ported the input generator specified above
Solution Sketch
This problem is the canonical example of Median Hacking. Since 50 is the solution such a large number of times, toss a slightly head-biased coin. If it turns up heads, print 50 and exit. If not, run the naive solution.
My naive solution is also an approximation. Go through the input, and if you find a contiguous segment of ones of length ‘m’ > 50 on row ‘n’, stride and check rows n+1, n+2, n+4, n+8, …, n+2^(log2(m)) (you can also do this randomly, I thought this was good enough). The solution is the minimum of consecutive ones encountered on those rows.
Thoughts
The success rate of this strategy is abysmal. There’s probably cleverer stuff you can do, such as striding some subset of diagonals of the input. I’ve noticed others with a low score have a very high success rate, so there has to be a better way of doing this.
I’m not a fan of this challenge. It’s not robust enough, neither does it stress actual computation (eg the CPU or the memory hierarchy). System noise dominates the leaderboard at this point.