Here is a solution without polynomial exp.

First, we know:

• For a cycle, if the minimum edge value not at \(i\to p_i\) where \(i\) is the minimum index of the cycle, Alice will get WA.
• For a cycle, if the minimum edge value not at \(i\to p_i\) where \(i\) is the maximum index of the cycle, Bob will get WA.

Consider \(f_i\) denoting the probability that both get AC with \(n=i\), and \(g_i\) denoting the probability that exactly one of them get AC. The obvious answer is \((1-f_i-g_i)\times (n!)^2\). And suppose the generating function for \(f,g\) is \(F,G\).

\(f_i\) is clearly \(\dfrac{1}{i!}\), this is because if there is a ring of \(\geq 2\) surely one of them get WA, so they must all form self-rings. There is no requirement for edge weights.

Consider counting \(g\). First there is the most basic common lemma: in a \(i\to p_i\) permutation ring of \(n\) points, the size of the ring where the point \(n\) is located ranges from \([1,n]\) with equal probability. With this lemma, we consider enumerating the ring size \(i\) where \(n\) is located, when we want exactly one person get WA, that we have probability \(\dfrac 2i\)(because we need the minimum weights edge locate at the maximum index or the minimum index).Let \(a_i=\dfrac{2}{i}\) with \(i>1\) and \(a_1=0\). Getting the contribution of \(F\) to \(G\) is \(g_n\leftarrow \dfrac{\sum_{i=2}^n a_i\times f_{n-i}}{n}\). Then we have \(G\leftarrow A\times F\), where \(A\) is generating function of \(a\).

Consider again the contribution of \(G\to G\), for the same reason as above, except that this time the ring generating function becomes \(b_i=\dfrac{1}{i}\) with \(i\geq 1\). To summarise there are:

\[ g_n=\dfrac{\sum_{i=1}^n(a_i\times \frac{1}{(n-i)!} +g_{n-i}\times b_i)}{n} \]

The first \(A\times F\) is partially convolved once, and the second \(G\times B\) is clearly a semi-online convolution.

my submission