### tfg's blog

By tfg, history, 12 months ago,

In yesterday's div1+2 contest problem E (1804E) required an optimization for bitmask dp looking for cycles that has appeared waaaaaay before in cf, dating back to the beta days in this problem. It seems that it wasn't that well known, looking at the number of TLE submissions, so I'm posting this blog to remind people that there are old rounds/contests and they do have some good or educational problems.

One silly lesson that I learned from an old-ish problem is that writing some combinatorics problems in polynomial form sometimes might expose some observations that might not be obvious at first glance. Perhaps if you have some similar experience you could share it in this blog, as there would be at least one person interested in seeing it (me).

• +152

 » 12 months ago, # |   -56 > ... there are old rounds/contests and they do have some good or educational problemsunlike modern problems
•  » » 12 months ago, # ^ |   +344 You dont participate since 2018 dude. Go use your dial up internet to hate somewhere else
•  » » » 12 months ago, # ^ |   +145 This might be one of the sickest burns in CF history.
•  » » 12 months ago, # ^ |   -57
 » 12 months ago, # | ← Rev. 2 →   +74 I have one cute problem that could be trivialize by writing the problem into polynomial form.Problem: Given non-negative integer $N, M$, find the number of non-decreasing sequence $A$ with length $N$ s.t. $0 \le A_i \le M \text{ }\forall 1 \le i \le N$ Solutionconsider enumerate the difference array $D$ of $A$, apparently $D_i$ must be non-negative and the sum should be no more than $M$, so we will get$answer = \sum\limits_{k = 0}^M [x^k](\sum\limits_{i = 0}^{\infty} x_i)^N = [x^M](\frac{1}{1 - x})^{N + 1} = \binom{N + M}{M}$by the fact that multiply a polynomial with $\frac{1}{1-x}$ is equivalent to taking prefix sum, and another fact that doing prefix sum $N + 1$ times over an array will give you $\binom{M + N}{M}$ at the $M$-th entry.and you can realize there actually exist a simple way to make one to one relation between the array $A$ and path going from lower-left to upper-right, which is quite amazing!
•  » » 12 months ago, # ^ |   0 I think this is a classical result in math Olympiad, which suddenly rings a bell for me.
 » 12 months ago, # | ← Rev. 2 →   +44 This year's IOI had a dp problem which rewritten in polynomial form required multiplying out a lot of linear polynomials, take the derivative and evaluate at 1. We can use Leibniz's rule to see that we need to calculate the product of the linear coefficient of one factor and multiply it with all the other factors evaluated at one.
•  » » 12 months ago, # ^ |   -13 This year's IOI?
•  » » » 12 months ago, # ^ |   +21 Obviously he means IOI 2022.
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   -67 Of course I know that, but it doesn't change the fact that it's wrong. Imagine someone reading the comment later this year.
•  » » » » » 12 months ago, # ^ |   +4 If you read ppavic's comment in December it will say "9 months ago", everyone will deduce that it's about IOI 2022, lol. Or maybe it's about IOI 2027 ?????!!1!1?
•  » » 12 months ago, # ^ |   0 Are you talking about IOI 2022 Fish? I didn't know that it has a solution with polynomials and derivative.
•  » » » 12 months ago, # ^ |   +21 No, about IOI 2022 Circuit.
•  » » » » 12 months ago, # ^ |   +5 Lmao, i solved that problem in contest and still didnt know what he was talking about
 » 12 months ago, # |   +46 After read this post I started thinking about how to optimize this problem to $O(n^2 2^n)$, It's really a cool idea (I don't know if it's the same idea) that you can first find all cycles containing vertex 20, then find all cycles containing vertex 19 and not containing vertex 20 and so on.. $O(n^2*2^n + (n-1)^2*2^{n-1} + ... ) = O(n^2 2^n)$ Unfortunately I wrote 140 lines of code in 1804E but at least I got AC in first try.
 » 12 months ago, # |   +10 n/1+n/2+n/3...+n/n = n*log2(n) I forget about it every time XD
•  » » 12 months ago, # ^ |   +50 nope it's $n\times \ln(n)$ but not a big problem
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +21 It's also not that. If we want to be precise then it's O(NlogN). Before someone replies this with something even more precise, I know that there's a known bound for the error.
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   -49 gonna
 » 12 months ago, # |   +14 Late to the party, but shameless self-plug SpoilerDuring its preparation, we solved it in $O(n*3^n)$, $O(3^n)$, $O(n^3*2^n)$, $O(n^2*2^n)$ and $O(n*2^n)$, we benchmarked all of them. So I knew what time complexities would be acceptable in 1804E.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 I understand $O(n^{2}*2^{n})$ solution but how to do in $O(n*2^{n})$ ?NVM, got it.
 » 12 months ago, # | ← Rev. 2 →   +10 I've actually seen cycle finding bitmask dp relatively recently (only 1 year ago compared to 13 years ago) in this usaco problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=1209Its a pretty neat trick and I agree that there might be value in practicing older problems.