In the last round (round 1048), I solved the (2138C2) Maple and Tree Beauty (Hard Version) using divide and conquer method and NTT. The problem could be solved by doing binary search on the length of the LCS. For that I can precalculate the number of nodes at every depth, afterwards assign all nodes of a certain depth either white or black color. I can check whether it’s possible by calculating all possible subset sums using NTT and divide and conquer. But every search I would have to calculate NTT using divide and conquer technique which would get me TLE.
To bypass this repeated calculation I tried a modified method of DnC. At first I calculated the NTT for the left subrange for divide and conquer. Afterwards I checked if I only considered the left subrange and could get a common prefix string of that range for the tree. If I could, then I moved to the right subrange, otherwise move to the left subrange. And afterwards repeatedly execute this process by dividing that subrange into left and right. This made sure that I am calculating divide and conquer NTT for the at most twice for each subrange of DnC. However, that also meant that the other half wouldn't be traversed. Making it equivalent to calculating the answer for the whole tree just once.
This was definitely a overkill and not the intended solution, but I knew it could be solved with DnC NTT so I just did. It was fun doing so. Did anyone else try the same idea?
I tried Divide and Conquer FFT with complexity $$$O(n \log^3 n)$$$ (scroll to the bottom of this submission), saw that it took $$$5999 \text{ ms}$$$ and that most users solved C2 immediately after solving C1, and then realised that using a bitset solution in $$$O(n^2/\omega)$$$ was probably safer (and implemented a bitset solution).
Divide and Conquer NTT with mod=998244353. Took 514ms. (Time limit was 6000ms). 337629930
you can also do nsqrtnlogn / 64 with bitset https://codeforces.me/contest/2139/submission/337673118
btw, I don't think that you need binary search because the answer is either the depth of the lowest leaf or the depth — 1
Can you give a proof why?
So it is true that the lowest leaf depth is going to be the upper bound. Let's sort the nodes by their depth (with ones with the same depth just being in arbitrary order) and assign $$$1$$$ to the first $$$k$$$ nodes and $$$0$$$ to the last $$$n - k$$$ nodes. What do we find in such an order? Well there's only one depth where we have $$$1$$$ s and $$$0$$$ s, so the LCS in such an assignment can just skip that depth and be the lowest leaf depth — 1. But we need dp to check if we can make it the lowest leaf depth.
btw, is your tie built into your shirt or what?
Okay, got the proof. You are actually talking about the highest leaf, I was a bit confused because I read lowest == deepest. Let the depth of leaf D, then the answer is either D or D — 1. It's because until D, the number of nodes per depth is non-increasing, after that it can be any arbitrary number. So, the condition may not hold. This is so much easier compared to this solution :3 If this was the intended solution I doubt it would have even half of the solves during contest.
Anyways, it's not a tie actually. I was wearing a "Punjabi", the collars are designed that way which makes it look like a tie. Technically, yes, it's built in. I was wearing a hoodie on top of the Punjabi in this photo