Prequel: A Hilarious Problem

I don't expect this can have a sequel. However, the problem is not that hilarious, because it indeed involves some ad-hoc. So I consider the problem interesting.

In today's AWC, Problem E can be reduced to this:

You're given a set $$$U = \lbrace 1, 2, 3, \ldots, n \rbrace$$$, and you needs to partition $$$U$$$ into several sets $$$S_1, S_2, \ldots, S_k (1 \le k \le n)$$$ such that:

• $$$\bigcup_{i=1}^{k}S_i = U$$$
• for all $$$1 \le i \lt j \le n$$$, $$$S_i \cap S_j = \emptyset$$$

You're also given an array $$$V$$$ of length $$$n$$$. Find the maximum of:

Again. The optimal partition is to assign each value $$$i$$$ to to separate group $$$S_i$$$, which yields a maximum of $$$\sum_{i}V_i - \max_{i} V_i$$$. Its proof can be left as an exercise for readers.

All of the LLM solutions do brute force on $$$B_n$$$ partitions, and fail to discover this greedy approach. However, if one copy the statement to the three LLMs, it can indeed give the greedy solution correctly. This has confirmed my doubt in the prequel: the workflow might be giving LLM a topic and asking it to generate both statement and editorial with no human review.

In addition, both problems involve partitioning. Perhaps Takahashi-kun just installed the partition topic and forget to ask LLMs to validate if there is a polynomial solution.