IEEE Xtreme just ended. Let's discuss it here.
There were a lot of amazing problems.Pretty tough for me in my opinion.
I got stucked on bitonic sequence, I found the sequence on oeis but it was hard to optimise. Also, is there a simple way for Diameter Problem Again. Another one was sequence decompositon, very easy to implement but no idea where my code was failing after 70%.
Auto comment: topic has been updated by clerisy47 (previous revision, new revision, compare).
I was the setter of Bitonic Sequences. I did see some submissions that used FFT, although the main intended idea was an $$$O(N\sqrt N)$$$ solution, with a small constant factor, which allowed for $$$O(N)$$$ memory.
You can find the method here: degwer's blog.
Basically, it’s about optimizing the $$$O(N^2)$$$ idea that relies on the recursion:
but only for $K < \sqrt{N}$. For $$$K \ge \sqrt{N}$$$:
Here, we only care about $t \le \sqrt N$, since otherwise $$$K * t \gt N$$$.
The important is to link $$$x$$$ with $$$dp$$$ simply by substitution, yielding a recursion in terms of $$$x$$$. The same analysis applies to $$$\sum\limits_{1 \le i \le K} dp[N][i]$$$. The answer is $$$\sum\limits_{1 \le i \lt \lceil \sqrt N \rceil} dp[N][i] + x[N][0]$$$.
One of the coolest problems. I couldn't get the full score, but I know some people who did by reading the math papers linked in OEIS: https://oeis.org/A001523.
That problem was very cool, I didn't knew about FFT or sqrt N trick tho.
How is "Sequence Decomposition" solved?
I can give a somewhat informal sketch of the solution, although there are several cases that need to be analyzed by hand.
First claim: the last 2 can always be paired with the last 1.
Proof: if not, that 1 pairs with another 2, but we can swap 2s without breaking the pattern, so the last 1 can match the last 2.
Second claim: each 1 (from right to left) can be matched with the last available 2 to its right.
Proof: if a 1 matches a 2 that "should" belong to an earlier 1 ($$$s_0$$$), we can swap this 2 with the 2 of that earlier 1. All such 1s and 2s are interchangeable, so the greedy pairing is safe. If no 2 is available, the 1 starts a new subsequence.
Idea: first, greedily match 12 pairs from right to left. Then, scan left to right taking the unused 1s: greedily form 12 pairs as new subsequences when possible, otherwise consider them secondary. Note that this is always possible without running out of 0s, so all subsequences can be completed.
problems seem very interesting, where can I solve them?
Here is the link: https://csacademy.com/ieeextreme19. I am not sure if you can submit at the moment, but they always post it later under https://csacademy.com/ieeextreme-practice/tasks/
EDIT: One of my friends tried and they did not have access to the portal since they did not participate in the IEEEXtreme. Later, it will be posted in the other link I provided.