Editorial of MindCoding 2017 Final 1

Approach #1

Start with the values [0, 1]. At each iteration, do the following:

• reverse the current list and append it to itself
• prepend each element in the first half with a 0
• prepend each element in the second half with a 1

The N^th iteration of this process generates all N bit configurations, in an order which respects the required property.

Haskell implementation

once applies a single iteration to a given list.
solve uses function composition to generate once composed to itself N-1 times, and applies the resulting function to the first iteration.

solve n = foldr (.) id (replicate (n-1) once) ["0", "1"]
once xs = map ('0':) xs ++ map ('1':) (reverse xs)

main = do
    input <- getContents
    let n = read input :: Int

    sequence $ map putStrLn $ solve n

Approach #2

Start from the null configuration. Try each of the N possible bit flips, and keep track of previously encountered configurations. When a new configuration is found, repeat the same process for it. Stop when no new configuration can be found.

Note: a recursive implementation of this approach can result in a stack overflow.

The easiest solution to this problem is based on observations.

Let's start with a matrix containing just values of 1:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Each individual cell makes up a magic submatrix by itself. There are 256 such submatrices. Now try to change every other value into a 2, in a chessboard-like pattern:

1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

In this solution, we have fewer 1×1 submatrices, but there is the advantage that any value of 1 can be extended in 4 directions, creating multiple 1×2 and 2×1 submatrices. This approach results in 608 magic submatrices, which is considerably closer to our target.

A natural step is to add larger values. For instance, we can recreate the following 4×4 pattern, resulting in 712 submatrices:

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

A better solution is to use the following pattern instead, where each line/column contains a permutation of [1, 2, 3, 4]:

1 2 3 4
3 4 1 2
2 1 4 3
4 3 2 1

This generates 832 magic submatrices:

• 64 submatrices of size 1×1
• 64 submatrices of size 1×2
• 56 submatrices of size 1×3
• 56 submatrices of size 3×1
• 176 submatrices of size 2×2
• 208 submatrices of size 1×4
• 208 submatrices of size 4×1

Given a subreddit, determining all days in which it can be declared Subreddit of the Day is a trivial task.

Now, consider the following:

• S = the set of all N subreddits
• D = the set of all K days
• an edge between i ∈ S and j ∈ D denotes the fact that subreddit i can be declared Subreddit of the Day on day j.

Using this model, the problem becomes equivalent to finding a maximum matching in a bipartite graph.

Further reading: infoarena.