The solution to this problem is concise but interesting, so we will first introduce the solution, and then explain the prerequisite.

The solution is quite simple. Let \(X = \sum_i A_i\). It is sufficient to solve the case where \(X\) is even.
Consider a edge-weighted undirected graph \(H\) with \(X\) vertices, defined as follows:

• Every vertex is labeled with an integer between \(1\) and \(N\).
  • Especially, there are exactly \(A_i\) labeled with an integer \(i\).
• There is an edge of weight \(0\) between any pair of vertices labeled with the same integer.
• There is an edge of weight \(1\) between any pair of vertices labeled \(i\) and \(j\) \((i \neq j)\) if and only if there is an edge \(i-j\) in \(G\).

Then, the problem can be solved by simply considering the minimum-weight perfect matching of \(H\)! In other words,

• If there is no minimum-weight perfect matching, then a good graph does not exist either;
• If there is a minimum-weight perfect matching, then the answer to the original problem coincides with the weight of a minimum-weight perfect matching.

Justifying the solution is not as difficult as coming up with \(H\), so we will omit the proof here.
Hence, the problem can be solved with a minimum-weight perfect matching algorithm. This runs in about \(\mathrm{O}(X^4)\) or \(\mathrm{O}(X^3)\) time (as described above), which is fast enough.

That concludes the solution. Next, we will describe a simple algorithm to find the weight of a minimum-weight perfect matching, which is necessary to solve the problem.

First, we will introduce a textbook algorithm. It is known that a minimum-weight perfect matching can be computed using an algorithm called Edmonds’ blossom algorithm in \(\mathrm{O}(N^3)\) time (where \(N\) is the number of vertices in the graph). The participants who solved the problem during the contest might probably have pasted this algorithm, or called an algorithm from a library, such as networkx module in Python. However, it is said that the implementation is puzzling and lengthy, and it is hardly used in an intended solution in competitive programming.

In fact, if you only want the weight of a minimum-weight perfect matching, it can be easily computed using Tutte matrix and polynomial interpolation. First, let us take a look at Tutte matrix.

Tutte matrix and perfect matching

For a graph \(G(V, E)\) (\(V=\lbrace 1,2,\dots,N \rbrace\)), its Tutte matrix \((A_{i,j})\) is an \(N \times N\) matrix defined as:

\[ A_{i,j}= \begin{cases} x_{i,j} & \text{if } (i, j) \in E \text{ and } i \lt j \\ -x_{i,j} & \text{if } (i, j) \in E \text{ and } i \gt j \\ 0 & \mathrm{otherwise}. \\ \end{cases} \]

An important property of Tutte matrix is that:

The following propositions are equivalent:

• The determinant of the Tutte matrix \(A\) is non-zero (as a polynomial with variables \(x_{i,j}\)).
• \(G\) has a perfect matching.

(Proof) The determinant \(\det A\) of \(A\) by the following equation. Here, \(S_N\) is the set of all permutations of size \(N\), and \(\mathrm{sgn}(\sigma)\) is a function that takes \(1\) if \(\sigma\) is an even permutation, and \(-1\) if it is an odd permutation.

\[\det A = \sum_{\sigma \in S_N} \mathrm{sgn}(\sigma) A_{1,\sigma(1)} A_{2, \sigma(2)} \dots A_{N, \sigma(N)}\]

Consider the term corresponding to a permutation \(\sigma\). The permutation graph of \(\sigma\) (the \(N\)-vertex \(N\)-edge directed graph with edges \(i \to \sigma(i)\)) forms cycles. Suppose that this graph contains an odd cycle. Pick the odd cycle containing the vertex with the minimum number among those in all negative cycles. Flip the direction of the edges contained in the cycle, and let \(\sigma'\) be the permutation corresponding to that graph. Then, we can confirm that the contribution of \(\sigma\) to \(\det A\) is \(-1\) times the contribution of \(\sigma'\) to \(\det A\). (This is because, the \(\mathrm{sgn}\) part can be ignored since the conversion from \(\sigma\) to \(\sigma'\) is an even permutation, and \(A_{\ast,\ast}\) are multiplied by \((-1)^{(odd cycle length)}\).) Since \(\sigam\) and \(\sigma'\) correspond one to one, the terms containing odd cycles are canceled out, and not contained in \(\det A\). Conversely, we can also assert that if \(\sigma\) contains only even cycles, that term is never canceled out. (This is because cancel-out may occur only for the reversed cycle, but reversing an even cycle does not change the contribution.)

By the discussion above, the equivalence can be proved as follows.

• \((\to)\): If \(\det A\) is non-zero, then there exists a permutation \(\sigma\) such that the contribution to \(\det A\) is non-zero and the permutation graph consists only of even cycles. By taking every other edges in each cycle, we obtain a perfect matching.
• \((\gets)\): Let \((a_1, b_1), \dots, (a_{N/2}, b_{N/2})\) be a perfect matching. Then, the permutation \(\sigma\) with \(\sigma(a_i) = b_i, \sigma(b_i) = a_i\) is not canceled out, so \(\det A\) is non-zero.

Hence, it has been proved that the two propositions are equivalent. (End of proof)

Using the property of Tutte matrix, we see that the existence of a perfect matching can be decided if we can compute a determinant with \(E\) variables. While computing it directly is difficult, in this case we can use a randomized algorithm to determine if the determinant is non-zero with high probability. Specifically, one can take a sufficiently large prime \(P\) and compute the determinant when random numbers are assigned to \(x_{i,j}\). By Schwarz-Zippel lemma, the probability that this randomized algorithm fails is bounded by \(\mathrm{O}(N / P)\).
By the discussion above, it turns out that one can use Tutte matrix to determine the existence of a perfect matching. The bottleneck of this algorithm is to compute the determinant; if you use Gaussian elimination, the total time complexity is \(\mathrm{O}(N^3)\).

Bonus 1: Tutte matrix also has the following property. Consider the proof.

• the rank of the matrix \(A\) modulo \(P\), when random numbers are assigned to \(x_{i,j}\), coincides with the size of a maximum matching with high probability.

Bonus 2: With knowledge of linear algebra, it is also known that we can reconstruct a perfect matching in \(\mathrm{O}(N^3)\) time using Tutte matrix. If you are interested, think of how to do so. (It is very difficult.)

Minimum-weight perfect matching

The algorithm of deciding the existence of a perfect matching using Tutte matrix can be tweaked to find the weight of a minimum-weight perfect matching. Simply put, we can add a variable \(y\) into the Tutte matrix to interpret as a kind of generating function.

We will explain specifically. For an edge-weighted graph \(G(V,E)\), let \(w_{i,j}\) be the weight of edge \(ij\). (Assume that \(w_{i,j}\) are non-negative). Define a matrix \(B\) by:

\[ B_{i,j}= \begin{cases} x_{i,j} y^{w_{i,j}} & \text{if } (i, j) \in E \text{ and } i \lt j \\ -x_{i,j} y^{w_{i,j}} & \text{if } (i, j) \in E \text{ and } i \gt j \\ 0 & \mathrm{otherwise}. \\ \end{cases} \]

Then, the weight of a minimum-weight perfect matching is found as follows:

• If the determinant of \(B\) is zero (as a polynomial), there is no perfect matching.
• If the determinant of \(B\) is non-zero, take the term with the minimum degree of \(y\). The weight of the minimum-weight perfect matching is the degree of \(y\) in that term, divided by two.
  

(Proof) It is obvious from the property of Tutte matrix that if the determinant of \(B\) is zero, then there is no perfect matching. We proof the latter claim. Since it is obvious that the term corresponding to a minimum-weight perfect matching of \(G\) has a degree on \(y\) twice the weight, so it is sufficient to assert that there is no non-zero term with a smaller degree on \(y\).

Take an arbitrary \(\sigma\) corresponding to a non-zero term. The permutation graph of \(\sigma\) consists only of even cycles. Take an even cycle of size at least four, denoted by \(v_1 \to v_2 \to \dots \to v_{2n} \to v_1\). Perform the following operation against \(\sigma\).

• Compare \(w_{v_1, v_2} + w_{v_3, v_4} + \dots + w_{v_{2n-1},v_{2n}}\) and \(w_{v_2, v_3} + w_{v_4, v_5} + \dots + w_{v_{2n}, v_1}\).
• If the former is smaller, replace the even cycle with \(v_3 \to v_4 \to v_3, \dots, v_{2n-1} \to v_{2n} \to v_{2n-1}\).
• Otherwise, replace the even cycle with \(v_2 \to v_3 \to v_2\), \(v_4 \to v_5 \to v_4, \dots, v_{2n} \to v_1 \to v_{2n}\).

By repeating this operation, one can reach to a \(\sigma\) whose permutation graph consists only of size-\(2\) cycles, while never increasing the degree of \(y\). If the degree on \(y\) of the non-zero term corresponding to this final \(\sigma\) is less than twice the weight of a minimum-weight perfect matching, it implies that there exists a perfect matching whose weight is smaller than that of a minimum-weight perfect matching, which is a contradiction. Hence, the degree on \(y\) of the term corresponding to the original \(\sigma\) is also no less than the weight of a minimum-weight perfect matching. Now the claim has been proved. (End of proof)

Therefore, if one can compute the degree of \(y\) in the term with the minimum degree of \(y\), then the weight of a minimum-weight perfect matching can be obtained. Just as the computation of Tutte polynomial, we can assign a random value to \(x_{i,j}\) and evaluate it modulo \(p\), so that it is reduced to computing the determinant of a matrix \(C\) with a single variable \(y\). The probability can be theoretically guaranteed by Schwarz-Zippel lemma, just as the previous example.
The maximum degree of \(y\) in the determinant of \(C\) is \(WN\), where \(W\) is the maximum edge weight of \(G\). Thus, the determinant of \(C\) is a polynomial of degree at most \(WN\). Thus, the determinant can be computed by plugging \(y=0,1,\dots,WN\) into \(C\) and performing a polynomial interpolation. The bottleneck is to compute the determinant \((WN+1)\) times, and the total time complexity is \(\mathrm{O}(WN^4)\).

As a side note, if you do not want to implement polynomial interpolation, you can also reconstruct the polynomial using discrete Fourier transform. That is, take an integer \(B\) greater than the degree \(N\) of the polynomial, evaluate the polynomial at \(y=\zeta^0, \zeta^1, \dots, \zeta^{B-1}\), and perform inverse Fourier transform in \(\mathrm{O}(B^2)\) time. If you set \(p\) to an NTT-friendly prime (NTT: number-theoretic transform) and set \(B\) to a power of two, you can also compute it in \(\mathrm{O}(B \log B)\) time using a fast Fourier transform (of base \(2\)).
All that required for this technique is the definition of Fourier / inverse Fourier transform, so it can be applied in a situation like “you’re in ICPC, and now you need polynomial reconstruction, but you forgot to include it into your library.” Do use it if you have a chance.

Bonus 3: one can modify this method to support general maximum-weight matching that is not necessarily perfect. (It is even applicable for minimum-weight matching, but the answer is always \(0\) after all). How can you modify it?

That is all for the method of using matrix operations to find the weight of a minimum-weight perfect matching. In this problem, it is sufficient to compute a minimum-weight perfect matching on a graph with edge weights \(0\) or \(1\), and applying the method above allows us to compute it in \(\mathrm{O}(N^4)\) time. Note that you may even apply the method mentioned in ABC323G to compute \(\det(Ax+B)\) fast.

Perfect matching or maximum matching on a general graph, as described above, usually does not appear in AtCoder. However, as we explained here, if you want to know only the size of a perfect / maximum matching, computing it is immediate (as long as you are proficient in combinatorics algorithms). Five-hour contests sometimes ask reducing to a maximum matching (although it is rare); if you want to be better at graph-related field, do learn this problem.