Beautiful League
Contest: Codeforces Round 604 (Div. 1)
Difficulty rating: 2700
Tags: constructive algorithms, flows, graph matchings

A football league has recently begun in Beautiful land. There are $$$n$$$ teams participating in the league. Let's enumerate them with integers from $$$1$$$ to $$$n$$$.

There will be played exactly $$$\frac{n(n-1)}{2}$$$ matches: each team will play against all other teams exactly once. In each match, there is always a winner and loser and there is no draw.

After all matches are played, the organizers will count the number of beautiful triples. Let's call a triple of three teams $$$(A, B, C)$$$ beautiful if a team $$$A$$$ win against a team $$$B$$$, a team $$$B$$$ win against a team $$$C$$$ and a team $$$C$$$ win against a team $$$A$$$. We look only to a triples of different teams and the order of teams in the triple is important.

The beauty of the league is the number of beautiful triples.

At the moment, $$$m$$$ matches were played and their results are known.

What is the maximum beauty of the league that can be, after playing all remaining matches? Also find a possible results for all remaining $$$\frac{n(n-1)}{2} - m$$$ matches, so that the league has this maximum beauty.

Input format:
The first line contains two integers $$$n, m$$$ ($$$3 \leq n \leq 50, 0 \leq m \leq \frac{n(n-1)}{2}$$$) — the number of teams in the football league and the number of matches that were played.

Each of $$$m$$$ following lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$) denoting that the $$$u$$$-th team won against the $$$v$$$-th team. It is guaranteed that each unordered pair of teams appears at most once.

Output format:
Print $$$n$$$ lines, each line having a string of exactly $$$n$$$ characters. Each character must be either $$$0$$$ or $$$1$$$.

Let $$$a_{ij}$$$ be the $$$j$$$-th number in the $$$i$$$-th line. For all $$$1 \leq i \leq n$$$ it should be true, that $$$a_{ii} = 0$$$. For all pairs of teams $$$i \neq j$$$ the number $$$a_{ij}$$$ indicates the result of the match between the $$$i$$$-th team and the $$$j$$$-th team:

- If $$$a_{ij}$$$ is $$$1$$$, the $$$i$$$-th team wins against the $$$j$$$-th team;
- Otherwise the $$$j$$$-th team wins against the $$$i$$$-th team;
- Also, it should be true, that $$$a_{ij} + a_{ji} = 1$$$.

Also note that the results of the $$$m$$$ matches that were already played cannot be changed in your league.

The beauty of the league in the output should be maximum possible. If there are multiple possible answers with maximum beauty, you can print any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The beauty of league in the first test case is equal to $$$3$$$ because there exists three beautiful triples: $$$(1, 2, 3)$$$, $$$(2, 3, 1)$$$, $$$(3, 1, 2)$$$.

The beauty of league in the second test is equal to $$$6$$$ because there exists six beautiful triples: $$$(1, 2, 4)$$$, $$$(2, 4, 1)$$$, $$$(4, 1, 2)$$$, $$$(2, 4, 3)$$$, $$$(4, 3, 2)$$$, $$$(3, 2, 4)$$$.

Example input:
3 1
1 2

Example output:
010
001
100

Example input:
4 2
1 2
1 3

Example output:
0110
0001
0100
1010

Editorial:
Firstly, Let's calculate the number of non-beautiful triples given all result of matches. It is obvious that for each non-beautiful triple $$$(A, B, C)$$$ there exactly is one team that wins over the others. So if a team $$$A$$$ wins $$$k$$$ other teams $$$B_1, B_2,\ldots, B_k$$$ then team A corresponds to $$$\frac{k\cdot (k - 1)}{2}$$$ non-beautiful triple $$$(A, B_i, B_j)$$$. If we define $$$(p_1, p_2,\ldots, p_n)$$$ as the number of wins of $$$n$$$ teams. Then the number of non-beautiful triples will be $$$\frac{p_1\cdot (p_1 - 1) + p_2\cdot (p_2 - 1) +\ldots+ p_n\cdot (p_n - 1)}{2}$$$. Notice that $$$p_1 + p_2 +\ldots+ p_n = \frac{n\cdot (n - 1)}{2}$$$. So we only need to minimize the square sum: $$$p_1^2 + p_2^2 +\ldots+ p_n^2$$$.
The remain can be solved easily by Mincost-Maxflow:
• Creating source $$$S$$$, sink $$$T$$$, each 'match node' for each match haven't played yet, each 'team node' for each team.
• Add an edge between source $$$S$$$ and each 'match node' with capacity $$$1$$$ cost $$$0$$$.
• Add an edge between each 'match node' and each of two 'team nodes' with capacity $$$1$$$ cost $$$0$$$.
• Assuming, after $$$m$$$ matches played, $$$i$$$-th team wins $$$q_i$$$ matches. We add $$$n - q_i - 1$$$ edges between the $$$i$$$-th 'team node' and sink $$$T$$$ with capacity $$$1$$$ and costs $$$2\cdot q_i + 1, 2\cdot q_i + 3,\ldots, 2\cdot n - 1$$$. The min cost after run Mincost-Maxflow plus $$$q_1^2 + q_2^2 +\ldots+ q_n^2$$$ will give us the minimal square sum.
Base on Mincost-Maxflow idea, we can solve in more sophisticated way. At any moment, we will try to pick a team with minimal number of wins. Then we try to give it one more win by setting result of a match (that haven't used so far) and possibly changing results of a path of matches to keep the number of win of others. If not pick next one and so on.
Complexity: $$$O(N^4)$$$.