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).
> ... there are old rounds/contests and they do have some good or educational problems
unlike modern problems
You dont participate since 2018 dude. Go use your dial up internet to hate somewhere else
This might be one of the sickest burns in CF history.
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$$$
consider 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!
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.
This year's IOI?
Obviously he means IOI 2022.
Of course I know that, but it doesn't change the fact that it's wrong. Imagine someone reading the comment later this year.
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?
Are you talking about IOI 2022 Fish? I didn't know that it has a solution with polynomials and derivative.
No, about IOI 2022 Circuit.
Lmao, i solved that problem in contest and still didnt know what he was talking about
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.
n/1+n/2+n/3...+n/n = n*log2(n) I forget about it every time XD
nope it's $$$n\times \ln(n)$$$ but not a big problem
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.
Late to the party, but shameless self-plug
During 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.
I understand $$$O(n^{2}*2^{n})$$$ solution but how to do in $$$O(n*2^{n})$$$ ?
NVM, got it.
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=1209
Its a pretty neat trick and I agree that there might be value in practicing older problems.