### maroonrk's blog

By maroonrk, history, 2 months ago,

We will hold AtCoder Regular Contest 155.

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

We are looking forward to your participation!

• +93

 » 2 months ago, # |   -49 Last week I registered with Atcoder Regular Contest 154 and didn't complete one problem.
 » 2 months ago, # |   0 omg 400-points-A round
 » 2 months ago, # |   0 Good luck!
 » 2 months ago, # |   0 Good Luck!
 » 2 months ago, # |   +1 Spoiler : after seen 1st problem me :(
 » 2 months ago, # |   +17 TOO HARD
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 i thought it was my bad 55555
 » 2 months ago, # |   +14 0 questions solved in a contest after very long :(
 » 2 months ago, # | ← Rev. 2 →   -10 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
 » 2 months ago, # |   0 Definitely too hard for ARC.Is this really ARC and not AGC?
•  » » 2 months ago, # ^ |   -8 AGC wont come up with repeated Logic I guess that what I read in AtCoder site. I read about ARC is also like that in atcoder page but I guess I was wrong. 
 » 2 months ago, # |   +23 TOOOO Hard
 » 2 months ago, # | ← Rev. 2 →   0 I had pretty bad luck for getting an AC on problem C just 2 minutes after the contest.
 » 2 months ago, # |   +27 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.
•  » » 2 months ago, # ^ |   0 can u explain how to solve A? i dont understand editorial solution
•  » » » 2 months ago, # ^ | ← Rev. 2 →   -30 you kan Categorize discussions
 » 2 months ago, # |   +38 AtCoder Regular Corner-case, struggled for Problem A and C in the whole contest.
 » 2 months ago, # |   +42 Good problems but the samples are too weak. Maybe give a stronger sample the next time?
 » 2 months ago, # | ← Rev. 2 →   +12 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!)
 » 2 months ago, # |   +30 I only solved D, couldn't manage to solve neither A nor B in 40 minutes :D
 » 2 months ago, # |   0 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"?
•  » » 2 months ago, # ^ |   0 I think it means "any $A_i < G$ is currently on the blackboard".
•  » » » 2 months ago, # ^ |   0 Well that's a very different meaning!
•  » » » » 2 months ago, # ^ |   0 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.
•  » » » » » 2 months ago, # ^ |   +8 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 be important enough to mention.
 » 2 months ago, # |   +8 I solved D using a simple dfs . But the time complexity may be wrong .https://atcoder.jp/contests/arc155/submissions/38465395
 » 2 months ago, # |   +14 Problem A was Too hard.
•  » » 2 months ago, # ^ |   +15 Problem A was Too hard.Problem C was Toooo hard.
•  » » » 2 months ago, # ^ |   +10 Too many Corner-cases on A and C.Tooooo Hardddddddddd!
 » 2 months ago, # |   +21
 » 2 months ago, # |   0 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 :(
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # | ← Rev. 4 →   +82 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 $L=\operatorname{diag}(nx_i + s) - \boldsymbol 1\boldsymbol x^{\mathsf T} - \boldsymbol x \boldsymbol 1^{\mathsf T}$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 $Ans = \prod_{i} (nx_i + s) + \sum_i (-2x_i) \prod_{j\neq i}(nx_j + s) + \sum_{i < j}(2x_ix_j - x_i^2 - x_j^2) \prod_{k\neq i,j} (nx_k + s).$For the first term, we have $[x_1^{d_1}\cdots x_{n-1}^{d_{n-1}}]\prod_{i} (nx_i + s) = T\left( \prod_{i=1}^{n-1} \left( n\frac{x^{d_i-1}}{(d_i-1)!} + \frac{x^{d_i}}{d_i!} \right) \right),$where $T$ is the linear functional, mapping $x^\ell$ to $\ell!$.The rest terms can be treated in a similar way.
 » 2 months ago, # |   +10 Problem A was Too hard that a person whose rating 2700+ cant' solve it!.https://atcoder.jp/contests/arc155/standings?watching=Barichek
 » 2 months ago, # | ← Rev. 2 →   +22 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 
•  » » 2 months ago, # ^ |   +22 maroonrk please add this into the after contest tests
•  » » » 2 months ago, # ^ |   +46 done