NeercNews's blog

By NeercNews, 13 days 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
Шеховцов Александр
UnstoppableSolveMachine
7657
Graneli Tbilisi Birkadze Nika
saba2000
Toloraia Teimuraz
Temotoloraia
Basadzishvili Archil
achi_basadzishvili
7271
а) Moscow Ушаков Фёдор
osaaateiasavtnl.
Федосеев Тимофей
fedoseev.timofey
Пискалов Дмитрий
TheWayISteppedOutTheCar
7189
Ого! Кажетсья это $#@! Moscow Логинов Игорь
IgorI
Шуклин Максим
xoxo
Садовничий Антон
antony191
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 Николай Будин
Nebuchadnezzar
Дмитрий Саютин
_kun_
Арсений Кириллов
senek_K
8122
MIPT: Godnotent Александр Голованов
Golovanov399
Евгений Белых
WHITE2302
Андрей Сергунин
andreysergunin
8032
Moscow IPT: Fennecs Дмитрий Григорьев
DmitryGrigorev
Николай Третьяков
ShadowLight
Денис Шпаковский
Denisson
7938
NN SU: Almost Retired Алексей Данилюк
Um_nik
Николай Калинин
KAN
Валерия Рябчикова
Ekler
7759
"Belarusian SU: Belarusian SU #1" Егор Дубовик
kefaa2
Александр Керножицкий
gepardo
Федор Коробейников
GandalfTheGrey
7607
HSE: Logarifmya4ka Владимир Романов
voidmax
Михаил Анопренко
manoprenko
Иван Сафонов
isaf27
7562
SPb SU: Havka — ne papstvo Егор Горбачев
Isaf27_loves_me
Михаил Иванов
imp
Савелий Григорьев
sava-cska
7438
SPb SU 25 Дмитрий Беличенко
mitterr1999
Никита Быков
StillBlueSkyOverhead
Семен Петров
Semenar
7369
SPb SU: LOUD Enough Никита Гаевой
nikgaevoy
Иван Бочков
gnomina007
Владислав Макаров
Kaban-5
7075

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

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

»
12 days ago, # |
  Vote: I like it -59 Vote: I do not like it

People who don't understand Russian:

»
11 days ago, # |
  Vote: I like it +17 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it -81 Vote: I do not like it

Is it only me or NEF = New English File?

»
10 days 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!

  • »
    »
    10 days 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.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      :( It's also my last year.

    • »
      »
      »
      10 days 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).

      • »
        »
        »
        »
        10 days 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.

»
10 days 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...

»
10 days ago, # |
  Vote: I like it +29 Vote: I do not like it

300iq IS THE GREATEST

»
10 days ago, # |
  Vote: I like it +28 Vote: I do not like it
»
9 days ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
9 days ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve G,H? Is there editorial?

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

      • »
        »
        »
        »
        8 days 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.

        • »
          »
          »
          »
          »
          8 days 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.

  • »
    »
    9 days 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.

    • »
      »
      »
      9 days 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.

      • »
        »
        »
        »
        9 days 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.

        • »
          »
          »
          »
          »
          9 days 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).

    • »
      »
      »
      5 days 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

      • »
        »
        »
        »
        5 days 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.

        • »
          »
          »
          »
          »
          5 days 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!

    • »
      »
      »
      4 days 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 ?

»
9 days ago, # |
  Vote: I like it +5 Vote: I do not like it

how to solve problem K (key Storage) ?

  • »
    »
    9 days 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$$$.

»
9 days ago, # |
  Vote: I like it +41 Vote: I do not like it

aid is mad

»
9 days ago, # |
  Vote: I like it -51 Vote: I do not like it

orz Havka — ne papstvo

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 days 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! : )

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good contest