Xellos's blog

AtCoder Regular Contest 059 / Beginner Contest 043
By Xellos, history, 8 years ago, In English

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

Also post-contest discussion, I guess.

  • Vote: I like it
  • +55
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +29 Vote: I do not like it

クマ means "bears".

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +61 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    And now we can add FFT and get solution.

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Can someone help me with ARC 59 — E?

→ Reply