Hello!
Currently, the qualification phase of Yandex Cup in the “Algorithm” track is taking place.
Qualification takes place in two formats: sprint and marathon.
Both competitions will end on Monday, November 7, 2022 at 23:59 (MSK).
As the author of one of the tasks, I invite everyone to participate.
Information about other Yandex Cup tracks can be found on the website.
As a tester, I invite you all to participate in the competition! :)
What's the difference between sprint and marathon in Yandex Cup context, I couldn't find info on site
Sprint: you choose when to start and then you have 120 minutes to solve 6 algorithmic problems.
Marathon: you have all the time until the end of the competition to solve one optimization problem.
And what the difference between them will be in final?
There is no difference for the final round this year. Final will be short contest (from 120 till 180 minutes), so there are just two ways to qualify.
I hope once Yandex Cup will have two separated algorithmic track as it was several years ago in Yandex Algorithm.
And how marathon round will conduct? 5 hours for solving one problem? Or 3 days as Irunner challenge?
Is there any T-shirts for finalists? :)
What about Yandex Cup 2021 algorithm finalists? Did they get t-shirts?
No.
I have several questions for the final round:
The website seems to be lacking information.
If you go back to the website now and log in, you will be able to click a button to confirm your attendance for the final round. After doing so, you get a button that brings you to the competition page which has the time and duration listed. Hope this helps!
Right. I can access the competition page and it answers all my three questions above. Thank you! Take my upvote.
Wow. Problem A from hell in today's Final Round for me… Tried 2 super-convoluted DP approaches, and ultimately couldn't make it work. That was an unexpected level of complexity after solving 4 Qual problems. Any slight hints for A?
Greedy :)
Problem A. Max and the erudite competition
For solving this problem you should think as a coach. You can start from something simple.
Look at your worst person $$$x$$$ from your team. How can he help to his team?
He can try to defeat strongest person $$$y$$$ from another team $$$\left(y \lt x\right)$$$. It would be the best thing he could do for his team.
If $$$x$$$ can't do this, then do nothing right now. Leave him alone for now and let him rest. Try next person.
When all of your team members will finish their attempts, try to talk with rest team players and convince them to try to do at least a draw.
Rest team members will lose. No matter how sad it may sound.
My C++ solution
Can we do the same strategy in strongest to weakest order for our team for winning stage? I think it will also give maximum wins possible but not sure about number of draws.
Alternate approach cause I kept messing up my greedy lol:
Binary search for the minimum number of losses, L by matching your L weakest players against the L strongest opponents. Then greedily pair your strongest remaining (N — L) players against the weakest (N — L) opposing players. This isn't optimal on its own. There will be some wins and some draws. We can increase the number of losses one at a time to see if we can get any of these draws to flip. We can count many draws will change on the i-th additional loss by getting the length of each subarray of draws. Ex:
(Note that the first array is always larger, since we binary searched to get rid of all the losses)
The lengths of each draw-subarray are 1, 1, 3, 2 (ex. there are 2 draws involving the element '4'). You can think of each new loss as cyclic-shifting the top array to the left. On the first additional loss, we'll create 4 new wins. On the second additional loss, we'll create 2 new wins. On the third additional loss, we'll create 1 new win. (It's fine if one of these wins is actually the same as the new loss [as is the case with the first new loss here]; we're just subtracting two points for every new loss).
Code:
Will there be an editorial? I want B and C. Thanks.
C: Fix N mod 3 (let's call it r) and binary search on N. For each prime factor of A, calculate how many times p^a is a factor of N!!! for each a >= 1 and add them up to get the total exponent of p in N!!!.
This can be done by counting the number of solutions to p^a | (3k + r). If p is 3, then we need r = 0 and k is a multiple of p^(a-1). If p is not 3, then the solutions will be k = p^a * anything + i, where i is whichever of (-r)/3, (-r + p^a) / 3, or (-r + 2p^a) / 3 is an integer.
Thank you sir!
Will there be an awards ceremony? Also, will the problems be available for upsolving?
Like previous years we are preparing online room to discuss Yandex Cup. We will return with it in some days.
Upsolve or look at problems one can here: https://contest.yandex.com/contest/42710/problems/
Open upsolving please.
Upsolving is opened here. Letters for problems are shifted by 6 problems from the qualification round.
How to solve E?
CHT / LiChao tree.
Cool,Thank you!
What's the intended time complexity for F? I managed to pass $$$O(N^{5/3})$$$ but it took quite a bit of constant optimization.
I will assume that $$$n = q$$$, expected complexity is $$$O(n\sqrt{n})$$$, but TL wasn't strict.
Let's replace $$$r$$$ by $$$\frac{r}{k}$$$ and name value that we need to calculate as $$$F(r, d)$$$.
It's easy to calculate $$$F(r, d)$$$ from $$$F(r - 1, d)$$$, main trick is that we are able to calculate $$$F(r, d)$$$ from $$$F(r, d - 1), \ldots, F(r, d - k + 1)$$$.
Do to this, let's notice that:
$$$\binom{x}{d}=\sum^{i=k}_{i=0} \binom{x - k}{d - i}\binom{k}{i}$$$
It's basically Vandermonde's identity.
Let's sum both parts for $$$x$$$ divisible by $$$k$$$ and not greater than $$$(r + 1) \cdot k$$$, we will get:
$$$\binom{(r + 1)\cdot k}{d} = \sum^{i=k}_{i=1} F(r, d - i)\binom{k}{i}$$$
(I moved part with $$$i = 0$$$, because evething except $$$\binom{(r + 1)\cdot k}{d}$$$ will cancel out).
From here, we can find $$$F(r, d - 1)$$$, if we know $$$F(r, d - 2), \ldots, F(r, d - k)$$$.
Let's go back to original problem.
We will also assume that $$$k \le \sqrt{n}$$$, otherwise we can calculate answer for each query in $$$O(\frac{n}{k})$$$ with total complexity $$$O(\frac{n^2}{k})$$$.
To solve the problem, let's fix some value of $$$B$$$ and calculate all values of the form $$$F(i \cdot B, x)$$$ for $$$x \le n$$$.
To do this, let's calculate $$$F(i \cdot B, x)$$$ for $$$x < k - 1$$$, we can easily do it in $$$O(\frac{n}{k} \cdot k) = O(n)$$$ for all $$$i$$$.
Then, for each $$$i$$$ we can find the remaining values in $$$O(nk)$$$(recovering $$$F(i\cdot B, d)$$$ from $$$F(i \cdot B, d - 1), \ldots F(i \cdot B, d - k + 1)$$$), so in total this part takes:
$$$O(nk \cdot \frac{n}{kB}) = O(\frac{n^2}{B})$$$.
Then, if we have the query $$$r, d$$$, let's just find largest $$$i$$$ such that $$$i \cdot B \le r$$$ and calculate answer from $$$F(i \cdot B, d)$$$ in $$$O(B)$$$. So, total complexity for queries will be $$$O(nB)$$$. Choosing $$$B = \sqrt{n}$$$ gives the desired complexity.
Cool, the implementation is very short.
Where did you get $$$O(\frac{n}{kB}\cdot k)$$$ from? I know how to do it in $$$O(k^2)$$$ per $$$i$$$ using the formula you provided (for a total of $$$O(\frac{n}{kB}\cdot k^2)$$$).
Sorry, it was wrong, I think it's easier just to do it naively for every fixed value of $$$x$$$ resulting in $$$O(\frac{n}{k}\cdot {k}) = O(n)$$$ (your way is faster, but of course it doesn't change complexity).
another passed solution that runs in time complexity $$$\mathcal{O}(n \sqrt{q \log n / k})$$$, where $$$n = \max(r)$$$. also took a bit of constant optimization on it.
let $$$T$$$ be the block size, and $$$F_u(x) = \sum_{i = 1}^{u T}(1 + x)^{i k}$$$. After preparing the first $$$n$$$ factorials and their inverse, we iterate for each $$$u = 0, 1, \ldots, \lfloor n / k / T \rfloor$$$ and process queries with $$$u k T \leq r < (u + 1) k T$$$ using $$$[x^d] F_u(x)$$$ and at most $$$T$$$ extra binomial coefficients, so the total complexity will be $$$\mathcal{O}(n + n^2 \log n / k / T + q T)$$$, which has a minimal value when $$$T = n \sqrt{\log n / k / q}$$$.