Квалификационный раунд Yandex Cup 2023

№	Пользователь	Рейтинг
1	tourist	3757
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

№	Пользователь	Вклад
1	maomao90	171
2	awoo	165
3	adamant	163
4	TheScrasse	159
5	maroonrk	155
6	nor	154
7	-is-this-fft-	152
8	Petr	147
9	orz	146
10	pajenegod	145

Всем привет!

Недавно мы публиковали новость про старт регистрации на квалификационный раунд в рамках отбора на Yandex Cup 2023.

Чемпионат состоит из шести направлений:

На этих выходных, 29 октября (ближайшее воскресенье) в 23:59 заканчиваются квалификационные раунды по каждому из направлений и у каждого из Вас есть хорошие шансы занять место в полуфинале! Полуфинал пройдёт уже в следующую субботу, 4 ноября, в 12:00 (GMT +3).

20 лучших полуфиналистов от каждого трека поедут на заключительный этап в Алматы, который пройдёт 1-2 декабря. Расходы на перелёты и проживание Яндекс берёт на себя!

Призовой фонд, который распределят между топ 5 участниками в каждом направлении!

1-е место — 500 000 рублей
2-е место — 250 000 рублей
3-е место — 200 000 рублей
4-е место — 150 000 рублей
5-е место — 100 000 рублей

А еще будут конечно футболки для топ-20 финалистов каждого трека. До встречи на Yandex Cup!

UPD. Стал доступен монитор квалицикации алгоритмического направления и участники могут попробовать свои силы в дорешке

with recursive name_tree as (select id, prev_id from pickup_point where id = id -- this is the starting point you want in your recursion union all select c.id, c.prev_id from pickup_point c join name_tree p on p.prev_id = c.id -- this is the recursion ) select id from name_tree

select id from pickup_point zzz where branded_since = :targetDate and not exists (select pickup_point_id from brand_data bd where bd.pickup_point_id in ( with recursive name_tree as ( select id, prev_id from pickup_point where id = zzz.id -- this is the starting point you want in your recursion union all select c.id, c.prev_id from pickup_point c join name_tree p on p.prev_id = c.id -- this is the recursion ) select id from name_tree) )

select id from pickup_point zzz where branded_since = :targetDate and not exists (select pickup_point_id from brand_data bd where bd.pickup_point_id in ( with recursive name_tree as ( select id, prev_id from pickup_point where id = zzz.id -- this is the starting point you want in your recursion union all select c.id, c.prev_id from pickup_point c join name_tree p on p.prev_id = c.id and c.id <> zzz.id -- this is the recursion ) select id from name_tree) )

Комментарии (19)

Написать комментарий?

orz

7 месяцев назад, # |

+18

Не удаётся войти в личный кабинет.

→ Ответить

Yandex

7 месяцев назад, # ^ |

+12

Действительно, в течение 9 минут личный кабинет был не доступен. В 00:43 работа сервиса была восстановлена.

Svyat

Что за бесполезная кнопка «завершить» в интерфейсе после окончания контеста?

Golovanov399

+26

> 20 лучших полуфиналистов от каждого трека поедут на заключительный этап.
> Будут футболки для топ-20 финалистов каждого трека.

То есть для всех финалистов?

CEKPET

← Rev. 3 →

-39

Общий призовой фонд $$$\color{red}{\text{Я}}\color{black}{\text{ндекс}}$$$ 6 000 000 ₽ или 63 694$.

dmkz

Откройте дорешивание задач, пожалуйста, по аналогии с прошлым годом, когда вы создали копию соревнования исключительно для дорешивания

Igorjan94

+19

Насколько я понимаю, задачи можно уже обсуждать, так как в личном кабинете уже вижу выставленный балл
Начну с организационных вопросов и глупых вопросов по сайту:

Почему кнопка "перейти" на раунд это не ссылка и её невозможно открыть в новой вкладке?
Почему в архиве нет всех контестов? Я хочу посмотреть архив и результаты полностью -- квалификация, финал для каждого трека. Я вижу только список победителей, где первый Гена (да ладно?). А некоторые треки вообще отсутствуют
Почему нет дорешки для всех контестов?
Почему нет положения для квалов бэкенд и алгоритм треков?
Почему я Я.Контесте нет истории контестов, в которых я участвовал?
Почему нет системы оценивания и собственно критерия отбора с квала на финал? Задача оценивается по IOI системе? По ICPC? Баллы за тест? Я хз каким образом за 8 из 14 тестов можно выставить 52 балла.

Теперь к задачам бэкенд трека:
А: Обычная хорошая задача, правда с трека алгоритм
Б: Обычная хорошая задача, правда с трека алгоритм
С: Расскажите пожалуйста, что эта задача делает в этом контесте? Каким образом здесь вообще бэкенд или алгоритм?
Д: Расскажите пожалуйста, что эта задача проверяет? То, что человек умеет гуглить? Только не говорите "знание sql", я последний раз руками запросы писал году в 2012, но задачу сдал на 100 баллов. Отдельно доставил вердикт Crash и отказ тестирования вместо TL на каком-то тесте
Е: Кто-нибудь читал вообще условие этой задачи? Нет, как задача она как раз отличная для этого контеста. Но вот формулировака условия и пример просто ужаснейшие. Часа два переписывался в кларах но так и не понял, что же от меня хотят. Сейчас открыл условие -- теперь гордо есть примечание "В случае, если существует несколько подходящих заявок для сделки, выбор происходит между заявками с наименьшей разницей между ценами покупки и продажи.", но когда я решал его не было. Как это возможно догадаться -- хз, в условии вообще ничего про это нет, а это собственно единственное, что требуется сделать в задаче. Я уж не говорю, что в задаче нет ограничений и догадайся сам

К счастью, к алгоритм треку никаких претензий по задачам нет
Пожалуйста, вычитывайте и отбирайте задачи и для бекенд трека! Мне он очень нравится, да и сама идея просто шикарная иметь не только обычный контест, но и контест для backend-frontend разработчиков! К сожалению, это единственный контест такого рода и очень не хочется, чтобы он скатился в ещё один алгоритм или контест где никто не участвует потому что задачи неинтересные/не вычитаны!

Papercut

Привет, а можно хинт по Д с бэкенд трека(если это действительно "умение гуглить", то поделитесь, пожалуйста, тем, что нагуглили :))?
0 идей во время контеста о том, как это вообще реализовывается средствами SQL

← Rev. 2 →

Конечно, легко. Я даже опишу как я решал задачу полностью. У меня это заняло чуть более получаса: первая посылка в 23:25:18, ок в 23:59:03. Но я совершенно не торопился и параллельно переписывался в кларах по задаче Е

Запихну под спойлер, а то много кода

Для начала смотрим условие и видим пример: select id from pickup_point where branded_since = :targetDate. Читаем его, понимаем что оно делает. Хорошо, давайте сначала решим "половину" задачи, когда нас не волнуют родители. Пример почти ок, только нам ещё надо проверить что для этого id не существует ничего в другой таблице. Окей, гуглим что-то типа "postgre select if not exists in another table", получаем готовое решение, которое набирает 52 балла:

select id from pickup_point where branded_since = :targetDate
  	and not exists (select * from brand_data bd where bd.pickup_point_id = id)

Теперь понимаем, что надо проверить, что не существует в brand_data не просто id, но и все его родители. Окей, давайте сначала перепишем чтобы мы проверяли что айдишки нет в списке, потом получим всех родителей. Хорошо, гуглим "postgre where not in list". Получаем что-то типа

select id from pickup_point where branded_since = :targetDate
  	and not exists (select * from brand_data bd where bd.pickup_point_id in (id))

Теперь надо получить всех родителей. Гуглим "sql get recursive parent id list", или что-то подобное:

Я нагуглил такое решение. Запускаю это (да, у меня есть поднятый постгре на сервере, но поднять докером локально дело 5 минут), получаю всех родителей по id. Мержим оба решения:

Получаем Crash. Окей, мы ведь забили на циклы и рекурсия циклится. Добавляем одну проверку:

Это решение набирает 100 баллов, хотя оно очевидным образом не работает на цикле с хвостом, например с ребрами 1->2->1, 3->1 при запросе 3. Но я хз как это решать и я не думаю что это легко решается sql и я сомневаюсь что и авторы умеют решать это легко

kartel

Как решать задачу F в треке алгоритмов?

Я видел похожую задачу только для одного запроса k(собственно, только его решать и умею). Но как Дейкстру можно заменить? Должна же быть некая закономерность.

_LeMur_

+10

Я не решил во время contest-а, но думаю что решается используя binary search на ответа (в double-ax), то есть например знаем что ответ у нас $$$answer$$$, надо найти количество $$$x / y$$$ меньше $$$answer$$$, это можно делать за $$$min(|X|, |Y|) * log(10^6) * 100$$$ (здесь $$$100$$$ это количество сколько мы делим наш отрезок, для binary search, наверно 60 тоже хватит)