problem C and D is pretty great ! High quality problems.

The base idea using Hall was that I would have two sets: elements and positions; both intervals [1;N]. I am trying to find a perfect matching between elements and positions. Not any matching, the smallest lexicographically one.

For each [l;r] in positions, it must be that the number of incoming edges to this interval must be >= number of unused elements in [l;r]. That is, having a incoming([l;r]) >= unused([l;r]), what is equiv. to incoming([l;r]) - unused([l;r]) >= 0. This reduces to checking if there is any position i smaller than 0, what can be done using a Segtree. A value i contributes with -1 to seg[i] and with 1 to seg[0:i-k] and seg[i+k;n-1].

I would then put the smallest element in each iteration that doesn't violate this condition. That is, when trying to figure the element at position i, check if it is still feasible for [i+1;n-1] if I remove the i-th element from the structure (add 1 to seg[i] and remove 1 from seg[0:i-k] and seg[i+k;n-1]).

The first problem is that Hall's isn't enough for "testing if it is feasible simulating adding x". It could be that all positions that a still unused element x could use are filled up and thus x has no out edges to [i+1;n]. Hall's worries only about saturating elements that have out edges. Thus, I would need another structure to check if I've left an element unmatched (probably another Segtree).

The second problem is checking what's the minimum element is efficiently. I depends on the first problem. I guess that if all elements can reach at least two positions and that the minimum element in seg[i] is >= 1, I can just take the smallest available element. But this is already too tricky.

Yes, there is :D https://atcoder.jp/contests/arc144/submissions/33347474

I was also confused about it. After thinking for a long time, I finally got it, so I'll try to explain my understanding here.

As the editorial read, the decision problem has been reduced to the following:

You are given some pieces of information in the form $$$P_v \equiv P_w + c \pmod x$$$. Determine whether one can set a sequence of potentials $$$(P_v)_v$$$ without contradicting them.

We can easily solve it with weighted union-find or just by DFS, so the only problem we need to consider is that $$$x$$$ is not fixed in the original problem.

Considering the process solving the decision problem, one can find that we only need to check if $$$a \equiv b \pmod x$$$ is true for a few pairs $$$(a,b)$$$, where both $$$a$$$ and $$$b$$$ are constants we can calculate.

And we can simply do the same: the answer is just the GCD of $$$|a-b|$$$ among all of these pairs. Since the final answer will always satisfy all of these equations, we don't need to modulo anything by the current answer. And if all such pairs satisfy $$$a=b$$$, the answer is obviously $$$-1$$$.

For more details, you can read some solutions for this problem, for example, the writer's submission.

More explanation: I always feel I have seen the problems at the past. But things were not like that, at arc 126-130, there was full of adhoc problems. As a comparison, I love AGC very much. I know it's hard to create good problems, that's why I feel sad about arc these days.

That's because you got stronger.

Same, wasted 30min and 6 penalties on it :)

Consider digit 1 to digit 9. When we multiply 2 to each digit, they become:

1 -> 2
2 -> 4
3 -> 6
4 -> 8
5 -> 10
6 -> 12
7 -> 14
8 -> 16
9 -> 18

Comparing the sum of digits, SOD(), of x and 2x:

SOD(1) = 1 -> SOD(2) = 2
SOD(2) = 2 -> SOD(4) = 4
SOD(3) = 3 -> SOD(6) = 6
SOD(4) = 4 -> SOD(8) = 8
SOD(5) = 5 -> SOD(10) = 1
SOD(6) = 6 -> SOD(12) = 3
SOD(7) = 7 -> SOD(14) = 5
SOD(8) = 8 -> SOD(16) = 7
SOD(9) = 9 -> SOD(18) = 9

The best "gain" is the 4th row, where the input is 4 and the output is 8. So, we should try to pack as many 4s as we can.

[]

[]