### maroonrk's blog

By maroonrk, history, 7 weeks ago,

We will hold AtCoder Grand Contest 058. This contest counts for GP30 scores.

The point values will be 400-700-900-1000-1400-2000.

We are looking forward to your participation!

• +286

 » 7 weeks ago, # |   +18
 » 7 weeks ago, # |   -31 how to do rated registration
•  » » 7 weeks ago, # ^ |   +16 You have to be a cyan or above to register for AGC which makes sense as it is supposed to be a Div 0.8 round
 » 7 weeks ago, # |   -39 Good luck have fun
 » 7 weeks ago, # |   +58 Can you please consider upgrading the kotlin compiler? The standard library improved a lot within two years passed since 1.3.72.
 » 7 weeks ago, # |   0 hope fine qwq
 » 7 weeks ago, # | ← Rev. 2 →   +38 Is it me or is there a 5min delay?
 » 7 weeks ago, # |   +37 Why is it delayed for 5 minutes?
 » 7 weeks ago, # |   +27 start at 20:05?
 » 7 weeks ago, # |   +143 A misconfiguration was found and the contest is delayed by 10 minutes.I'm super sorry for the inconvenience.
•  » » 7 weeks ago, # ^ |   +20 That's okay. Just adds more anticipation to the to-be amazing contest :)I love maroonrk rounds.
•  » » 7 weeks ago, # ^ |   +11 Now that the contest has ended, what was the misconfiguration?
•  » » » 7 weeks ago, # ^ |   +47 The scores of problems were set to wrong values. It's on my checklist, but I somehow skipped the check. Again, sorry for the inconvenience.
 » 7 weeks ago, # | ← Rev. 2 →   +5 The contest delay for 5 minutes and we have only 175 minutes. upd: The contest start at 20:10 and end at 23:10.
 » 7 weeks ago, # |   0 oh god
 » 7 weeks ago, # |   -21 another delay?!
 » 7 weeks ago, # |   0 10 minutes delay!
 » 7 weeks ago, # |   -8 oh delaycoder
 » 7 weeks ago, # |   -11 waitcoder
 » 7 weeks ago, # |   -11 hey,why another delay. Made me thought i did sth wrong.
 » 7 weeks ago, # |   +47
 » 7 weeks ago, # |   +28 Oooooooooooooooops, I get AC in C at 23:12. TAT
 » 7 weeks ago, # | ← Rev. 2 →   +1 In A we can just look at numbers on even positions and swap with maximal of their neighbours if needed.
 » 7 weeks ago, # |   +23 Hi,I think the testcases of A maybe a little weak.A wrong way to solve the problem is to compare every adjacent element one by one. Here is the link of the wrong solution my wrong codeAs you see, it only get WA*1.When I was chatting with my friend hellojim after contest, I found his AC solution is this wrong way! his codeThis testcase can hack him.6 8 1 9 2 10 3 11 4 12 5 6 7He gives 6 1 3 5 7 9 11 instead of 5 1 3 5 7 9Hope there will be after contest hacks.
•  » » 7 weeks ago, # ^ |   0 was about to say the same! my solution perhaps can be hacked by the same test case as well!
•  » » 7 weeks ago, # ^ |   +37 Thanks. It's now uploaded as after-contest-001.txt.
 » 7 weeks ago, # |   +68 Problems as unpleasant as always.
•  » » 7 weeks ago, # ^ |   +10 LOLdo you know how much effort Author make for such a good problemset :(
•  » » 7 weeks ago, # ^ |   +51 For some function defined as a lexicographically minimum permutation of $S(x)$ find the existence of inverse. My brain is already exploding. If I tried this, I will definitely miss or flip some words and solve a different problem :)For C, I just wrote brute-force and found the rule.But I don't think it's unpleasant. I just think "why I have to use my time on this?", but for somebody it should be good.
•  » » 7 weeks ago, # ^ |   +48 Problems as pleasant as always
 » 7 weeks ago, # |   +9 Hi, can anyone explain logic behind B's DP more clear than in editorial? I understand where we get from the interval [l,r) for each a[i], but have absolutely no idea why do we add dp[i]+=dp[i+1]?
 » 7 weeks ago, # | ← Rev. 3 →   +54 This is probably similar to the editorial for D, but I think it's more natural.For any string S, divide it into maximal groups such that each group has size >= 3 and is a substring of ABCABCABC... For example, when S = ABCABBCABCACBACABBCA, we have the partition [ABCAB][BCABCA]CBA[CAB][BCA]. Within each group (e.g. [ABCAB]), mark the first 3 letters. So, we have [(ABC)AB][(BCA)BCA]CBA[(CAB)][(BCA)]Now, we use inclusion-exclusion on the number of ()s we choose. We just need to compute for each k, the number of ways to choose a string S and choose k ()s from it. It turns out that this is easy to compute! The main observation is that once we determined the letters outside the ()s, the number of ways to determine the letters inside the brackets is of the form 2^a*3^b (with b=0 or 1).e.g. Suppose we know S = ()AB()BCACBA()() with the initial () stuck to the beginning of the string. Then, the number of ways to choose the letters in () is 3*2^3. If the initial () is not stuck to the beginning, the number of ways is 2^4.We can enumerate those 2 cases and in each case, the answer is 2^a*3^b*some binomial coefficient.
•  » » 7 weeks ago, # ^ |   +8 Cool, Thanks!
 » 7 weeks ago, # | ← Rev. 3 →   +39 In problem D, the multivariate generating function to the answer is $\large F(a,b,c) = \frac{ab+ac+bc-a-b-c}{a+b+c-2abc-1}$In particular, it means that the answer is $[a^A b^B c^C] F(a, b, c)$ and that it follows the recurrence ans[A][B][C] = ans[A-1][B][C] + ans[A][B-1][C] + ans[A][B][C-1] - 2*ans[A-1][B-1][C-1]Unfortunately, I don't know how to solve the problem further with this, as multivariate genfuncs are hard...
•  » » 7 weeks ago, # ^ |   +26 To find $[a^Ab^Bc^C](1 + 2abc - a - b - c)^{-1} = \sum_k[a^Ab^Bc^C](a + b + c - 2abc)^k$, one can see that all monomials of the right hand side look like $a^ib^jc^k(-2abc)^l$, and try all possibilities for $l$, deducing the other exponents from it along with $(A, B, C)$. To find $[a^Ab^Bc^C]F(a, b, c)$, one just find some coefficient of the denominator inverse for each summand of the numerator
•  » » » 7 weeks ago, # ^ |   +13 Wow, very cool! Thanks!
•  » » 7 weeks ago, # ^ |   +38 Can you explain how did you come up with this formula?
•  » » » 7 weeks ago, # ^ |   +28 Yes.
•  » » » 7 weeks ago, # ^ |   +21 Alright, I found how to eliminate $(1-abc)$ in my calculations and I got a similar function now. I think that the correct expression is $F=\frac{3abc-a-b-c}{a+b+c-2abc-1}$and my guess would be that you forgot to sum up functions corresponding to having two correct symbols in the end, but... My method involved solving a system of 6 linear equations (3 after simple substitutions) and it took me almost an hour :( So I still would like to hear the method.My idea was to kind of build Aho-Korasik on forbidden substrings, then for each node in AK create a GF, then get linear equations from transitions in AK and then solve the system.
•  » » » » 7 weeks ago, # ^ |   0 Yes, you're right, I forgot about walks that end in the middle of an edge. After fixing it, I get the same formula.
•  » » 7 weeks ago, # ^ |   +51 Amazing approach. By the way, after I observe your recurrence I think there is a more simple way to explain it .Let F[A][B][C] be the answer of "a=A,b=B,c=C". Then consider add a character after the current string , ignoring the influence of the last three characters F[A][B][C] can be written as F[A-1][B][C]+F[A][B-1][C]+F[A][B][C-1] .But you need to subtract the cases that last three characters are "abc"/"bca"/"cab" and these string has never appeared in all but the last three.If A=B=C=1 ,then you need to subtract 3.If A+B+C>3 then the restriction is "The fourth-to-last character cannot be the third-to-last character -1" , there are two possibilities to choose the third-to-last character . So you need to subtract F[A-1][B-1][C-1]*2.
 » 7 weeks ago, # |   0 In problem C, how to prove that if there's adjacent 1 2, then we can immediately delete 1?
 » 7 weeks ago, # |   +8 What's $O(n\log^2n)$ solution of B?
 » 7 weeks ago, # |   +8 Where can I find the current GP30 standings?
•  » » 7 weeks ago, # ^ |   +3 We are now preparing official standings.Meanwhile, Clist has an unofficial one.
 » 6 weeks ago, # |   0 Can you do DP for Question D?(link here:AGC058_D)