omg 400-points-A round

TOO HARD

0 questions solved in a contest after very long :(

Definitely too hard for ARC.
Is this really ARC and not AGC?

TOOOO Hard

Hi there from the 4th place!

Generally, most definitely, thank you for the contest!! But here's some feedback:

• As many will moan here together with me, A was too hard for its slot.
• С is nice, but some parts can be guessed-without-proof. May be, asking for the entire procedure of swaps would be a better check for whether a contestant got all the needed ideas.
• I solved E, but I do not understand a single thing about its solution. I just guessed what you could possibly ask me to do on position E with a matrix up to 300×300, and then tried to figure out the ±1 ending by chance. That makes me happy with the result but unhappy about its fairness.

AtCoder Regular Corner-case, struggled for Problem A and C in the whole contest.

Good problems but the samples are too weak. Maybe give a stronger sample the next time?

TOOOO Hard！My classmate who get 11st in arc154 did't solve any problem!(I only solve one!) if you don't belive ,than i'll tell you his id :jbwlgvc(look it!)

I only solved D, couldn't manage to solve neither A nor B in 40 minutes :D

From the editorial of D (evima):

if $$$1 < \gcd (A_i, G) < G$$$ for some $$$A_i$$$, then $$$A_i$$$ always remain on the blackboard

Am I missing something essential? Isn't this obviously false according to the statement? Maybe you wanted to express something else using the word "always"?

I solved D using a simple dfs . But the time complexity may be wrong .

https://atcoder.jp/contests/arc155/submissions/38465395

Problem A was Too hard.

Weird screencast

Problem A is really treasure! I think my idea is quite close to the editorial (reduce large k to small one and handle the case with O(N) size), but I have never thought about using mod=2*n.

This may sound a little bit sad but I have considered using n or 3n, which gave me nothing :(

An algebraic approach on F (sketch):

Imagine the edge between $$$i$$$ and $$$j$$$ has weight $$$x_i + x_j$$$, we want to compute the coefficient of $$$x_1^{d_1} \cdots x_n^{d_n}$$$ among the total weight of all spanning trees. We can apply the matrix tree theorem.

Let $$$s = \sum x_i$$$, $$$\boldsymbol x$$$ be the vector of $$$x_i$$$ s, $$$\boldsymbol 1$$$ be the all-one vector.

Therefore, the Laplacian matrix is

Wlog assume $$$d_n = 0$$$, we compute the determinant of $$$L$$$ removing the last row and column. We assume all indices are from $$$1$$$ to $$$n-1$$$ later. Note that $$$\boldsymbol 1\boldsymbol x^{\mathsf T} + \boldsymbol x \boldsymbol 1^{\mathsf T}$$$ has rank $$$2$$$, the expansion of determinant is simple, we have

For the first term, we have

where $$$T$$$ is the linear functional, mapping $$$x^\ell$$$ to $$$\ell!$$$.

The rest terms can be treated in a similar way.

Problem A was Too hard that a person whose rating 2700+ cant' solve it!.

https://atcoder.jp/contests/arc155/standings?watching=Barichek

Hack on problem D:

Input:

6
2 2 6 15 30 30

Expected output:

Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki

Output of hacked solution:

Takahashi
Takahashi
Aoki
Aoki
Takahashi
Takahashi