First, we may notice that the task has two hard parts, which are…

1. Finding where you really should plant the crops
2. Scheduling the crops to the positions

To exceed 30M score in the pretests you may have needed to think of the two parts as a single process, but here, let us just think that these two are separate processes. Then the two processes correspond to very well-known tasks.

• Finding where you really should plant the crops

If we think about using only the reachable cells for the candidates for now, we can formulate the task to the following:

• maximize the size of the vertex set \(C\)
• so that every vertex in \(C\) are connected to some vertex in \(V \setminus C\)
• and the induced graph of \(V \setminus C\) is connected

If we change the focus from \(C\) to \(D=V \setminus C\), then \(|C|+|D|=HW\), and so the task changes to the following:

• minimize the size of the vertex set \(D\)
• so that every vertex in \(V \setminus D\) are connected to some vertex in \(D\)
• and the induced graph of \(D\) is connected

Now this is the Minimum connected dominating set problem. Do note that the literature in this field is divided into two main insights, one focusing on the dominating set, and the other focusing on the number of leaves in the spanning tree. I decided to focus on the former.

There were many papers of either approach, but they were either inefficient, or hard to implement. I eventually had to find an unique heuristic. The heuristic was as follows:

• At each step, find all vertices that are NOT an articulation point.
• Sort the found vertices by increasing order of degree.
• Remove the one vertex with minimum degree, setting it as a candidate for planting.
• Repeat.

This heuristic seemed to find a sufficiently good solution for the average case, so I stopped focusing on this part. For example, when \(seed=998244353\), the utility map this algorithm finds is as follows.

We may now move to the next process.

• Scheduling the crops to the positions

You may have used many different approaches for this part, for example, a greedy scheduling approach. While other approach work sufficiently well, I decided to find the optimal scheduling. It turns out that we can formulate the task as follows.

• maximise sum of \(W=E-S+1\)
• when scheduling the work to \(m\) identical machines

This task, due to Arkin and Silverberg, can be solved in polynomial time. Precisely, we formulate the task into a flow graph, and solve the min-cost flow problem for sending \(C-m\) flows, where \(C\) is the size of the maximum clique. The paper suggests that the time complexity of the algorithm is \(O(n^2 \log n)\), and here, \(4000 \le n=K \le 7000\) approximately, so the approach’s time complexity may seem too tight for the time limit of 2 seconds. But this time complexity is not tight for this task. In fact, the time complexity is really \(O(cn \log n)\), where \(c\) is the number of maximal cliques. The \(O(n^2 \log n)\) that the paper suggests is in the case that \(c=O(n)\). However, in our task, \(c\) is at most a constant, which is \(T=100\). This finally results in a time complexity of \(O(TK \log K)\), which is fast enough to pass in the time limit.

Combining these two processes, we get a score of 26604075 in the pretests, and 1057731000 in the system tests. Quite an impressive result for an approach not using metaheuristic algorithms, isn’t it?