Northern Eurasia Finals 2018
By NercNews, 6 years ago, translation, In English

Olá a todos!

text

Current Standings

The first winter weekend of the year would be tough for students who arrive to St. Petersburg, Barnaul, Almaty and Tbilisi. On the 1-2 of December ITMO University, Altai State Technical University, European University and Kazakh-British Technical University will host the final contest of Northern Eurasia. Participants are going to face a serious competition – they will fight for the right to represent their university on the finals of the ICPC 2019 in April in Portugal.

At the ITMO University stage we also expect 131 teams, including the Champions and Vice-Champions (but, worth mentioning, NEERC Champions) from last year ICPC'18.

Stay tuned for the latest news and monitors from the competition! These guys will go to the Porto to represent our Northern Eurasian region! Participants of our region have been taken the Final ICPC Cup for the last seven years. Will they continue their series of victories? Will see!

UPD: To the finals ICPC 2019 were qualified 15 teams:

  1. Moscow SU 3 (Makeev, Reznikov, Ipatov)
  2. Moscow IPT 6 (Sergunin, Belykh, Stepanov)
  3. International IT U 1 (Satylkhanov, Baimukanov, Kuanyshbay)
  4. SPb ITMO University 2 (Poduremennykh, Naumov, Korobkov)
  5. SPb br of NRU HSE 1 (Ermilov, Fedorov, Labutin)
  6. U of Latvia 2 (Klevickis, Pretkalnins, Pakalns)
  7. SPb SU 5 (Grebennikov, Fadeeva, Zavarin)
  8. Belarusian SU 1 (Lukyanov, Rak, Kim)
  9. NRU HS of Economics 1 (Sakhabiev, Nikolenko, Gribov)
  10. Kazakh-British TU 1 (Amanov, Aman, Zhussupov)
  11. Saratov SU 1 (Androsov, Glazov, Dalabaev)
  12. Belarusian SUIR 1 (Mosko, Razhkou, Shilyaev)
  13. Tbilisi IBSU 1 (Ksovreli, Narushvili, Svanidze)
  14. Northern FU (Dyachkov, Guriev, Asyutchenko)
  15. Ural FU 6 (Permyakov, Zuev, Mullabaev)

Follow the official competition hashtag #NEERC and join a live video, organized by ICPCLive and, in person, Aksenov239.

We are pleased to notice that this year at the NEERC will be special! We host some unique guests from the Committee of the ICPC organization – the Executive Director of the ICPC, Dr. Bill Poucher and Deputy Executive Director of the ICPC, Dr. Jeff Donahue. We will passionate to hear some inspiring words for our teams from Bill! And, of course, don’t miss the interviews with our special guests live!

If you want to visit the championship as a guest – please fill out the form.

If you do not participate in the semifinals, you can try to solve problems from 23rd NEERC challenge in the mirror. It will start in a few minutes after the main round on December 2nd. The tasks will be provided in English only. The mirror is an unrated contest.

We have compiled a table of participating teams with the total Codeforces rating >= 7000. Who is your favorite thou?

Team Participant 1 Participant 2 Participant 3 Rating
Moscow SU: Red Panda Ipatov (LHiC) Reznikov (vintage_Vlad_Makeev) Makeev (V--o_o--V) 7788
Moscow IPT: Shock Content Stepanov(irkstepanov) Sergunin(AndreySergunin) Belykh(WHITE2302) 7689
Moscow IPT: Good Game Golovanov(Golovanov399) Uvarov(-imc-) Machula(mHuman) 7671
SPb SU 1 Gorbachev(peltorator) Ivanov(orz) Safonov(isaf27) 7638
SPb ITMO University 1 Sayutin(cdkrot) Kirillov(craborac) Drozdova(demon1999) 7604
Moscow IPT: Racoons Grigoryev(gop2024) Tretyakov(ShadowLight) Shpakovskij(Denisson) 7440
SPb SU 2 Milshin(Morokei) Filippov(step_by_step) Fedorov(DaniilF) 7367
SPb ITMO University 2 Korobkov(romanasa) Poduremennykh(PoDuReM) Naumov(josdas) 7360
Moscow SU: NoNames Kalendarov(Andreikkaa) Koshelev(SendThemToHell) Chunaev(ch_egor) 7243
NRU HSE: IOI is not ICM, said MS Nikolenko(qoo2p5) Gribov(grphil) Sakhabiev(super_azbuka) 7052
Saratov SU #2 Androsov(BledDest) Dalabaev(adedalic) Glazov(Roms) 7000

Вoa sorte! Siga-nos:

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

Comments Comments (86)
| Write comment?
»
6 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Why does vintage_Vlad_Makeev make his rating lower on purpose?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why doesn't SpyCheese join participate in this contest ?

→ Reply
»
6 years ago, # |
  Vote: I like it -40 Vote: I do not like it

hăăpp-ciu!

→ Reply
»
6 years ago, # |
  Vote: I like it -6 Vote: I do not like it

What is formula of counting team rating?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +147 Vote: I do not like it

    a + b + c

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -177 Vote: I do not like it

      i mean on mirror contest team ratings, you noob

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        click. Also this blog is about NEERC, so you should have clarified that you need codeforces team ratings.

        → Reply
»
6 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Is iT rAted?

→ Reply
»
6 years ago, # |
  Vote: I like it +50 Vote: I do not like it

I think this guy discriminate against Chinese.He should be banned.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    khar_khar You should give our Chinese a reason.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +68 Vote: I do not like it

    No, he only discriminates against chinies.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Excuse me.What's the difference between these?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +33 Vote: I do not like it

        The difference is knowing how to write.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh, My friend just have a talk with this guy. His English,Emm.. not really good. But this team's name, just tell us his racism.

          → Reply
»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

team rating 7788

Was this part of vintage_Vlad_Makeev's master plan?

→ Reply
»
6 years ago, # |
  Vote: I like it +33 Vote: I do not like it

I couldn't register as a team in this contest, though I am the founder of the team. What should I do?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How many problems in the contest?

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

The page crashes when you try to view friends' submissions.

UPD: Seems to be fixed.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

Thanks for giving us the opportunity to take participate in the mirror contest.

Really great problems.

We really enjoy this contest.

→ Reply
»
6 years ago, # |
  Vote: I like it +23 Vote: I do not like it

how to solve c?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    On a tree this problem is solvable with centroid decomposition. We find centroid, print it and if it's not the chosen vertex, we go in one of its subtrees.

    For cactus, let's build tree of vertices and cycles: for each cycle, delete all it's edges, create a new vertex and connect it with all vertices in the cycle. On this tree, let's find a weighted centroid: all real vertices have weight 1 and all added vertices have weight 0. If this centroid is a real vertex, then we guess it, and go to one of its subcactuses. If it's a cycle, then if we ask some vertex v on this cycle, we will know that the chosen vertex is either in subcactus of some vertex to the left of v, some vertex to the right of v or in subcactus of v itself. So each v splits graph in three parts. We know that subcactus of v is always not larger than n / 2 because we chose centroid. We need to choose such v so that other 2 parts are also not greater than n / 2. It turns out that it's always possible. Let's choose some v, if the part to the right of v is too big, then the part to the left and subcactus of v together are not greater than n / 2, so if we shift v to the right, then the part to the left of v is still small. If we do this, we will stop eventually. There is also a case when the cycle length is even, then parts to the left and to the right of v are intersecting, but the proof still works with some minor fixes.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +16 Vote: I do not like it

      Now that we have this proof, we can actually do a brute-force search: for each vertex in the current subtree, compute the worst-case number of vertices remaining in the tree after we ask the question. We can therefore come up with an "optimal" query in O(n2) time.

      In order to get accepted, I needed to do some minor optimizations (memoize the optimal queries for each subtree). This gives us an O(n3) solution which fits comfortably in TL.

      Edit: we just realized that the memoization brings the runtime to O(n2). :)

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +63 Vote: I do not like it

      You can always choose a vertex which has smallest sum of distances to (all vertices which could be answer right now). After that the set of vertices which could be the answer becomes at least two times smaller.

      Also this works for all graphs, not only for cactus.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        Can you give proof why the set becomes 2 times smaller(for general graphs) ?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +65 Vote: I do not like it

          Let's say we asked vertex v, Chloe responded with w and set didn't become 2 times smaller. Vertex u stay in the set iff dist(v, u) = dist(w, u) + 1.

          If this condition is true for more than half of candidates than we should choose vertex w instead of v because it has smaller sum of distances to set: (at least half of distances is smaller by one) + (less than half of distances is bigger by at most one). Contradiction.

          → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +49 Vote: I do not like it

        Also this works for all graphs, not only for cactus.

        Wow! That's magic! If it works for general graphs why haven't you posed a question like that instead of just for cacti? For cacti it is much more intuitive that we can do this, not surprising at all and easier to come up with, while for general graphs it is very surprising and more fun to solve.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +27 Vote: I do not like it

          Probably because problems on cactus is a "feature" of NEERC?

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +72 Vote: I do not like it

          There are several reasons for doing that:

          • Cactus problems is NEERC tradition
          • I think we would have much smaller number of AC. But it is still possible to guess the correct solution and submit it without trying to prove. And I think it is not good if some team doesn't get top place at NEERC only because it doesn't guess/believe a solution.
          • I like the idea that you shouldn't try to find a solution based on constraints. E.g. in this problem you could invent much harder solution with centroid decomposition like aid described above.
          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            There will be a day when the first argument will be thrown away, or at least won't be the first in the list. The other arguments make sense though.

            → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

What is reason for WA on test 10 in A?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    i had wa 10 because for some test, we answered
    2:3
    25:a b:25 c:25 d:25 15:e
    where a,b,c,d,e — some numbers (i can't remember now)

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why the codes are not seen after final standing.

→ Reply
»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

What kind of matrix do I need to compute determinant of in order to solve B :p?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +98 Vote: I do not like it
    Spoiler
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +97 Vote: I do not like it

      In Moldova we can say the same thing about sorting.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      How come every problem is well known in China? And yet Chinese teams always lose to Northern Eurasians in ICPC finals.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +106 Vote: I do not like it

        Most strong competitors in China are high school students, and they spend less time in the algorithm competition in the university.

        And I want to say the problemset this year is not original enough. Someone also sent the problem I with constraint n = 2000 to me eight months ago.

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How exactly should we use it? We thought about the reduction during the contest but couldn't come up with one.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it
        Spoiler
        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 5   Vote: I like it +18 Vote: I do not like it
        Spoiler

        UPD: my solution is almost equivalent to what jqdai0815 written above (though the reduction is of linear size). I was late by 3 minutes :)

        UPD2: one more observation applicable to both mine solution and the jqdai0815's above: as all edges in the graph have the costs of 0 and 1, we do not need the weighted maximum matching algorithm: simply find the maximum matching in the subgraph formed by zero cost edges (this graph is still non-bipartite, though).

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Any ideas on how to solve it if we had to match each vertex on left with some k ≥ 3 vertices on right?

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve K?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I used a segment tree, and for each node [left, right] (with respect to times of people queuing) i held some values so that i could calculate finish time of people in this interval. Those values are: Sol (the actual answer), First (time of the first guy that queues), Free (How much can i get pushed by something from my left so that my solution won't get affected by it), and Cnt (Number of people waiting). The Cnt value i think you can get rid of it, but i used it just to make sure i calculate the correct values. Of course other solutions exists, this is what i implemented.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Approach is same as for timus 2014

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Couldn't that timus problem be solved with a seg tree of size 365*24*60 ? . So is that the intended approach or is there some other thing?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        It could. Problem K as well might be solved with quite same segment tree of size 106.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Any other approaches? Lot of solutions only use a max segment tree.

    → Reply
»
6 years ago, # |
  Vote: I like it +23 Vote: I do not like it

How to solve I?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -31 Vote: I do not like it

    http://oeis.org/A111111

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      On onsite competition internet is not allowed, so we didn't use it either. So what I meant is: how to solve it without oeis or google?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My solution: dp[n][k] the number of permutations of integers from 1 to n in which the first interval starts at k. Group the interval at k into a single value then compressing values, the new permutation is interval-free or the first position an interval appears is not less than k (except case ).

        → Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve M？

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +16 Vote: I do not like it

    I placed strongly connected components on the same level, and made zone with "lifts" between layers, as edges between components. Possibility to climb up is useless, as it's simpler without it.

    How it looks
    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hints on how to solve F?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You can find answer with just two fractions.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Proof?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it -53 Vote: I do not like it

        the proof is the fact that a lot of teams got OK using just two fractions

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        Basically, we are trying to solve this problem.

        We have a_1/d_1 + a_2/d_2 + ... a_m/d_m = (n-1)/n where d_i is the i-th divisor of N.

        If we multiply everything by n, we see we have a linear diophantine equation.

        a_1*(N/d_1) + a_2*(N/d_2) + ... a_m*(N/d_m) = N-1

        As we know that all the values divide by N, in order for there to be a solution for N-1 on the right, the gcd of the values must be 1. As solving diophantine equations for multiple variables is too hard, we notice that if we choose a d_i = p^k, where p does not divide (N/p^k) (ie: d_i contains all of the factors of p in N), then N/d_i must be coprime with d_i. As such, we can just solve a 2 variable linear diophantine equation and get the solution.

        There is a little bit of a wrinkle that you need positive solutions, but that's not too hard.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let v is a divisor of n such that gcd(v, n/v) = 1 (if v does not exist, the answer is NO). Juse choose a1 = (n/v)^-1 * (n-1) mod v, b1 = v, a2 = (n-1-a2*(n/2))/v, b2 = n/v. You can see that a1<b1, a2<b2 and a1/b1 + a2/v2 = 1 — 1/n.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The first three teams with highest rating ranked also top 3 in the final standings!

So to me seems like a notorious coincidence

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How many teams from Northern Eurasia are going to the finals?

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve D?

→ Reply