EDU round 168 was today. Since I was eating breakfast, I started by reading F and quickly got the idea :D. Then I couldn’t think of anything for E, so I got ABCDF, then ran out of time implementing a sqrt solution on E.
A few notes:
For B I didn’t read that there was only 1 connected component, that would have made things easier…
For F the idea is that you can move the coins similar to fibonacci base, so the coins represent a number. The minimum # of 1’s in a fib number can be found using Zeckendorf representation. Then, knapsack gets AC.
For E:
My solution takes advantage of the fact that either $\text{level} \le \sqrt{n}$, or $k \le \sqrt{n}$. For small k, brute force, and for larger k, you can binary search on prefix sums to find the intervals.
Speaking of intervals, there were always $\mathcal{O}(N \log N)$ of them. That motivates us to just compute these intervals. You can maintain the the position of every $k$ at level $i$, and update these in $\mathcal{O}(\log N)$ each. Once they reach the end, you can remove them.
Of course, there is another solution. Note that for an index $i$, it will be fought by $k \lt k_0$ and skipped otherwise. You can see this be visualizing the levels for each $k$ (it feels intuitive that it is monotonic). Then, the minimum $k_0$ such that it is skipped can be found with binary search: index $i$ will be skipped if and only if $\left\lfloor\frac{\text{monsters fought by k}}{k}\right\rfloor+1 \gt a[i]$. You can find which monsters were fought by k by storing the $k_0$’s for each index in a data structure such as a segment tree.
Well, that was a pretty good round. Too bad I won’t gain much rating :(.
