StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I'll attach what I have. Same as yours, alas, time is basically <code>O(n**3)</code>. But at least it avoids recursion (etc), so won't blow up when you get near a million ;-) Note that this returns the best vector found, not the count; e.g.,</p> <pre><code>>>> solve(23) [6, 0, 11, 0, 1, 0, 0, 10, 0, 5, 0, 9, 0, 3, 0, 0, 8, 0, 4, 0, 7, 0, 2] </code></pre> <p>So it also shows the order in which the 1 bits were chosen. The easiest way to get the count is to pass the result to <code>max()</code>.</p> <pre><code>>>> max(solve(23)) 11 </code></pre> <p>Or change the function to return <code>maxsofar</code> instead of <code>best</code>.</p> <p>If you want to run numbers on the order of a million, you'll need something radically different. You can't even afford quadratic time for that (let alone this approach's cubic time). Unlikely to get such a huge <code>O()</code> improvement from fancier data structures - I expect it would require deeper insight into the mathematics of the problem.</p> <pre><code>def solve(n): maxsofar, best = 1, [1] + [0] * (n-1) # by symmetry, no use trying starting points in last half # (would be a mirror image). for i in xrange((n + 1)//2): v = [0] * n v[i] = count = 1 # d21[i] = distance to closest 1 from index i d21 = range(i, 0, -1) + range(n-i) while 1: d, j = max((d, j) for j, d in enumerate(d21)) if d >= 2: count += 1 v[j] = count d21[j] = 0 k = 1 while j-k >= 0 and d21[j-k] > k: d21[j-k] = k k += 1 k = 1 while j+k < n and d21[j+k] > k: d21[j+k] = k k += 1 else: if count > maxsofar: maxsofar = count best = v[:] break return best </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload