Good luck

good luck

sure? this problem with c=3, n<=10 was in russian regional olympiad several years ago and proper solution is randomization

I can't do better with a square board, but I think $$$625\times 650$$$ is possible. Identify the labels with elements of the finite field $$$\mathbb{F}_{25}$$$, the rows with ordered pairs $$$(u, v)\in \mathbb{F}_{25}^2$$$, and the columns with tuples $$$(a, b, c)\in \mathbb{F}_{25}^3$$$ where $$$(a, b)$$$ is restricted to the set $$$\{(1, x) \mid x\in \mathbb{F}_{25}\}\cup \{(0, 1)\}$$$. Then the label at the intersection of $$$(u, v)$$$ and $$$(a, b, c)$$$ is $$$au+bv+c$$$.

Let's choose distinct rows and columns $$$(u_1, v_1), (u_2, v_2), (a_1, b_1, c_1), (a_2, b_2, c_2)$$$ and suppose that the corners all have the same label. If $$$(a_1, b_1) = (a_2, b_2)$$$ then $$$c_1\neq c_2$$$, so $$$a_1u_1+b_1v_1+c_1 \neq a_2u_1+b_2u_1+c_2$$$, i.e. the corners don't have the same label. Otherwise, $$$(a_1, b_1)\neq (a_2, b_2)$$$ so then $$$(u_1, v_1)$$$ is uniquely determined by $$$a_1u_1+b_1v_1+c_1$$$ and $$$a_2u_1+b_2v_1+c_2$$$. However, $$$(u_2, v_2)$$$ is determined by the same constraints so we would get $$$(u_1, v_1) = (u_2, v_2)$$$ contradiction.

Also, by a counting argument, $$$625\times k$$$ is not possible for $$$k > 650$$$.

Source: I spent almost the whole contest on problem E, and I got AC $$$37$$$ seconds before the end.

My notes: PDF

• Page $$$9$$$: maybe it's useful to consider the "classical" bipartite graph.
• Page $$$10$$$: small cases by hand, in the $$$4 \times 4$$$ case the cells with color $$$1$$$ make a big cycle. Maybe the intended is choosing a color for each diagonal.
• Page $$$11$$$: there is a rectangle if there are two equal pairwise differences in the set of diagonals of a fixed color. Can we partition $$${0, 1, \dots, 499}$$$ in such a way that there are no such differences?
• I tried to generate such diagonals on my PC, but I got stuck at $$$n \approx 370$$$.
• Page $$$13$$$: ok, let's quit the diagonals approach. Let's put the color $$$1$$$ greedily, but in such a way that there are $$$\approx \sqrt{500}$$$ occurrences on each row (unbalanced occurrences = more pairs of cells with the same color in the same row = worse)
• Page $$$14$$$: let's remove the rows $$$[4, 6]$$$ of page $$$13$$$, they seem inconsistent with the rest of the grid. Ok, we've found a construction with $$$n = m = 16$$$ and $$$4$$$ colors. [Actually it's wrong, there is a rectangle $$$(1, 1), (1, 11), (9, 1), (9, 11)$$$, but I hadn't noticed it.]
• Page $$$15$$$: oh wait, it works even with $$$n = m = 625$$$ and $$$25$$$ colors!
• [1:58:05] Submitted, got WA.
• Oh wait, there actually is a rectangle because $$$25$$$ is not prime.
• Let's try $$$23$$$.
• [1:59:23] Submitted, got AC, shouted like a crazy guy.

If we consider directed edge (i->xi), then each vertex will have out degree of exactly 1. Because of that, if we consider one graph such that all xi != -1, then each component will have at most one cycle if there are any.

No. of connected components = No. of vertices — No. of edges + No. of cycles

Initially we will have n components in which no edge is added. We will start adding edges one by one. Adding each edge will reduce the component by one unless we are already in a same CC in which it won't reduce. All such edges will have one to one mapping with cycles. So we can count cycles instead.

Now if we consider the graph with X array given in the question. We will get some components. Each component will have at most one xi = -1. We only consider the component with xi =-1 as we are interested only in cycles.

Let the size of components be A1,A2...AM where M are the number of component which have xi = -1

Consider the cycle formed from component set {A1,A2,A3...AK}. We can permute them in (k-1)! ways. And then we connect the edges. There are A2 edges we can direct of comp1 to comp2, A3 edges we can direct from comp2 to comp3 ... and A1 edges we can direct from compK to comp1. Then we can choose remaining edges arbitrarily. So we multiply N^(M-k).

Thus for component set {A1,A2...AK} we have (k-1)! * A1 *A2...*Ak * N^(M-k)ways to form a cycle. So we can use NTT to find Summation of product of (A1*A2*A3..AK) for each k.

Hello there, I'll try my best to give a clear explanation about the solution.

first of all, let's assume that the given array contains no -1 (in other words, all edges are given). By looking at a single component of the graph, you can see the number of edges in it are equal to the number of nodes, since as given in the input there is a single edge having a starting point at each particular vertex.

Therefore, for every graph built in the same manner as the problem asks, it is enough to count the number of it's cycles and add these numbers up to form the answer. So from now on, we forget about the main problem and solve the new one, which is counting the number of cycles of all the graphs that can be built.

Array A may contain values equal to -1, let's see how the graph will look if we forget about these edges. There will be a bunch of components, each one having at most one cycle since there is at most one vertex in each with no edge starting at it.

Now instead of counting for each graph the number of cycles it contains, we can count for each cycle the number of graphs which contain it and sum these values up. Think of a cycle which there are T other values equal to -1 in A other than those used to make the cycle. Then there are n^T graphs containing the cycle. So if there already exists a cycle in a component of the given graph, just add n^(the number of -1s) and forget about these components.

What is left, is a group of components, each looking like a tree, with exactly one node in them that you can add an edge from it to any other node to make your cycles. Consider a cycle using components with size B_1, B_2, ..., B_x. Then there are exactly

(x - 1)!(B_1 * B_2 * ... * B_x)

cycles that can be formed since you can put these components around a circle and then connect each component to the next one. So now you just have to calculate sum of the given expression for all components, which can be done using dynamic programming.

Here's also my code for better understanding of the solution

#include <bits/stdc++.h>

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define pb 			push_back

using namespace std;
typedef long long 		LL;

const int N = 2000 + 7;
const int MOD = 998'244'353;

LL n, cnt, ds, bc;
LL ns[N], colored[N];
LL dp[N][N], fact[N];
vector<int> adj[N], v;

inline void init() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> ns[i];

        if (ns[i] != -1) {
            ns[i]--;
            adj[i].pb( ns[i] );
            adj[ ns[i] ].pb(i);
        }

        else bc++;
    }

    return;
}

void dfs(int now) {
    colored[now] = 1;
    cnt++;
    ds += adj[now].size();

    for(int on : adj[now]) if (!colored[on]) 
        dfs(on);

    return;
}

inline LL pw(LL a, int b) {
    LL res = 1;
    for(; b; b >>= 1, a = a * a % MOD) 
        if (b & 1) res = res * a % MOD;
    return res;
}

int main() {
    IOS;
    
    init();
    LL ans = 0;

    v.pb(0);
    for(int i = 0; i < n; i++) if (!colored[i]) {
        cnt = ds = 0;
        dfs(i);
        
        if (ds / 2 < cnt) v.pb(cnt);
        else ans = (ans + pw(n, bc)) % MOD;
    }

    for(int i = 1; i < v.size(); i++) {
        dp[i][1] += v[i];

        for(int j = 1; j < v.size(); j++) 
            dp[i][j] = (dp[i][j] + dp[i - 1][j] + dp[i - 1][j - 1] * v[i]) % MOD;
    }

    fact[0] = 1;
    for(int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
    for(int i = 1; i <= bc; i++) ans = (ans + (pw(n, bc - i) * dp[v.size() - 1][i] % MOD) * fact[i - 1]) % MOD;

    cout << ans;
}

I hope this helps :)

Thank you so much for creating such great problems.

Problem B is a nice practice for greedy algorithm, and I think there are several corner cases which one should take care of.

As for Problem C, I missed the simple solution in editorial and used a more complicated one, but anyway, I have learned a lot of exciting ideas from your problems, thanks a lot!

B and C maybe a bit simple for me. Thanks for Problem E. I took really much time in it in the contest (sadly didn't solve D or E), and was happy when I could explain and proof the solution clearly.

Really a nice construction round, thank you again. ;)