Блог пользователя Xellos

Автор Xellos, история, 8 лет назад, По-английски

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 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

クマ means "bears".

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

Is there going to be an editorial (in English) for this contest unlike the previous regular contest?

»
8 лет назад, # |
  Проголосовать: нравится +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 лет назад, # ^ |
      Проголосовать: нравится +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 лет назад, # ^ |
    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 equviprobable

    It'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 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    And now we can add FFT and get solution.

    Anyway, the intended O(n2) solution much more beatiful.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +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 лет назад, # ^ |
      Проголосовать: нравится +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] = 1

    f[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 лет назад, # |
  Проголосовать: нравится 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.

»
5 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Can someone help me with ARC 59 — E?