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

Also post-contest discussion, I guess.

# | User | Rating |
---|---|---|

1 | Benq | 3601 |

2 | jiangly | 3598 |

3 | orzdevinwang | 3561 |

4 | ecnerwala | 3542 |

5 | cnnfls_csy | 3539 |

6 | Radewoosh | 3532 |

7 | inaFSTream | 3478 |

8 | maroonrk | 3451 |

9 | tourist | 3434 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | adamant | 166 |

3 | awoo | 161 |

3 | TheScrasse | 161 |

5 | nor | 160 |

6 | maroonrk | 158 |

7 | SecondThread | 155 |

8 | Um_nik | 151 |

9 | Geothermal | 145 |

9 | BledDest | 145 |

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

Also post-contest discussion, I guess.

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/02/2024 05:43:03 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

クマ means "bears".

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

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 withN-Lparentheses in total (L= |S|). That's aL-tuple convolution of one array with itself, which can be computed in in the same way as fast exponentiation, since convolution is associative.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.

It may also be solved in

O(n^{2}). 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.

Yes, this is intended.

And now we can add FFT and get solution.

Anyway, the intended

O(n^{2}) solution much more beatiful.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.

I "solved" it in different way. First observe that the answer depends only on

NandL= |S|. Then writeO(N^{3}) brute-force and display results forN,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] ifi=j(mod2).Precompute

f[1][N] forN= 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 thef[][] table.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.

Can someone help me with ARC 59 — E?