### 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! Comments (37)
 » 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 HARD
•  » » 2 months ago, # ^ | ← Rev. 2 →   i thought it was my bad 55555
 » 0 questions solved in a contest after very long :(
 » 2 months ago, # | ← Rev. 2 →   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?
•  » » 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. 
 » TOOOO Hard
 » 2 months ago, # | ← Rev. 2 →   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: 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.
•  » » can u explain how to solve A? i dont understand editorial solution
•  » » » 2 months ago, # ^ | ← Rev. 2 →   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?
 » 2 months ago, # | ← Rev. 2 →   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 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 be important 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!
 »
 » 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.
 » 2 months ago, # | ← Rev. 4 →   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.
 » 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 →   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 
•  » » maroonrk please add this into the after contest tests
•  » » » done