We will hold AtCoder Regular Contest 144.

- Contest URL: https://atcoder.jp/contests/arc144
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220716T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: maspy
- Tester: HIR180,Nyaan
- Rated range: — 2799

The point values will be 300-400-600-700-800-900.

We are looking forward to your participation!

YEAR！

Thanks for the contest. I liked problem C. Also, the problem statement of problem A was a little bit confusing for me.

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

Is there a way to solve C using something similar to Hall's marriage theorem?

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

Can anyone explain the solution of E? I can't understand why if you solve the decision problem, you can solve the original problem easily.

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:

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.

Thank you very much! After trying several small cases I finally understood it.

As a fan of ARC, I sadly feel it is going downhill. Neither the depth and breadth can't catch up with computer scientific research, and even other contests like opencup. That sounds sad, but that's what I feel more and more deeply everytime participating. Missing the good days, spending with the old good arc.

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.

How is AGC not full of adhoc

That's because you got stronger.

How to approach C? Can someone explain their approach.

Thanks to the strong tests, I

wasso close to 2000 points.(It is really hard for me to think of treating these $$$K$$$ s in a special way.)

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

Alternative solution for problem D:

Implementation

After reading editorial of problem D, although I still not quite understand part [4], I get really shocked, that, it needs so many observation and mathematics. Really a complicated problem! By the way, is there any different approach that someone would like to share or talk about?

For part [4] of the editorial of problem D, I think I have come up with a little bit different approach.

As method-1 says, we are going to compute the sum of $$$(1+K-\sum x_i)$$$ overall $$$(x_1,x_2,..,x_n)$$$ with $$$\sum x_i \le K$$$. If we write $$$\sum x_i = S$$$, where $$$S=1,2,...,K$$$, then we should compute $$$T=\sum_{S=1}^{S=K}(1+K-S) \times C_{S-1}^{n-1}$$$, where $$$C_{S-1}^{n-1}=\frac{(S-1)!}{(n-1)!(n-S)!}$$$ means the number of ways to choose $$$x_1,x_2,..,x_n$$$ under the constraint of $$$\sum x_i = S$$$.

Note that $$$C_{S-1}^{n-1}=0$$$ for $$$S<n$$$, thus $$$T=\sum_{S=1}^{S=K}(1+K-S) \times C_{S-1}^{n-1}=\sum_{S=n}^{S=K}(1+K-S) \times C_{S-1}^{n-1}$$$.

Then, $$$T=(1+K)\sum_{S=n}^{S=K}C_{S-1}^{n-1}-\sum_{S=n}^{S=K}SC_{S-1}^{n-1}$$$.

Now, by taking advantage of this equation $$$C_{k}^{k}+C_{k+1}^{k}+...+C_{n}^{k}=C_{n+1}^{k+1}$$$, we have $$$(1+K)\sum_{S=n}^{S=K}C_{S-1}^{n-1}=(1+K)C_{K}^{n}=(1+K)\frac{K!}{n!(K-n)!}=\frac{(K+1)!}{n!(K-n)!}=\frac{(n+1)(K+1)!}{(n+1)!(K-n)!}=(n+1)C_{K+1}^{n+1}$$$, and

\begin{equation} \begin{aligned} \sum_{S=n}^{S=K}SC_{S-1}^{n-1}=\sum_{S=n}^{S=K}S\frac{(S-1)!}{(n-1)!(S-n)!}=\sum_{S=n}^{S=K}\frac{S!}{(n-1)!(S-n)!} \ &=\sum_{S=n}^{S=K}\frac{nS!}{n!(S-n)!}=n\sum_{S=n}^{S=K}C_{S}^{n}=nC_{K+1}^{n+1} \end{aligned} \end{equation}

Thus, $$$T=(n+1)C_{K+1}^{n+1}-nC_{K+1}^{n+1}=C_{K+1}^{n+1}$$$.

I was so close to D!

I just found that if $$$f(x)$$$ for $$$x\le 2 ^ i$$$ is fixed, then $$$f(x+2^{i+1})$$$ could be written as $$$f(2^{i+1})+f(x)-f(0)$$$.

If I had expended this fomula a little bit, I could have found the key observation that $$$f(x)=f(0)+\sum_{i\in x}(f(2^i)-f(0))$$$, but I turned to think of DP instead.

Anyway, this is a great problem. I enjoyed it and learned a lot!

Who can please teach me how to solve problem C ? I can't understand the Editorial. Thanks a lot!!!

[]

This is under ARC, not ABC.

yeah，I asked how to solve ARC problem C

Can anyone help me with problem b, I read the editorial but could not understand the solution

[]

Wrong contest.