Всем привет!
Эти выходные ознаменованы двумя масштабными финальными этапами важных командных чемпионатов региона: ICPC 2019 Финалом Северной Евразии и Всероссийской командной олимпиадой школьников по программированию.
Состязания традиционно проходят на нескольких площадках: в Санкт-Петербурге, Барнауле, Алматы, Тбилиси и Кременчуге. Школьным командам предстоит борьба за кубок чемпионов России, а студенческие команды встретятся в нешуточной борьбе за путевки в финал ICPC 2020, который пройдет 25 июня в Москве и станет третьим финалом, прошедшим в нашем регионе.
Конечно же, присоединяйтесь к трансляциям ICPCLive с обоих мероприятий.
UPD: Поздравляем команды финалистов ICPC 2020!
- 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)
ВКОШП
Принять участие в финальном этапе ВКОШП было приглашено 269 команд. 128 из них встретятся на площадке исторического парка "Россия — моя история" в Санкт-Петербурге, 49 примут участие в Барнауле, 56 команд — Алматы и по 18 команд будут принимать участие в Тбилиси и Кременчуге.
Основной тур чемпионата начнется в субботу 30 ноября в 10:00.
Таблица результатов. Условия задач.
Вот некоторые команды, у которых высоки шансы стать обладателями кубка:
| Команда | Город | Участник 1 | Участник 2 | Участник 3 | Рейтинг |
| Power of Three | СПб | Ефремов Андрей receed | Гайнуллин Ильдар 300iq | Одинцов Андрей forestryks | 8110 |
| Mex Foundation | Москва | Лифарь Егор Egor.Lifar | Савкин Семён cookiedoth | Шеховцов Александр Jatana | 7657 |
| Graneli | Тбилиси | Birkadze Nika saba2000 | Toloraia Teimuraz Temotoloraia | Basadzishvili Archil achi_basadzishvili | 7271 |
| а) | Москва | Ушаков Фёдор ---------- | Федосеев Тимофей fedoseev.timofey | Пискалов Дмитрий TheWayISteppedOutTheCar | 7189 |
| Ого! Кажетсья это $#@! | Москва | Логинов Игорь IgorI | Шуклин Максим xoxo | Садовничий Антон sadovan | 7092 |
| Преимущественно овощи | Казань | Миннахметов Булат Minnakhmetov | Харисов Булат Nutella3000 | Исмагилов Азат ismagilov.code | 6912 |
Больше команд с суммарным рейтингом вы можете посмотреть в посте. Большое спасибо, ismagilov.code!
Northern Eurasia Finals
Студенческие соревнования стартуют в воскресенье 1 декабря в 9.30 одновременно на четырех площадках: историческом парке в Санкт-Петербурге, Алтайском государственном техническом университете в Барнауле, Грузинском университете бизнеса и технологий в Тбилиси и в Казахстанско-Британском техническом университете в Алматы.
Ссылки на таблицу результатов, а также задачи контеста разместим после старта основного тура.
Если вы не участвуете в полуфинале, вы можете попробовать свои силы на задачах финала Северной Евразии в зеркале.
Постараемся внимательно следить за командами и оперативно рассказывать о новостях, ведь именно по результатам этого контеста будут отобраны команды, которым в июне предстоит представлять наш Северо Евразийский регион на международной площадке ICPC 2020 и, возможно, продолжить серию побед.
Здесь представлены команды с их суммарным рейтингом, за которыми будем следить особенно внимательно:
| Команда | Участник 1 | Участник 2 | Участник 3 | Рейтинг |
| 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 |
Делитесь с нами вашими новостями, впечатлениями и фотографиями в соцсетях с хештегами #nef и #вкошп.
А можно на NEF и ICPC тоже убрать правило двух попыток и возрастные ограничения? И давайте будут команды из одного человека. Я считаю, так соревнование станет ещё более захватывающим.
Однозначно. И со своими ноутами! А то что это за беспредел
А можно включить в список команд на NEF SPb SU: 25? Мне немного кажется, что суммарный рейтинг Dmitriy.Belichenko, anta.baka и Semenar побольше 7000.
Важнее, что он больше 7075.
Спасибо, добавили
SPbSU 25 orz
Представляете, у меня есть знакомая команда в которой чел слил 100 пунктов на последнем раунде и у них сейчас 6993 в сумме.
Morokei, step_by_step и DaniilF тоже должны быть в таблице, у них 7267 в сумме.
Но на финал пройдут Agreb, andrey.zavarin и kek1234 с рейтингом 6508.
А где в этом комментарии присутствует Андрей Сергеевич Станкевич?
У Андрея Сергеевича andrewzta Станкевича суммарный рейтинг равен 2617, что гораздо меньше необходимых 7000.
Это не список тех, у кого 7000, это список тех, "за которыми будем следить особенно внимательно" :)
А если серьезно, это не список тех, у кого высокий рейтинг, в списке некоторые команды, которые проявляли себя хорошо на сборах.
Тогда странно, что в списке нет команды из Латвии:
Alex_2oo8 Sanja how_to_become_purple
MIPT Fennecs gop2024 ShadowLight Denisson 7900+
Почему есть зеркало nef, но нет зеркала вкошпа?
Желаю удачи!
Поздравляю всех
аа
Вам не кажется что личного пространства оставили чуть больше, чем нисколько? Лично мне не нравится, когда слева, справа и напротив сидят по три идиота
С идиотами как-то резко, но расстояние между рядами выглядит небольшим
Если один из этих идиотов буду я, то я тебе питание компа вырублю
Ты даже до Петербурга доехать не можешь, алло
А ты смышленный
А то
забавно, но что-то похожее вышло у наших соседей напротив. Кабель питания к ноутам подключался сзади, у них он выпал и они не заметили. Мы подсказали, конечно, а то было бы ребятам не очень приятно.
В итоге вышло норм, все равно общий шум как в баре — слышишь только своих соседей. Хотя, ребята говорят, что справа была шумная команда... хз, у меня были соседи слева и они были ок.)
А те, кто напротив, вообще уже незаметны.
Лично я слышал каждое слово оппонентов напротив
это жесть, конечно. Видимо, я слишком уходил "в себя". Может, напротив тебя сидели Loud Enough?))
Если честно, на четверти нас рассаживают по аудиториям, команд по шесть. И это не особо спасает. В помещении тише, отвлекать может буквально все.
Ну и ощущение, конечно, такое себе, типа просто олимпиадку пишешь.
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 ;)
А как правильно в итоге: NEERC, NERC или NEF?
nerc.itmo.ru
А мониторы забыли купить?
Ага. И стулья. И компьютеры. Зато две клавиатуры, интересно, я один не видел объявления заранее, что на NEERC будет две клавиатуры? Доколе, граждане?
Я вообще поражен, наверное, никто просто не читает текст коммента, когда у него 10 поставленных по заказу минусов?
Организаторы просто оставили всех участников с ноутами. Что дальше? В следующем году на планшетах будем программировать? Серьезно, вам удобнее смотреть в 15-дюймовый экран ноута вместо 25-дюймового монитора? Давайте, отписывайте все сюда, кому удобнее смотреть в ноут, а не в монитор, посмотрим на вас.
Организаторы старались сделать все красиво, пафосно, арендовали какой-то крутой зал, а на банальном удобстве участников сэкономили. Это позор.
В прошлом году моей команде на вкошпе достался ужасно старый квадратный монитор и сам компьютер ужасно лагал. Я бы, очевидно, выбрал ноутбук вместо этого.
Да, я гораздо больше привык к ноуту, чем к монитору. Нет, это не я попросил так сделать.
Позор -- это сначала токсично высказывать свое никому не нужное мнение, а потом удивляться, что тебя заминусили и говорить, что эти минусы проплачены. Все хорошо с тобой? Да, меня всем устраивает ноутбук. Я понимаю, что оргам было и так тяжело их достать. Плюс, я в последние несколько лет за компьютером сидел только на олимпиадах, наверно
Потом еще уберите мышки и клавиатуры, замените все ноуты на маки, оставьте на них только Vim. А что? меня же все устраивает.
Вы принимаете абсолютно абсурдные решения, и лучше пресечь это сразу, подняв эту тему здесь и сейчас.
Наконец, наличие монитора не обязывает им пользоваться. Если правда хочется смотреть в маленький экран — открываешь ноут и смотришь.
Я решения не принимаю, я участник. Надеюсь, вам не нужно объяснять, чем отличается отсутствие чего-то, от наличия, но не удовлетворяющего вас размера. В этом плане, отсутствие внешней клавиатуры было бы, в целом, тоже удовлетворительно. А отсутствие мыши -- все же не очень. А если бы вам поставили 20-дюймовый монитор, вас бы это устроило? Или вы бы стали требовать 30-дюймовый?
Is it only me or NEF = New English File?
Что-то батя Кек Сун не наблюдает в этом списке самую топовую команду этого сезона из Ярославского ГУ. Все какие-то ноунеймы.
Чудесная идея ставить контест на 9:30 утра.
По ночам надо спать, а не аниме смотреть :)
да-да, аниме
не ну там тоже аниме есть
Я даже не знаю, наверно вы лучше меня знаете "чем я занимаюсь по ночам"
Зато мы знаем, чем ты не занимаешься по ночам :)
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
Что означает название команды havka ne papstvo?
Знал бы кто.
Ну, наименьшее, что я могу уверенно сказать — что это название придумали peltorator и isaf27 в качестве противопоставления названию "Havka — papstvo", которое носят, если не ошибаюсь, те и только те составы, в которые входит PavelKunyavskiy.
Всё-таки хавка — папство или не папство?
Не папство, конечно!
фу на вас
Скорее Egor но он уехал в Мюнхен, а мы с продолжили писать под тем же названием
https://www.youtube.com/watch?v=hxHKGV4LY34
Финал ВКОШП теперь доступен в Тренировках: 2019-2020 Всероссийская командная олимпиада школьников по программированию (ВКОШП 19)
The high-school contest is available in Gym: 2019-2020 Russia Team Open, High School Programming Contest (VKOSHP 19)
How many people will advance to the WF in this ICPC contest?
А можно будет следить за ходом соревнования? Ссылки не вижу.
Standings
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! : )
В прошлом году рядом с архивом жюри выкладывали и посылки всех команд (архив Runs с официальной страницы http://neerc.ifmo.ru/archive/2018.html). Будет ли выложен такой же архив в этом году?
How to implement the checker of problem H?
Why does my problem D get "Denial of judgement"?
Maybe something goes wrong with the checker?