NercNews's blog

NEF & ROHSTPC
By NercNews, 5 years ago, translation, In English

Hello friends!

text

ICPCLive broadcast

Standings

Problems

This weekend we'll hold two large-scale final stages of important Championships in the region: ICPC Northern Eurasia Finals 2019 and Russia Open High School Team Programming Contest.

Competitions are traditionally held at several places: in St. Petersburg, Barnaul, Almaty, Tbilisi and Kremenchuk. School teams will fight for the "Champions of Russia" Cup. Student teams will meet in a serious intellectual fight for places to the ICPC 2020 World Finals, which will be held on June 25 in Moscow. This is going to be the third final organized in our region.

Of course, join ICPCLive broadcasts for live-streaming from both events. Live streams are expected from the opening of the championship, both contests, and closing ceremonies.

UPD: Congratulations to teams of ICPC 2020 finalists!

  • SPb SU: 25 (Belichenko, Bykov, Petrov)
  • Nizhny Novgorod SU: Almost Retired (Daniliuk, Kalinin, Ryabchikova)
  • MIPT: Godnotent (Belykh, Golovanov, Sergunin)
  • SPb ITMO: 1 Standard deviation (Budin, Kirillov, Sayutin)
  • Innopolis: 1 (Gaivoronskiy, Khakimiyon, Yalalov)
  • HSE: Logarifmya4ka (Anoprenko, Romanov, Safonov)
  • Belarusian SU: #1 (Dubovik, Karabeinikau, Kernazhytski)
  • Latvia: 2 (Civkulis, Zajakins, Zajakins)
  • Moscow SU: NoNames (Chunaev, Kalendarov, Koshelev)
  • SPb HSE: Last Hope (Bogomolov, Labutin, Podguzov)
  • Saratov SU: 1 (Meshcheryakov, Petrov, Piklyaev)
  • Belarusian NTU: #1: Great team (Sheftelevich, Vasileuski, Zdanovich)
  • Kazan FU: 2 (Ilikayev, Kapralov, Yagafarov)
  • Yerevan SU: One Last Dance (Galstyan, Muradyan, Mikaelyan)
  • International IT University: 2 (Kuanyshbay, Niyazbekov, Khlinovskiy)
  • Belarusian SUIR: #2 (Shavel, Udovin, Vishneuski)

ROHSTPC

269 teams were invited to participate in the final stage of the competition. 128 of them will meet in Saint Petersburg in the historical park "Russia — is my history". 49 teams will compete in Barnaul, 56 teams — in Almaty and 18 teams will take part in the competition in Tbilisi and Kremenchuk.

The main round of the championship will begin this Saturday (30 November) at 10:00. As the tour starts, we'll add links for you to monitor results.

Some teams that have high chances of becoming Cup winners are listed in the table below:

Team City Participant 1 Participant 2 Participant 3 Rating
Power of Three St.Petersburg Ефремов Андрей
receed		 Гайнуллин Ильдар
300iq		 Одинцов Андрей
forestryks		 8110
Mex Foundation Moscow Лифарь Егор
Egor.Lifar		 Савкин Семён
cookiedoth		 Шеховцов Александр
Jatana		 7657
Graneli Tbilisi Birkadze Nika
saba2000		 Toloraia Teimuraz
Temotoloraia		 Basadzishvili Archil
achi_basadzishvili		 7271
а) Moscow Ушаков Фёдор
----------		 Федосеев Тимофей
fedoseev.timofey		 Пискалов Дмитрий
TheWayISteppedOutTheCar		 7189
Ого! Кажетсья это $#@! Moscow Логинов Игорь
IgorI		 Шуклин Максим
xoxo		 Садовничий Антон
sadovan		 7092
Преимущественно овощи Kazan Миннахметов Булат
Minnakhmetov		 Харисов Булат
Nutella3000		 Исмагилов Азат
ismagilov.code		 6912

More teams with their total ratings you can see in the post. Thank you very much, ismagilov.code!

Northern Eurasia Finals

Student competitions will start this Sunday, December 1 at 9:30(Moscow time) at four sites: the historical Park in St. Petersburg, the Altai state technical University in Barnaul, the Georgian University of Business and Technology in Tbilisi and the Kazakh-British Technical University in Almaty.

Links to the results table, as well as the tasks of the contest will be provided soon after the start of the main round of the competition.

If you don't plan to participate in the semifinals, you can try your hand at the challenges of the Northern Eurasia finals in the mirror.

We're going to follow the teams and tell you about the news! Note that the results of this contest dictates which teams will be selected to represent the North Eurasia Region on World Finals ICPC 2020.

Some teams with their total ratings, which we're going to follow especially closely listed in a table below:

Team Participant 1 Participant 2 Participant 3 Rating
SPb ITMO: 1 Standard deviation Николай Будин
budalnik		 Дмитрий Саютин
cdkrot		 Арсений Кириллов
craborac		 8122
MIPT: Godnotent Александр Голованов
Golovanov399		 Евгений Белых
WHITE2302		 Андрей Сергунин
AndreySergunin		 8032
Moscow IPT: Fennecs Дмитрий Григорьев
gop2024		 Николай Третьяков
ShadowLight		 Денис Шпаковский
Denisson		 7938
NN SU: Almost Retired Алексей Данилюк
Um_nik		 Николай Калинин
KAN		 Валерия Рябчикова
Ekler		 7759
"Belarusian SU: Belarusian SU #1" Егор Дубовик
244mhq		 Александр Керножицкий
gepardo		 Федор Коробейников
Mediocrity		 7607
HSE: Logarifmya4ka Владимир Романов
voidmax		 Михаил Анопренко
manoprenko		 Иван Сафонов
isaf27		 7562
SPb SU: Havka — ne papstvo Егор Горбачев
peltorator		 Михаил Иванов
orz		 Савелий Григорьев
sava-cska		 7438
SPb SU 25 Дмитрий Беличенко
Dmitriy.Belichenko		 Никита Быков
anta.baka		 Семен Петров
Semenar		 7369
SPb SU: LOUD Enough Никита Гаевой
nikgaevoy		 Иван Бочков
tranquility		 Владислав Макаров
Kaban-5		 7075

Share with us your news, impressions, and photos with hashtags #NEF and #ВКОШП.

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

Comments Comments (39)
| Write comment?
»
5 years ago, # |
  Vote: I like it -59 Vote: I do not like it

People who don't understand Russian:

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

So long, not even in English and on the main page.

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

Is it only me or NEF = New English File?

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

Wow, didn't expect Um_nik and KAN are still eligible for ICPC!

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

    That's why they're "almost retired". It's the last year when then they can take part in ICPC I guess.

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

      :( It's also my last year.

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

      That's true for me, but KAN would be eligible for one more year if he would stay in university next year (at least that's how I understood him).

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

        Aren't you certain finalists in 2019-2020? If yes, KAN will run out of his attempts to participate in ICPC, so he will retire inevitably.

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

VKOShP Standing, ICPCLive. Somehow top 3 teams are badly stuck in first 2 hours...

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

300iq IS THE GREATEST

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

The high-school contest is available in Gym: 2019-2020 Russia Team Open, High School Programming Contest (VKOSHP 19)

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

How many people will advance to the WF in this ICPC contest?

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

How to solve G,H? Is there editorial?

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

    Solutions

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

      The optimal strategy is to never random after buying any relic for its price.

      Proof?

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

        Reduce the cost of each relic by $$$x/2$$$, and add the total cost by $$$n*x/2$$$ in the end. Also change the random price to $$$x/2$$$ and no refund is given, this is the same problem and it becomes obvious that we should never random after buying.

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

          After reading your comment I realised that we don't need to subtract $$$x/2$$$ and the proof is actually straightforward: we compare $$$s/k$$$ and $$$x + (n - k)/k \cdot x/2$$$. Let's multiply everything by $$$k$$$. Now we have $$$s$$$ and $$$(n + k) \cdot x/2$$$. When we buy any element the first value decreases by some $$$c_i$$$ and the second value decreases by $$$x/2$$$ which is less than any $$$c_i$$$. So if the first value is smaller for some set, it will also be smaller for all its subsets and we can use induction.

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

    G: I wrote subset dp and noticed that if the average of remaining elements is smaller than the current cost of buying a random element then we buy everything with $$$c_i$$$, otherwise we buy a random element.

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

      How to write without precision error? I got WA12, so I thought the assumption is wrong (indeed it is when $$$c_i < x$$$) but it turns out long double wasn’t precise enough.

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

        For each subset of $$$k$$$ elements with sum $$$s$$$ you should add to answer $$$\min(s/k, x + (n - k)/k \cdot x/2) \cdot \binom{n}{k}^{-1}$$$. You calculate the number of subsets for each $$$k$$$ and $$$s$$$ with knapsack. This way you don't need any subtractions.

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

          Wow thanks. My formula needed to compute knapsack without one element (so I needed subtract).

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

      For G, I tried the following, but I can't see why it's wrong. If we're buying, we should buy the cheapest remaining element, because buying a random element costs the same irrespective of the actual costs of the elements.

      Therefore, sort the costs, and do a dp where $$$f(l, k)$$$ is the cost for the suffix starting at position $$$l$$$ if $$$k$$$ elements from the suffix (chosen uniformly at random) were already removed.

      We can either roll and go to $$$(k, l +1)$$$ for cost of choosing randomly or "try" to buy element $$$l$$$: if it was removed already then we go to $$$(l+1, k-1)$$$ for free, otherwise we pay $$$c_l$$$ and go to $$$(l+1, k)$$$.

      Submission: 66292244

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

        For the same dp state it can be optimal to either buy the cheapest or random element depending on which random elements you already bought.

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

          Ah, I see. Whether we should buy $$$l$$$ can depend on whether we have $$$l + 1$$$ already. Thanks!

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

      I am curious to know how you had this observation. Did you stress-test on random tests ? Also when you do decide that you should write a brute-force solution and look for patterns ?

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

      Anyone has some proof for this ? The editorialists just expect us to come up with it somehow. Although it intuitively makes sense a proof would be nice.

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

how to solve problem K (key Storage) ?

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

    Compute the fingerprint. The answer is the number of permutations having $$$f_i\leq i \land f_n\neq0$$$. This can be computed with DP or by simple combinatorial logic (Multiply by the number of positions — number of used positions) (Divide by the number of duplicate permutations) don't forget to subtract permutations having $$$f_n=0$$$.

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

aid is mad

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

orz Havka — ne papstvo

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

Can somebody please explain in more detail the solution for A, please.

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

Would you mind updating the ghost standings in the codeforces mirror to the unfrozen onsite standings? Thank you! : )

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

How to implement the checker of problem H?

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

Why does my problem D get "Denial of judgement"?

Test: #26, time: 0 ms., memory: 0 KB, exit code: 0, checker exit code: 0, verdict: CRASHED
Checker Log
Unable to find classes\devopsGenerateServerCopieskt.class

Maybe something goes wrong with the checker?

→ Reply