Hello friends!

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 #ВКОШП.

People who don't understand Russian:People who don't understand Russian:^_^ ^_^

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

Now in English ;)

Is it only me or NEF = New English File?

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

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

:( It's also my last year.

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

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.

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

300iq IS THE GREATEST

I don't agree

The high-school contest is available in Gym: 2019-2020 Всероссийская командная олимпиада школьников по программированию (ВКОШП 19)

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

How to solve G,H? Is there editorial?

Solutions

Proof?

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.

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.

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.

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.

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.

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

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

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.

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

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 ?

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.

how to solve problem K (key Storage) ?

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

aid is mad

orz Havka — ne papstvo

orz Nayka — ne papsovo

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

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

Good contest