StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>From a programming perspective this suggests a search that takes advantage of the symmetries of the rectangle to reduce search space. What follows is something of an extended hint.</p> <p>As the OP points out, a naive implementation would check all possible k-subsets of nodes, a size of C(nm,k).</p> <p>The amount of search space reduction depends on how symmetries are exploited. The square has symmetries of reflection and rotation, so for n=m there's an 8-fold symmetry group. If say n < m, then the lesser amount of symmetry gives a 4-fold group.</p> <p>A typical approach is to organize the possible k-subsets by a lexicographic ordering, so that a potential configuration is skipped when it's equivalent to one of earlier appearance in that ordering.</p> <p>But there are additional "wrap-around" symmetries to be exploited. Suppose the last row of the grid is moved to the top (along with any assignment of stones to its nodes). This transformation preserves the count of the 4-stone rectangles (though the exact sizes of those rectangles will differ).</p> <p>Indeed transposing two rows or two columns preserves the counts of 4-stone rectangles. Once you have that insight, can you see how to parameterize the search space more efficiently?</p> <p><strong>Added:</strong> Even though it's more of a math insight than programming, consider the number of 4-stone rectangles provided by a "full subrectangle", say r x c if rc < k. Consider the incremental number of extra rectangles provided by one more stone; by two more stones.</p>

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