Hello, CodeForces!

I am hirayuu_cf. I often create problems on yukicoder.

By the way, GPT-4o is a hot topic right now. It has a significant impact on competitive programming, such as making it possible to solve typical problems by just copy-pasting, but that's another story. I am a Japanese speaker and cannot speak English very well, but thanks to ChatGPT, I am able to express my thoughts in English like this. Most of this blog, including this text, has been translated by ChatGPT, sorry for any mistakes.

Let's get back to the topic. In the past, I co-hosted the yukicoder contest 424 with Magentor. (At the time of writing, I am a Candidate Master, and Magentor is a Newbie, but both Magentor and I have good results on AtCoder.)

Since this is a good opportunity, I would like to share some of my best creations translated into English. Please give them a try!

Of course, you won't be able to solve this problem just by copy-pasting it into ChatGPT (haha). If you manage to solve it, please hide your solution in a spoiler and leave a comment!

Please Hack Greedy Solution! (★★☆)

Problem Statement

This is an output-only task.

In the 0-1 knapsack problem, is it possible that the exact solution almost always outperforms the greedy solution?

Find a sequence of positive integers $$$N, W$$$, and pairs of positive integers $$$((v_1, w_1), (v_2, w_2), \dots, (v_N, w_N))$$$ that satisfy the following conditions:

• $$$1 \leq N \leq 2000$$$
• $$$1000 \leq W \leq 2000$$$
• $$$1 \leq v_i \leq 10^9$$$
• $$$1 \leq w_i \leq W$$$
• For $$$p = 1, 2, \dots, W$$$, there is at most one $$$p$$$ that does not satisfy the following conditions:
  • Let $$$R$$$ be the maximum value of $$$\sum_{i \in S} v_i$$$ among all subsets $$$S \subseteq \{1, 2, \dots, N\}$$$ such that $$$\sum_{i \in S} w_i \leq p$$$. If there is no non-empty $$$S$$$ satisfying $$$\sum_{i \in S} w_i \leq p$$$, let $$$R = 0$$$.
  • Replace $$$((v_1, w_1), (v_2, w_2), \dots, (v_N, w_N))$$$ with the sequence sorted in descending order of $$$\frac{v_i}{w_i}$$$ (if they are equal, sorted by descending $$$w_i$$$), and perform the following operations in order for $$$i = 1, 2, \dots, N$$$, with $$$q = p$$$ and $$$G = 0$$$:
    • If $$$w_i \leq q$$$, replace $$$q$$$ with $$$q - w_i$$$ and $$$G$$$ with $$$G + v_i$$$.
  • At this point, $$$R$$$ is strictly greater than the final $$$G$$$.

Hints

Solution

Comment

This is probably the last problem I came up with among the problems I submitted to the contest. I suddenly thought of it while lying in bed, and after trying various things, I arrived at a neat conclusion. The problem doesn't really require much algorithmic knowledge; it's one where analytical skills problem the most. Although I'm not very familiar with the level of difficulty of CodeForces problems, I think it could fit as the 2nd or 3rd problem in a Div.2 contest (setting aside the fact that it is output-only).

L to R Graph (Another ver.) (★★★★)

Problem Statement

Consider the following problem.

Given a sequence of integers $$$A = (A_1, A_2, \dots, A_N)$$$ of length $$$N$$$ consisting of integers from 1 to $$$N$$$, and given $$${L, R}$$$ satisfying $$$1 \leq L \leq R \leq N$$$, and $$${S, T}$$$ satisfying $$$1 \leq S \leq N, 1 \leq T \leq N, S \ne T$$$.

Define $$$f(i) = A_i$$$. Also, let $$$f^k(i)$$$ denote $$$f(i)$$$ composed $$$k$$$ times.

There is a directed graph with $$$N$$$ vertices labeled from 1 to $$$N$$$ and 0 edges initially. The following operation is performed on this graph:

• For $$$1 \leq i \leq N$$$ and $$$L \leq k \leq R$$$, add an edge from vertex $$$i$$$ to vertex $$$f^k(i)$$$.

Determine if there is a path from vertex $$$S$$$ to vertex $$$T$$$.

Given $$$N$$$ and a prime number $$$P$$$, find the number of valid inputs where a path exists from vertex $$$S$$$ to vertex $$$T$$$, modulo $$$P$$$. There are $$$N^N \times \frac{N(N+1)}{2} \times N(N-1)$$$ possible inputs.

Constraints

• $$$2 \leq N \leq 10^5$$$
• $$$10^8 \leq P \leq 10^9$$$
• $$$P$$$ is a prime number
• All inputs are integers

Hints

Comment

This problem is derived from the problem "L to R Graph" proposed by Magentor. The original problem presents queries in the form of "Given $$$A$$$, $$$L$$$, and $$$R$$$, is it possible to reach vertex $$$T_i$$$ from vertex $$$S_i$$$? If so, what is the shortest distance?" with up to $$$Q \ (1 \leq Q \leq 10^5)$$$ queries. The original problem is also interesting because it is an information Olympics-like problem, so I encourage you to try it out. However, since this is a comment on my reformulated problem, let's get back to the main topic.

This is my proudest creation. I don't think there will ever be a day when I can create a more difficult and interesting problem than this one...

Some time after the original problem was proposed, I suddenly thought, "Can't we turn this problem into a counting problem?" At first, I tried to make it ask for the sum of the shortest distances, but this didn't work out. Then, by relaxing the conditions to count the number of reachable vertices, and it turned out to be a surprisingly good problem, which made me very excited. During the contest, two Legendary Grandmasters who tackled this problem right away both took about an hour to achieve AC, so it turned out to be much more difficult than I had initially expected. However, it doesn't require advanced knowledge such as formal power series, but rather very typical knowledge. So, I definitely encourage you to try solving it!

UPD: A solution for "Please Hack Greedy Solution!" has been added. A solution for "L to R Graph (Another ver.)" will be added in the future.