CF2201G Codeforces Heuristic Contest 1001

There is a graph of $ n^2 $ vertices, where vertices are labeled by integer pairs $ (r,c) $ such that $ 1 \le r,c \le n $ . Vertices $ (r_1,c_1) $ and $ (r_2,c_2) $ are directly connected if and only if $ (r_1-r_2)^2+(c_1-c_2)^2=\color{red}{13} $ . This graph is called the Zebra Graph of dimensions $ n \times n $ . Please find a subset of vertices $ S $ in the Zebra Graph of dimensions $ n \times n $ , which satisfies the following condition. - The graph induced $ ^{\text{∗}} $ by the subset $ S $ is isomorphic to a cycle graph of at least $ \left\lfloor{\frac{n^2}{e}}\right\rfloor $ vertices $ ^{\text{†}} $ . It can be shown that such a subset of vertices exists under the constraints of this problem. $ ^{\text{∗}} $ The induced graph of a subset of vertices $ X $ is a graph that contains all vertices in $ X $ and all edges whose both endpoints are in $ X $ . $ ^{\text{†}} $ Here, $ e $ is the mathematical constant equal to the limit $ \lim \limits_{n \to \infty} \left ({1 + \frac{1}{n}} \right )^n \approx 2.71828182 $ . Note that the value of $ \frac{1}{e} $ is approximately $ 0.36787944 $ .

The first and only line of input contains a single integer $ n $ ( $ n\in \{5,1001\} $ ). There are only two input files for this problem: - The first input file (the example input) has $ n=5 $ ; - The second input file has $ n=1001 $ . Hacks are disabled for this problem.

Output $ n $ lines, each containing a string $ s_i $ of length $ n $ denoting the $ i $ -th row of the graph. If the vertex $ (r,c) $ is an element of $ S $ , then the $ c $ -th letter of $ s_r $ should be '1'. Otherwise, the $ c $ -th letter of $ s_r $ should be '0'. If there are multiple solutions, print any of them.

For the example output, the induced graph corresponding to the subset $ S $ is shown below. This graph is isomorphic to the cycle graph $ C_{16} $ consisting of $ 16 $ vertices. As $ 16 \ge \left\lfloor{\frac{n^2}{e}}\right\rfloor = 9 $ , the output satisfies the problem's condition.