### Xellos's blog

By Xellos, history, 8 years ago,

A reminder that AtCoder doesn't only have Grand Contests, but also these. Starting time: in the past.

Also post-contest discussion, I guess.

• +55

 » 8 years ago, # |   +29 クマ means "bears".
 » 8 years ago, # | ← Rev. 2 →   +17 Is there going to be an editorial (in English) for this contest unlike the previous regular contest?
 » 8 years ago, # |   +13 Well, this was easy. Stupid MLE on the last problem... btw the main part of my solution was computing L-tuples of balanced sequences of parentheses with N - L parentheses in total (L = |S|). That's a L-tuple convolution of one array with itself, which can be computed in in the same way as fast exponentiation, since convolution is associative.
•  » » 8 years ago, # ^ |   +13 Yes, the last problem of last ARC was exceptionally hard but usually ARC tends to be easy. Anyway, you can predict the difficulties from point values.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +61 It may also be solved in O(n2). Let dp[n][l] = number of ways to get length l after n keystrokes. Now answer is dp[n][l] / 2^l with l = s.size() since all strings of same length are equviprobableIt's seems that it's a solution from editorial (I've found 2^m and O(n^2) in it) but I'm not sure.
•  » » » 8 years ago, # ^ |   +21 Yes, this is intended.
•  » » 8 years ago, # ^ |   +5 And now we can add FFT and get solution.Anyway, the intended O(n2) solution much more beatiful.
•  » » » 8 years ago, # ^ |   +5 Indeed.Recently, I think a lot in terms of convolutions and solving the last problem with FFT. It's probably connected to FFT problems becoming much more common recently.
•  » » 8 years ago, # ^ |   +16 I "solved" it in different way. First observe that the answer depends only on N and L = |S|. Then write O(N3) brute-force and display results for N, L ≤ 10. Look at these values and observe that: f[i][i] = 1f[i][j] = f[i - 1][j - 1] + 2 * f[i - 1][j + 1]. f[i][j] = f[i][j - 1] if i = j(mod2). Precompute f[1][N] for N = 1, 2, ..., 5000 with brute-force and include those values in your code (I searched for the sequence in OEIS but failed). Then just use observed formulas to fill the f[][] table.
 » 8 years ago, # |   0 Can someone please explain dp approach to last problem.. I didnt get the part that all strings were equiprobable..thus I was trying an alternate dp state..dp[i][j]->denotes that we have made i moves and have got string of length j which matches first j characters of input string(basically a prefix of length j)..however I couln't figure out the transitions.
 » 4 years ago, # |   -10 Can someone help me with ARC 59 — E?