orz's blog

By orz, history, 7 months ago, In English

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:

Problem Author Developer
1912A - Accumulator Apex Aksenov239 Aksenov239
1912B - Blueprint for Seating VArtem niyaznigmatul
1912C - Cactus Transformation _LeMur_ _LeMur_
1912D - Divisibility Test elizarov elizarov
1912E - Evaluate It and Back Again VArtem VArtem
1912F - Fugitive Frenzy orz orz
1912G - Great City Saint Petersburg cdkrot cdkrot
1912H - Hypercatapult Commute pashka pashka
1912I - Innovative Washing Machine isaf27 isaf27
1912J - Joy of Pokémon Observation goldvitaly goldvitaly
1912K - Kim's Quest Elena Kryuchkova izban
1912L - LOL Lovers orz orz

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!

  • Vote: I like it
  • +193
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem A why this test case , print 11

1 1
4 1 2 -5 12

When I withdraw -5, the accumulator will become negative, right?

»
7 months ago, # |
  Vote: I like it +13 Vote: I do not like it

pretty unfortunate to see an LGM (Ormlis) not qualifying for World Finals...

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

    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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +41 Vote: I do not like it

      true i was there as well and he just couldn't handle the pressure. too bad gl next time tho

»
7 months ago, # |
  Vote: I like it +46 Vote: I do not like it

Instead, one can take some initial approximation, e.g. $$$x_u = 1$$$ or $$$x_u = (n − 1)^2$$$, and iteratively apply the formula above to get a more and more precise answer. This process seems to converge relatively fast, although jury does not have a proof of that

So jury's solution to problem F is basically a heuristic? How did you guarantee that all the tests are correct?

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it -33 Vote: I do not like it

    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).

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 21   Vote: I like it +55 Vote: I do not like it

      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:

      1. $$${\rm dis}(u,v)\ge 1$$$

      2. $$$E(u) \ge \max {\rm dis}(u,v)$$$, because thief can always choose to go to the furthest leaf

      3. $$$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

      $$$x'_u=\frac{\sum {\rm dis}(u,v)/x_v+m-1}{\sum 1/x_v}$$$

      $ 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

      $$$X=B+\sum \left(1/x_v,{\rm dis}(u,v)/x_v\right)$$$

      $ We rewrite $$$x_v$$$ in the form of $$$E(v)/k_v$$$, then $$$X$$$ can be represented as

      $$$X=B+\sum k_v\cdot \left(1/E(v),{\rm dis}(u,v)/E(v)\right)$$$

      $ 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

      $$$X=B + \sum k_v\cdot \overrightarrow{a_v}$$$

      $ 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

      $$$P=B+\sum \overrightarrow{a_v}$$$

      $ 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

      $$$ X'=B+\sum k_\min\cdot\overrightarrow{a_v} = B+ k_\min\cdot\sum \overrightarrow{a_v}$$$

      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:

      1. $$$O=(0,0)$$$

      2. $$$B=(0,m-1)$$$

      3. $$$P=B+\sum \overrightarrow{a_v}$$$, the slope of which is $$$E(u)$$$

      4. $$$X'=B+k_\min \sum \overrightarrow{a_v}$$$, the slope of which is the upper bound

      5. $$$Y$$$, the intersection of line $$$OX'$$$ and line $$$x=p_x$$$

      6. $$$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

      $$$PQ=m-1+\sum {\rm dis}(u,v)/E(u)\ge m-1+\sum 1/n^2=(m-1)\left(1+n^{-2}\right)$$$

      Therefore, we have

      $$$x'_u=\frac{YQ}{OQ}=\frac{PQ+(m-1)\cdot (k_\min^{-1}-1)}{PQ/E(u)}\le \frac{1+n^{-2}+k_\min^{-1}-1}{1+n^{-2}} E(u)$$$

      Thus we have

      $$${k'}_u^{-1}-1=\frac{x'_u}{E(u)}-1\le \frac{1}{1+n^{-2}}(k_\min^{-1}-1) $$$

      $ 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

      $$$ X'=P+p\cdot (k_\max-1,k_\max-1)$$$

      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

      $$$x'_u=\frac{p_x\cdot E(u)+p_x\cdot (k_\max-1)}{p_x+p_x\cdot (k_\max-1)}=\frac{E(u)+k_\max-1}{k_\max}$$$

      Thus we have

      $$$1-{k'_u}^{-1}=1-\frac{x'_u}{E(u)}=1-k_\max^{-1}-E^{-1}(u)+k_\max^{-1}\cdot E^{-1}(u) = (1-k_\max^{-1})\cdot (1-E^{-1}(u))$$$

      $ Where $$$E(u)\le n^2$$$, therefore

      $$$1-{k'_u}^{-1}\le \left(1-n^{-2}\right)(1-k_\max^{-1})$$$

      $ 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.

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it +30 Vote: I do not like it

    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!

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +90 Vote: I do not like 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?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +41 Vote: I do not like it

        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.

        This appears to be untrue of Codeforces; not sure about other platforms. CF Round 889 D1E was used without a provably correct solution.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          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.

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +30 Vote: I do not like it

    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).

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How many iterations did this approach require to get Accepted?

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

add c++20 please

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    C++20 is allowed, isn't it?

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, it isn't.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you provide a screenshot? Maybe I can only use C++20 because I am a manager of this contest.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain the solutions to A and K please?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Have you read the tutorial? If you have and still have questions, ask again please.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like 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


    void solve(){ int n; cin>>n; vi arr(n); fori0n{ cin>>arr[i]; arr[i]%=2; } ll z=0; ll o=0; ll zo=0; ll oz=0; ll oo=0; ll zz=0; ll ans=0; fori0n{ if(arr[i]==0){ ans+=oo; ans=ans%mod; ans+=zz; ans=ans%mod; int t1=oo; int t2=oz; int t3=zo; int t4=zz; zz+=zz+z; oz+=o+oo; zz=zz%mod; oz=oz%mod; z++; } else{ ans+=zo; ans=ans%mod; ans+=oz; ans=ans%mod; int t1=oo; int t2=oz; int t3=zo; int t4=zz; zo+=oz+z; oo+=t3+o; zo=zo%mod; oo=oo%mod; o++; } } cout<<ans<<endl; }
»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

AITU: jaujurek 3 bala (dolbaeb, dimachine, nkamzabek)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by orz (previous revision, new revision, compare).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by orz (previous revision, new revision, compare).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem k, can anyone explain how answer of fourth test case is 386??

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a solution that requires less mathematics for Problem J?