Hello everyone!
We are very happy that our previous contest was held without issues.
The next Premier round is here.
Premier rounds are currently the highest level among our contest series. We hope you enjoy it!
- Start Time: Sunday, 3 May 2026, 14:35 (UTC)
- Duration: $$$2$$$ hours, $$$30$$$ minutes
- Registration: https://repovive.com/contests/6
The contest is rated for everyone.
- Writers: AmShZ, Hamed_Ghaffari and AmirAli-Asgari
- Testers: Amoo_Safar, Ali_BBN and Shayan
See you on the leaderboard!
UPD1: Fortunately, the contest went smoothly without any issues. You can view the solutions in the Learn tab.
Congratulations to the top participants:
- 1: 244mhq
- 2: Um_nik
- 3: HIR180
- 4: potato167
- 5: jiangxinyang
- 6: hitonanode
- 7: Rubikun
- 8: Golovanov399
- 9: DanielChang
- 10: MarcosK
Auto comment: topic has been updated by AmShZ (previous revision, new revision, compare).
The first Premier Round with 2:30 duration.
Yeah, it was painful for some participants.
Don't miss the contest!
Happy to see a new premier contest
Reminder: Less than 4 hours until the contest.
30 minutes
I don't see for what the vive coins are? Will it's use be added later?
So I managed to make a proper solution for F that isn't probabilistic (and doesn't use bitsets or platform-specific code). I'm not subtracting anything in knapsacks, only combining items (subtree sizes) with distinct weights, independently for each vertex.
Lots of tiny optimisations all around, such as knapsacking only up to sum $$$v-d_v$$$ instead of $$$n$$$, special cases for adding a small number of items of some weight or some number of items of a small weight, adding items of distinct weights in the order of increasing weight*count, and a surprisingly big one: hey we got some sequence of knapsack states, let's rebuild some a solution greedily first and if that uses all distinct weights, we don't need to check rigorously which ones can be used in a solution.
It fits reasonably within the time limit as a result, but some of these optimisations are doing a ton. I wonder if it has a better worst case than $$$O(N^2 \sqrt{N})$$$. OTOH $$$O(N^2 \log{N})$$$ is very tough to fit within 2s TL with these constraints too!
Thanks for sharing the details!
You are right, the time limit was quite close to the edge. There is an (O(n^3 / 32)) solution using bitset knapsack, and it was important for us that this approach would not pass. Because of that, the current constraints were the best trade-off we could find.
Our own solutions passed in around 400 ms, so we felt the intended approaches had enough margin. But overall, I agree that the limit was a bit annoying, especially for optimized non-probabilistic alternative solutions like yours.