JYPnation
Contest: Codeforces Round 633 (Div. 1)
Difficulty rating: 3500
Tags: graphs

Due to the success of TWICE, JYP Entertainment has earned countless money and emerged as the biggest entertainment firm by market capitalization. Therefore, the boss, JYP, has decided to create a new nation and has appointed you to provide a design diagram.

The new nation consists of $$$n$$$ cities and some roads between them. JYP has given some restrictions:

- To guarantee efficiency while avoiding chaos, for any $$$2$$$ different cities $$$A$$$ and $$$B$$$, there is exactly one road between them, and it is one-directional. There are no roads connecting a city to itself.
- The logo of rivaling companies should not appear in the plan, that is, there does not exist $$$4$$$ distinct cities $$$A$$$,$$$B$$$,$$$C$$$,$$$D$$$ , such that the following configuration occurs.

JYP has given criteria for your diagram. For two cities $$$A$$$,$$$B$$$, let $$$dis(A,B)$$$ be the smallest number of roads you have to go through to get from $$$A$$$ to $$$B$$$. If it is not possible to walk from $$$A$$$ to $$$B$$$, $$$dis(A,B) = 614n$$$. Then, the efficiency value is defined to be the sum of $$$dis(A,B)$$$ for all ordered pairs of distinct cities $$$(A,B)$$$.

Note that $$$dis(A,B)$$$ doesn't have to be equal to $$$dis(B,A)$$$.

You have drawn a design diagram that satisfies JYP's restrictions. Find the sum of $$$dis(A,B)$$$ over all ordered pairs of cities $$$(A,B)$$$ with $$$A\neq B$$$.

Note that the input is given in compressed form. But even though it is compressed, you'd better use fast input.

Input format:
The first line contains a single integer $$$n$$$ ($$$4 \le n \le 8000$$$, $$$n \equiv 0 \pmod{4}$$$) — the number of cities.

A binary matrix is encrypted in the following format. Each of $$$n$$$ next lines contains $$$\frac{n}{4}$$$ one-digit hexadecimal numbers (that is, these numbers can be represented either as digits from $$$0$$$ to $$$9$$$ or as uppercase Latin letters from $$$A$$$ to $$$F$$$). Binary representation of each of these numbers denotes next $$$4$$$ elements of the matrix in the corresponding row. For example, if the number $$$B$$$ is given, then the corresponding elements are $$$1011$$$, and if the number is $$$5$$$, then the corresponding elements are $$$0101$$$.

After you obtain the decrypted binary matrix, the $$$j$$$-th character of the $$$i$$$-th row is $$$1$$$ if the one-directional road between cities $$$i$$$ and $$$j$$$ is directed from $$$i$$$ to $$$j$$$, and $$$0$$$ otherwise. It is guaranteed that the graph satisfies the restrictions mentioned above.

Output format:
Output one integer, representing the sum of $$$dis(A,B)$$$ over all ordered pairs of cities $$$(A,B)$$$ with $$$A\neq B$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Note:
The first example corresponds to the matrix:

$$$\begin{matrix} 0111 \\ 0010 \\ 0001 \\ 0100 \\ \end{matrix}$$$

Which corresponds to this graph:

$$$dis(1,2)=dis(1,3)=dis(1,4)=dis(2,3)=dis(3,4)=dis(4,2)=1$$$

$$$dis(2,4)=dis(4,3)=dis(3,2)=2$$$

$$$dis(2,1)=dis(3,1)=dis(4,1)=2456$$$

Therefore the answer for the diagram is $$$7380$$$.

Example input:
4
7
2
1
4

Example output:
7380

Example input:
8
7F
3F
1F
0C
06
03
11
18

Example output:
88464

Editorial:
The solution contains several tricky observations, but its not hard to prove each of them seperately, so I will mention only the key points of the solution and proof.
Firstly, we should repeatedly remove points that have no in-degree. We can calculate their contribution easily.
For a node $$$x$$$, define $$$in(x)$$$ to be the set of nodes $$$u$$$ that $$$u \rightarrow x$$$ exists.
Lemma 1: $$$in(x) \cup {x}$$$ has no cycles for any node $$$x$$$.
Let's pick $$$X$$$ to be the node with maximum in-degree.
Let $$$P$$$ = $$$in(X) \cup {X}$$$, and let $$$Q$$$ = $$$Z \setminus P$$$, where $$$Z$$$ is the set of all vertices.
Lemma 2: There exist nodes $$$U \in Q$$$,$$$V \in P$$$, such that $$$U \rightarrow V$$$ exists.
Let $$$R$$$ = $$$in(V) \cap Q$$$, and let $$$S$$$ = $$$Q \setminus R$$$
Lemma 3: For all nodes $$$A \in S$$$,$$$B \in R$$$, $$$A \rightarrow B$$$ exists.
Lemma 4: $$$S$$$ has no cycles, $$$R$$$ has no cycles.
Lemma 5: $$$P$$$ has no cycles, $$$Q$$$ has no cycles.
That means we have partitioned the graph into two sets of nodes, where each set is completely ordered.
Lets label the nodes in $$$P$$$ by $$$P_i$$$ where $$$i$$$ is an integer from $$$1$$$ to $$$|P|$$$, such that for two nodes $$$P_i$$$ and $$$P_j$$$, $$$P_j \rightarrow P_i$$$ exists iff $$$j>i$$$.
Label nodes in $$$Q$$$ by $$$Q_i$$$ in similar manner.
Define $$$inP(x)$$$ to be the set of nodes $$$u \in P$$$ that $$$u \rightarrow x$$$ exists.
Define $$$inQ(x)$$$ to be the set of nodes $$$u \in Q$$$ that $$$u \rightarrow x$$$ exists.
Lemma 6a: If $$$|inQ(P_i)| = |inQ(P_j)|$$$ then $$$inQ(P_i) = inQ(P_j)$$$.
Lemma 6b: If $$$|inP(Q_i)| = |inP(Q_j)|$$$ then $$$inP(Q_i) = inP(Q_j)$$$.
Final observations:
• $$$dis(P_i,P_j)=1$$$ iff $$$i>j$$$
• $$$dis(P_i,P_j)=2$$$ iff $$$i<j$$$ and $$$|inQ(P_i)| \neq |inQ(P_j)|$$$
• $$$dis(P_i,P_j)=3$$$ iff $$$i<j$$$ and $$$|inQ(P_i)| = |inQ(P_j)|$$$
• $$$dis(Q_i,Q_j)=1$$$ iff $$$i>j$$$
• $$$dis(Q_i,Q_j)=2$$$ iff $$$i<j$$$ and $$$|inP(Q_i)| \neq |inP(Q_j)|$$$
• $$$dis(Q_i,Q_j)=3$$$ iff $$$i<j$$$ and $$$|inP(Q_i)| = |inP(Q_j)|$$$
• $$$dis(P_i,Q_j)+dis(Q_j,P_i)=3$$$
Finally, we can count the answer in $$$O(N^2)$$$ by the above observations.