We will hold AtCoder Regular Contest 155.

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

The point values will be 400-500-700-800-900-1000.

We are looking forward to your participation!

Last week I registered with Atcoder Regular Contest 154 and didn't complete one problem.

omg 400-points-A round

Good luck!

Good Luck!

Spoiler : after seen 1st problem me :(TOO HARDi thought it was my bad 55555

0 questions solved in a contest after very long :(

Very nice contest. Thanks for kicking me 4th time with the logic that reverse of reverse of reverse = blank. I will leave the blank to people. you can fill what ever you want

Definitely too hard for ARC.

Is this really ARC and not AGC?

TOOOO Hard

I had pretty bad luck for getting an AC on problem C just 2 minutes after the contest.

Hi there from the 4th place!

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

can u explain how to solve A? i dont understand editorial solution

you kan Categorize discussions

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):

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 think it means "any $$$A_i < G$$$ is currently on the blackboard".

Well that's a very different meaning!

The editorial does not mean "such A_i will be on the board forever". It means "we can guarantee that such A_i is not yet erased", because G must be a divisor of any erased number.

The problem is that "always" has a very specific meaning, which is distinct from "so far". It's possible to expand upon a short sentence like that so the different meaning is clarified, but Atcoder editorials are way too brief and tend to not do that, so they only help understand solutions to those who already more or less know the solutions. In addition, that statement is obvious to anyone with half a brain, which makes it extra misleading — if an editorial is quite short, then everything in it

should beimportant enough to mention.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.Problem A was

Too hard.Problem C was

Toooo hard.Too many Corner-cases on A and C.

Tooooo Hardddddddddd!

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 :(

Same! I used mod n and tried to go through many cases, but nothing was turning up.

I know from the editorial that 2*n works, but I'm trying to understand what was the intuition to try 2*n and not n or 3*n.

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:

Expected output:

Output of hacked solution:

maroonrk please add this into the after contest tests

done