The ICPC Northern Eurasia Finals (a.k.a. Northern Eurasia Regional Contest) took place on 13 December 2023. The onsite participants competed on four venues: St. Petersburg, Russia; Novosibirsk, Russia; Astana, Kazakhstan; and Kutaisi, Georgia.
Congratulations to the medalists of the contest:
Rank | Team | = | Time |
🏆 1 | MIPT: Yolki-palki (Pechalka, Tikhon228, Kapt) | 12 | 1266 |
🥇 2 | HSE: Youthful Passion Fruit (alexxela12345, daubi, talant) | 10 | 982 |
🥇 3 | SPb ITMO: pengzoo (iakovlev.zakhar, golikovnik, DishonoredRighteous) | 9 | 713 |
🥇 4 | MIPT: Log-rank conjecture (sadovan, receed, Jatana) | 9 | 759 |
🥈 5 | SPb SU: block of cats (LeoPro, fastmath, turmax) | 9 | 843 |
🥈 6 | SPb SU: \_ -> chill (UnstoppableChillMachine, D.Pavlenko, Volkov_Ivan) | 9 | 904 |
🥈 7 | MIPT: In God We Trust (antonis.white, gop2024, PeregudovSergey) | 9 | 935 |
🥈 8 | MIPT: Shawarmasters (stepanov.aa, RP-1, PBBx0) | 9 | 1072 |
🥉 9 | HSE: Muffix Sassif (sevlll777, crazyilian, tem_shett) | 9 | 1076 |
🥉 10 | HSE: Drunk Driving in Moscow (Siberian, blyat, Nybik) | 9 | 1223 |
🥉 11 | HSE: am nyam) (vaaven, Ormlis, vsinitsynav) | 9 | 1368 |
🥉 12 | MIPT: Wake right (ZorikVar, ShadowLight, serg3000) | 8 | 905 |
As a result, several teams qualified for the ICPC Finals, which will be held in 2024 in Astana, Kazakhstan:
Rank | Team | = | Time |
🏆 1 | MIPT: Yolki-palki (Pechalka, Tikhon228, Kapt) | 12 | 1266 |
🥇 2 | HSE: Youthful Passion Fruit (alexxela12345, daubi, talant) | 10 | 982 |
🥇 3 | SPb ITMO: pengzoo (iakovlev.zakhar, golikovnik, DishonoredRighteous) | 9 | 713 |
🥈 5 | SPb SU: block of cats (LeoPro, fastmath, turmax) | 9 | 843 |
13 | Belarusian SU: 1: Last hope (MathBoy, ne4eHbKa, VEGAnn) | 8 | 944 |
14 | AITU: jaujurek 3 bala (dolbaeb, dimachine, nkamzabek) | 8 | 1089 |
15 | Yerevan SU: SD3 (mcdx9524, Andreasyan, erankyun) | 8 | 1446 |
16 | MAI: 1 (Inyutin, Belousov, Plyushkin) | 7 | 551 |
18 | Belarusian SUIR: 1: So Stuffy (kartel, p3rfect, romarkovets) | 7 | 673 |
19 | Novosibirsk SU: 1: Avdim last hope (amokrousov, Lylova, Timonnable) | 7 | 770 |
21 | Skoltech: Caravella (madn, kek1234, Goldman) | 7 | 819 |
22 | Tbilisi SU: Darwin Nunez (Macharashvili, Pipia, Khvedelidze) | 7 | 834 |
It is possible that the ICPC committee will increase the quota and allow more NERC teams to attend the Finals.
For the contestants who did not participate onsite, there was an online mirror on Codeforces: 2023-2024 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred). I would like to especially highlight the teams who scored total during the contest:
Rank | Team | = | Time |
1 | xinyoudui: PubabaOnO, orzdevinwang, jqdai0815 | 12 | 842 |
2 | HoMaMaOvO: maroonrk, hos.lyric, maspy | 12 | 1266 |
3 | P+P+P: 244mhq, 353cerega, 998kover | 12 | 1339 |
The problemset was prepared by the jury headed by elizarov: cdkrot, VArtem, Aksenov239, goldvitaly, tourist, kgeorgiy, isaf27, izban, _LeMur_, orz, niyaznigmatul, PavelKunyavskiy, pashka and Elena Kryuchkova:
You can find the PDF statements here, and the tutorials here.
Finally, you are welcome to share your thoughts on the problemset in the comments. Also please tell me if there are mistakes in this post. Thanks to all of you who participated and attempted our problems!
In Problem A why this test case , print 11
When I withdraw -5, the accumulator will become negative, right?
Yes, the answer to this tests seems to be
4
, not11
.Thanks I think test cases not strong enough This submission print 11 : https://codeforces.me/contest/1912/submission/237095249
Yes, you're right, the tests could be better.
pretty unfortunate to see an LGM (Ormlis) not qualifying for World Finals...
i was there and i saw hes been trying soo hard but couldnt succeed that was sooo saaad T_T T_T T_T like this comment if ur sad to
true i was there as well and he just couldn't handle the pressure. too bad gl next time tho
So jury's solution to problem F is basically a heuristic? How did you guarantee that all the tests are correct?
You're right. Since I was not able to prove the convergence, there is no guarantee, only several pieces of evidence. One evidence is that, during the contest testing, all other solutions had an absolute error less than $$$10^{-10}$$$. Another strong evidence is that, when I tried two starting approximations, one unital (i.e. less than the answer) and the other one $$$x_u = (n - 1)^2$$$ (i.e. greater than the answer), they both ended up as approximate solutions with absolute error less than $$$10^{-10}$$$. Since the small and the big starting points converged to basically the same point, it is highly believable that the real solution should also be near that point. (Maybe it is possible to prove some analogue of the squeeze theorem, in which case I will be able to certify the validity of each test. But, again, I did not prove that.) Another convincing fact is that in the end the distance between the current approximation and the next one is really small (that is, all $$$|L|$$$ equalities are approximately true). Generally, the vicinity of $$$x_n$$$ and $$$x_{n + 1}$$$ does not imply the vicinity of $$$x_n$$$ and $$$\lim x_i$$$ (e.g. $$$\sum_{i = 1}^n{\frac{1}{i}}$$$ is near $$$\sum_{i = 1}^{n + 1}{\frac{1}{i}}$$$ but $$$\sum_{i = 1}^{\infty}{\frac{1}{i}} = \infty$$$), but there are some additional conditions which may lead to it, e.g. alternation of the sign of $$$x_n - \lim x_i$$$. I am not a specialist in the theory of multidimensional dynamical systems, but I stronly believe that there should be a similar way to strictly prove the convergence in our case. Also not only $$$x_{10\,000}$$$ and $$$x_{10\,001}$$$ are close to each other, but also $$$x_{2\,000}$$$ and $$$x_{15\,000}$$$ are (and, I believe, everything in between is also near the answer, too, although I did not check that explicitly).
Following is my proof that it is a linear convergence when $$$n$$$ is considered as constant, and for each iteration the error reduces by a factor of $$$1+n^{-2}$$$. Please ignore dollar signs in the front of some lines, they are for preventing this bug.
Notations:
$$$n$$$ is the number of vertices.
$$$m$$$ is the number of leaves.
$$${\rm dis}(u,v)$$$ is the distance between $$$u$$$ and $$$v$$$.
$$$E(u)$$$ is the expected time for police to catch thief starting from $$$u$$$.
First, we have three important conclusions:
$$${\rm dis}(u,v)\ge 1$$$
$$$E(u) \ge \max {\rm dis}(u,v)$$$, because thief can always choose to go to the furthest leaf
$$$E(u)\le n^2$$$, because police can always choose a random leaf, the cost is less than $$$n$$$ and the chance is greater than $$$1/n$$$.
Then, we revisit the iteration formula
$ in geometric form, where we start from $$$B=(0,m-1)$$$, each leaf $$$v$$$ contributes a vector $$$\left(1/x_v,{\rm dis}(u,v)/x_v\right)$$$, and the slope of the endpoint $$$X$$$ is $$$x'_u$$$, where
$ We rewrite $$$x_v$$$ in the form of $$$E(v)/k_v$$$, then $$$X$$$ can be represented as
$ It's obvious that we always have $$$x_v>0$$$ during the iteration, hence $$$k_v>0$$$. We denote the vector $$$(1/E(v),{\rm dis}(u,v)/E(v))$$$ by $$$\overrightarrow{a_v}$$$. Then, the endpoint can be represented as
$ And also, at the fixed point we have each $$$x_v=E(v)$$$ and hence all $$$k_v=1$$$. Therefore, we can rewrite the fixed point of the iteration formula as the slope of $$$P$$$ being $$$E(u)$$$, where
$ Then, we aim to find both the lower bound and the upper bound of the slope of $$$X$$$ to prove its convergence and convergence speed.
Upper bound of $$$x'_u$$$
Because $$$E(u)\ge \max {\rm dis}(u,v)$$$ as mentioned before, we have that the slope of $$$P$$$ is larger than any slope of $$$\overrightarrow{a_v}$$$. Therefore, if current slope of $$$X\ge E(u)$$$, then $$$X$$$ always increases when $$$k_v$$$ decreases. This gives us an upper bound by setting every $$$k'_v=k_\min=\min{k_v}$$$. Formally, we define
and the slope of $$$X'$$$ is an upper bound of $$$X$$$.
We denote the $$$x$$$-coordinate of $$$P$$$ by $$$p_x=\sum 1/E(v)$$$. Then, we calculate the slope of $$$X'$$$ by finding out the $$$y$$$-coordinate of $$$OX'$$$ at $$$x=p_x$$$. There are six important points on the plane:
$$$O=(0,0)$$$
$$$B=(0,m-1)$$$
$$$P=B+\sum \overrightarrow{a_v}$$$, the slope of which is $$$E(u)$$$
$$$X'=B+k_\min \sum \overrightarrow{a_v}$$$, the slope of which is the upper bound
$$$Y$$$, the intersection of line $$$OX'$$$ and line $$$x=p_x$$$
$$$Q=\left(p_x,0\right)$$$, so the slope of $$$X'$$$ is $$$\frac{YQ}{OQ}$$$
We find that $$$\triangle X'OB$$$ and $$$\triangle X'YP$$$ are similar triangles, so $$$PY=(m-1)\cdot (k_\min^{-1}-1)$$$. Also, we can find a lower bound of $$$PQ$$$, where
Therefore, we have
Thus we have
$ Lower bound of $$$x'_u$$$
If the slope of $$$X'$$$ is less than $$$E(u)$$$, then there must be some $$$k_v>1$$$, i.e. some of $$$\overrightarrow{a_v}$$$ are extended. The lower bound of slope of $$$X'$$$ is that we suppose all extended $$$\overrightarrow{a_v}$$$ has the minimum possible slope, i.e. $$${\rm dis}(u,v)=1$$$. This gives us a lower bound by setting every $$$k_v'=k_\max=\max{k_v}$$$ and the slope of extended part is $$$1$$$. Formally, we define
and the slope of $$$X'$$$ is a lower bound of $$$X$$$.
Here we also denote the $$$x$$$-coordinate of $$$P$$$ by $$$p_x=\sum 1/E(v)$$$. Then, we calculate the slope of $$$X'$$$ directly, we have the slope of $$$X'$$$ being
Thus we have
$ Where $$$E(u)\le n^2$$$, therefore
$ Hence both $$$k_\min^{-1}-1$$$ and $$$1-k_\max^{-1}$$$ reduce by a factor of $$$1+n^{-2}$$$ for each iteration, and the convergence is linear if $$$n$$$ is considered a constant.
More than with the fact that I did not have a strict proof of the correctness of the tests, I was frustrated with the fact that some participants struggled to find the proof during the contest and thus did not attempt the problem. For example, both turmax and Jatana did all the math on the paper, but were not able to make the last step of not trying to find an analytical answer and apply some numerical method instead. What ultimately prevented them from submitting and ACing the problem might have been the belief that the jury had a strictly provable solution. This makes me feel a little bit awkward, as if I should feel like I've let the math fraternity down.
Sorry, folks. As many problemsetters say, there are basically two ways to come up with a problem: think of an solution idea and develop it into a problem which is solvable with this idea (solution↦statement), or think of a nice problem statement and do your best to try and solve it (statement↦solution). This problem was created with a statement↦solution approach, so what written in the tutorial is basically the best approach I was able to come up with (and the furthest point up to which I managed to strictly prove everything). It is possible that it is simply impossible to come up with a satisfying proof of convergence; it is even possible that there is some other procedure which converges faster (and, moreover, converges provably), but this method is unsuitable for a contest, because it will take all five hours of the contest, or even more, to come up with a quick method, to prove it, and to implement it. This is the problem, and I am sorry that optimally (for the contest) solving it requires both being a mathematician and, at the right moment, ceasing to be one.
Still I believe the problem is quite nice, and this is my highest quality and most difficult problem that I have offered to competitions of such a high level. I am so glad that a lot of talented programmers tried it!
Not sure about about others but I don't conaider a problem without a provable solution a "CP problem".
As far as I know, all the major CP platforms follows this, and expects authors to have a proven solution to every single problem before any contest.
Given that this problem was a deciding factor of whether your team qualifies to WF or not, I would be extremely pissed at the judges if I were an official participants and failed to qualify while trying this problem.
If NERC is willing to accept such problem, will it also accept problems like ML-based ones in the future?
This appears to be untrue of Codeforces; not sure about other platforms. CF Round 889 D1E was used without a provably correct solution.
I stand corrected. But I would argue cf participants do believe such rule exists without being written, which is what prompted dario to post such comment in the first place.
I believe this approach (slightly different iteration as the model solution) gives upper bounds on the correct answer and does converge, though I'm not sure about the convergence rate.
Initialize $$$x_l$$$ to be an upper bound on the answer starting at each node l. From the police officer's point of view, we can update each $$$x_l$$$ to the optimal answer given the values of other $$$x_j$$$: the fugitive should pick the minimum threshold $$$A$$$ where $$$q_j$$$ can be set so $$$d_{l,j} + (1-q_j)x_j \le A$$$ for all j. The computed value of $$$x_l$$$ is the same as the editorial's formula when all $$$q_j$$$ are positive, however this may not necessarily be the case with current values of $$$x_i$$$. Since each $$$x_l$$$ is decreasing, they must converge and in the limit must satisfy the same equations.
EDIT: Now that I think about it, the matching approach for lower bounds should also work. If you set $$$x_i$$$ as the currently proven lower bound on the answer, the fugitive should pick $$$q_j$$$ to maximize $$$\min(d_{l, j} + (1-q_j)x_j)$$$. This must also converge as it's increasing, and the equations satisfied are the same (all true $$$q_j$$$ are nonzero as proved in the editorial).
How many iterations did this approach require to get Accepted?
add c++20 please
C++20 is allowed, isn't it?
No, it isn't.
Can you provide a screenshot? Maybe I can only use C++20 because I am a manager of this contest.
I meant at the onsite event )
Do I look like a person with a time machine?
obviously, I meant in future rounds
Can somebody explain the solutions to A and K please?
Have you read the tutorial? If you have and still have questions, ask again please.
I have, but I still don't understand it.
Solution of K : First change even element to 0, and odd element to 1 When arr[i]=0, if this element adds in a subsequence, then previous two elements should be either (even,even) or (odd,odd) = (00) or (11) If arr[i]=1, the previous elements are (01) or (10) Also we maintain all such valid subsequences ending with 10 or 01 or 00 or 11 If arr[i]=0, this element can append in a subsequence ending with 1-> Just 0 -> result will be one extra 00 2-> Just 1 -> result will be one extra 10 3-> With 00 -> result will be one extra 00 4-> with 11 -> result will be one extra 10
If arr[i]=1, this element can append in a subsequence ending with: 1-> Just 0 -> result will be one extra 01 2-> Just 1 -> result will be one extra 11 3-> With 10 -> result will be one extra 01 4-> with 01 -> result will be one extra 11
great explanation thanks
AITU: jaujurek 3 bala (dolbaeb, dimachine, nkamzabek)
Thank you very much!
Auto comment: topic has been updated by orz (previous revision, new revision, compare).
Auto comment: topic has been updated by orz (previous revision, new revision, compare).
for problem k, can anyone explain how answer of fourth test case is 386??
Is there a solution that requires less mathematics for Problem J?
in question d why:-
It can be shown, that this particular kinds of divisibility tests can be checked by looking at the remainder of b k modulo n: • Kind 1 — b^k ≡ 0 (mod n). • Kind 2 — b^k ≡ 1 (mod n). • Kind 3 — b^k ≡ −1 (mod n).
I can't find the data files for NERC 2023. Does NERC no longer provide data downloads?