Русский
Русский
English
Статистика
Реклама

Конкурсы разработчиков

Как заставить код выполняться за одинаковое время? Способы от Яндекс.Контеста

27.08.2020 10:09:54 | Автор: admin
Недавно мы объявили на Хабре, что начинаем принимать заявки на Яндекс.Алгоритм и другие треки чемпионата по программированию Yandex Cup. Уже много лет онлайн-соревнования Яндекса и других компаний проходят на платформе Контест. Меня зовут Павел Тыквин, я один из разработчиков Контеста. Основная задача нашей платформы получить от участника чемпионата исходный код решения, скомпилировать и запустить этот код, прогнать тесты и вернуть результат. Звучит не очень сложно. Давайте попробуем.

#include <iostream>using namespace std;int main(){int n = 500000000;int *a = new int[n + 1];for (int i = 0; i <= n; i++)a[i] = i;for (int i = 2; i * i <= n; i++){if (a[i]) {for (int j = i*i; j <= n; j += i) {a[j] = 0;}}}delete[] a;return 0;}

Это простенькое приложение специально для экспериментов, оно ищет простые числа методом решета Эратосфена. Запустим решение 20 раз и посчитаем user time каждого исполнения.

Описание тестового стенда
i7-8750H @ 2,20 ГГц
32 ГБ RAM
OС:
Ubuntu 18.04.4
5.3.0-53-generic

Разброс времени исполнения до оптимизаций:


Разница между самым быстрым и самым медленным исполнением 2230 мс.

Для олимпиадного программирования это неприемлемо. Время выполнения кода участника один из критериев успешности его решения и одно из условий соревнования, от этого зависит распределение призовых мест. Поэтому существует важное требование к подобным системам одинаковое время проверки одного и того же кода. Далее будем называть это консистентностью выполнения кода.

Попробуем выравнять время исполнения.

Изоляция ядер


Начнем с очевидного. Процессы конкурируют за ядра, и нужно каким-то образом изолировать ядро под исполнение решения. Кроме того, с включенным Hyper Threading операционная система определяет одно физическое ядро процессора как два отдельных логических ядра. Для честной изоляции ядра нам нужно отключить Hyper Threading. Это можно сделать в настройках BIOS.

Ядро Linux из коробки поддерживает флаг запуска для изоляции ядер isolcpus. Добавим этот флаг в GRUB_CMDLINE_LINUX_DEFAULT в настройках grub: /etc/default/grub. Например: GRUB_CMDLINE_LINUX_DEFAULT="... isolcpus=0,1"

Выполним update-grub и перезапустим систему.

Все выглядит как ожидалось первые два ядра не используются системой:


Запустимся на изолированном ядре. Конфигурация CPU Affinity позволяет привязать процесс к конкретному ядру. Есть несколько способов это сделать. Например, запустим решение в porto-контейнере (ядро выбирается с помощью аргумента cpu_set):

portoctl exec test command='sudo stress.sh' cpu_set=0

Офтоп: для запуска решений в продакшене мы используем QEMU-KVM. Porto-контейнер используется в статье, чтобы было проще показать.

Запуск с ядром, выделенным под решение, без нагрузки на соседние ядра:


Разница 375 мс. Стало лучше, но это все равно слишком много.

Тюним перфоманс


Давайте попробуем провести наш тест под нагрузкой. Под какой именно? Наша задача множеством потоков нагрузить все ядра. Это можно сделать несколькими способами:

  1. Написать простое приложение, которое создаст много потоков и начнет считать что-нибудь в каждом из них.
  2. Выполнить команду: cat /dev/zero | pbzip2 -c > /dev/null. pbzip2 здесь это многопоточная реализация bzip2.
  3. Или можно установить утилиту stress и дать нагрузку командой stress --cpu 12.

Запуск с ядром, выделенным под решение, с нагрузкой на соседние ядра:


Разница 1354 мс: на секунду больше, чем без нагрузки. Очевидно, нагрузка повлияла на время исполнения, несмотря на то, что мы запускались на изолированном ядре. Видно, что в определенный момент время исполнения уменьшилось. На первый взгляд это контринтуитивно: при растущей нагрузке производительность тоже увеличивается.

В продакшене такое поведение (когда время исполнения начинает плыть под нагрузкой) может выстрелить очень болезненно. Что такое нагрузка в данном случае? Поток решений от участников, чаще всего на крупных соревнованиях и олимпиадах.

Причина в том, что под нагрузкой включается Intel Turbo Boost технология увеличения частоты. Отключим ее. Для своего cтенда я выключил еще и SpeedStep. Для процессора AMD нужно было бы выключить Turbo Core Cool'n'Quiet. Все перечисленное делается в BIOS, основная идея отключить то, что автоматически управляет частотой процессора.

Запуск на изолированном ядре с отключенным Turbo Boost и нагрузкой на соседние ядра:


Выглядит неплохо, но разница все еще составляет 252 мс. И это все еще слишком много.

Офтоп: заметьте, как просело среднее время исполнения примерно на 25%. В повседневной жизни отключенные технологии это добро.

Мы избавились от конкуренции за ядра, стабилизировали частоту ядер теперь на них ничто не влияет. Так откуда же разница?

NUMA


Non-Uniform Memory Access, неравномерный доступ к памяти, или Non-Uniform Memory Architecture, архитектура с неравномерной памятью. В NUMA-системах (то есть, условно, на любом современном многопроцессорном компьютере) у каждого процессора есть локальная память, которая рассматривается как часть общей. Каждый процессор может обратиться и к своей локальной памяти, и к локальной памяти остальных процессоров (удаленной памяти). Неравномерность в том, что доступ к локальной памяти происходит заметно быстрее.

Время исполнения гуляет именно из-за такой неравномерности. Пофиксим ее, привязав наше исполнение к конкретной numa node. Для этого добавим numa node в конфигурацию porto-контейнера:

portoctl exec test command='stress.sh' cpu_set="node 0" cpu_set=0

Запуск на изолированном ядре с отключенным Turbo Boost, конфигурацией NUMA и нагрузкой на соседние ядра:


Разница 48 мс, а среднее время выполнения решения после того, как мы отключили процессорные оптимизаций, составляет 10 с. 48 мс в масштабе 10 с равносильно погрешности в 0,5%, очень хорошо.

Еще немного про isolcpus


У флага isolcpus есть проблема: некоторые системные потоки все равно могут schedule'иться на изолированное ядро.

Поэтому в продакшене мы используем пропатченное ядро с расширенной функциональностью этого флага. Тем самым мы выбираем ядро с учетом флага, когда происходит scheduling потоков.
Патч самописный, сделан над ядром 3.18. В этом ядре есть макрос kthread_run, которым некоторые драйвера пользуются для запуска своих потоков. Во время запуска не производится проверка на доступные CPU, и потоки могут исполняться на любом ядре вне зависимости от настроек isolcpus.

Поэтому мы и написали патч в нем добавлен новый аргумент запуска slave_cpus и несколько макросов, которые выбирают ядро для запуска с учетом маски из этого флага.

Планы на будущее


Пулы
Если одна решающая машина мощнее другой, то никакие ухищрения с изоляцией ядер не помогут в результате мы все равно получим большую разницу во времени исполнения. Поэтому нужно думать про гетерогенные среды. До сих пор мы просто не поддерживали гетерогенность весь парк решающих машин комплектуется одинаковым железом. Но в ближайшем будущем мы начнем разделять разнородное железо на однородные пулы, и каждое соревнование будет проходить в рамках одного пула с одинаковым железом.

Переезд в облако
Новым вызовом для системы станет необходимость запускаться в Яндекс.Облаке. По нынешним меркам железные сервера это ненадежно, переезд необходим, но важно сохранить консистентность выполнения посылок. Здесь технические возможности пока исследуются. Есть идея, что в крайних случаях на облачных машинах можно выполнять решения, не требующие строгого времени исполнения. Тем самым мы снизим нагрузку на железные машины и они будут заниматься только решениями, которые как раз требуют консистентности. Есть и другой вариант: сначала проверять посылку в облаке и, если она не уложилась в лимит времени, перепроверять на реальном железе.

Сбор статистики
Даже после всех ухищрений процессоры неизбежно будут троттлить. Чтобы снизить негативный эффект, будем выполнять решения параллельно, сравнивать результаты и, если они расходятся, запускать перепроверку. Кроме того, если одна из решающих машин постоянно деградирует, это повод вывести ее из обслуживания и разобраться с причинами.

Выводы


У Контеста есть особенность может показаться, что все сводится к простому запуску кода и получению результата. В статье я приоткрыл лишь один небольшой аспект этого процесса. Нечто подобное есть на каждом слое сервиса.
Подробнее..

Где порешать аналитические задачи от команд Яндекса? Контест и разбор

21.09.2020 18:14:10 | Автор: admin
Сегодня начинается пробный раунд чемпионата по программированию Yandex Cup. Это означает, что можно с помощью системы Яндекс.Контест решать задачи, подобные тем, которые будут в квалификационном раунде. Пока результат ни на что влияет.

В посте вы найдёте условия задач трека аналитики и разборы, которые сознательно спрятаны в спойлеры. Вы можете подглядеть решение либо сначала попробовать сделать задачи самостоятельно. Проверка происходит автоматически Контест сразу сообщит результат, и у вас будет возможность предложить другое решение.

A. Посчитать лгунов в стране

Решить в Контесте

В государстве живёт 10 000 человек. Они делятся на правдолюбов и лгунов. Правдолюбы говорят правду с вероятностью 80%, а лгуны с вероятностью 40%. Государство решило подсчитать правдолюбов и лгунов на основе опроса 100 жителей. Каждый раз случайно выбранного человека спрашивают: Вы лгун? и записывают ответ. Однако один человек может поучаствовать в опросе несколько раз. Если житель уже участвовал в опросе он отвечает то же самое, что и в первый раз. Мы знаем, что правдолюбов 70%, а лгунов 30%. Какая вероятность того, что государство недооценит количество лгунов, т. е. опрос покажет, что лгунов меньше 30%? Дайте ответ в процентах с точкой в качестве разделителя, результат округлите до сотых (пример ввода: 00.00).

Решение
1. Посчитаем вероятность получить ответ Да на вопрос Вы лгун?.

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

От правдолюбов, которых не спрашивали до этого: 0,2 * доля правдолюбов, которых не спрашивали.
От лгунов, которых не спрашивали до этого: 0,4 * доля лгунов, которых не спрашивали.
От правдолюбов, которых уже спрашивали до этого и которые ответили Да: 1,0 * доля правдолюбов, которых уже спрашивали и которые ответили Да.
От лгунов, которых уже спрашивали до этого и которые ответили Да: 1,0 * доля лгунов, которых уже спрашивали и которые ответили Да.

Посчитаем по шагам вероятность получить ответ Да от правдолюбов:

1. 0,2 * % правдолюбов.
2. 0,2 * (% правдолюбов % опрошенных правдолюбов) + 0,2 * (% опрошенных правдолюбов) = 0,2 * % правдолюбов.
3. Аналогично шагу 2.

То есть на каждом шаге вероятность получить ответ Да, я лгун от правдолюбов составляет 0,2 и не зависит от того, сколько правдолюбов опросили до этого. Точно так же для лгунов.

Таким образом, вероятность получить ответ Да от правдолюбов и лгунов: 0,2 * 0,7 + 0,4 * 0,3 = 0,26.

2. Посчитаем вероятность недооценить количество лгунов.

Количество лгунов, которое получит государство по результатам опроса, это биномиальное распределение с параметрами n = 100, p = 0,26.

Количеством успехов в нашем случае будет 30 (30% от 100 опрошенных). Если мы посмотрим на функцию распределения в этой точке, то получим P (x < 30) = 0,789458. Посчитать можно вот тут: stattrek.com/online-calculator/binomial.aspx.

Ответ в процентах, округлённых до сотых: 78,95.

B. Театральный сезон и телефоны

Решить в Контесте

Международный сервис по продаже билетов решил подвести итоги театрального сезона. В качестве одной из метрик руководитель проекта хочет посчитать количество пользователей, которые покупали билеты на разные спектакли.

При покупке билета пользователь указывает номер своего телефона. Необходимо найти спектакль с наибольшим числом уникальных телефонных номеров. И посчитать количество соответствующих уникальных телефонных номеров.

Формат ввода

Логи покупок доступны в файле ticket_logs.csv. В первом столбце название спектакля из базы сервиса. Во втором номер телефона, который оставил пользователь при покупке. Отметим, что в целях конспирации телефонные коды стран заменены на необслуживаемые в настоящий момент зоны.

Формат вывода

Число уникальных номеров.

Решение
Технические особенности данных

Подробный вариант решения лежит в main.py.

Пользователи оставляют телефонные номера в разных форматах. В качестве набора данных берутся случайно сгенерированные номера из необслуживаемых кодов. По данным из Википедии были взяты необслуживаемые зоны 801807.

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

1. 8-(801)-111-11-11
2. 8-801-111-11-11
3. 8801-111-11-11
4. 8-8011111111
5. +88011111111
6. 8-801-flowers, вместо цифр буквы (распространено в США)

Как предполагается обнаружить эти особенности:

1. Форматы в пунктах 14 видны при первом взгляде на данные и удаляются стандартными методами вроде replace.
2. Формат 5 легко отфильтровать, проверив число символов в телефонах после форматирования пункта 1. Во всех номерах будет 11 символов, кроме этого формата.
3. Пункт 6 самый неочевидный, надо догадаться проверить наличие нечисловых символов в номере телефона. Надеюсь, что смысл этих букв участник быстро найдёт в интернете.

Количество данных относительно небольшое, чтобы при желании можно было даже просмотреть каждую строчку вручную. Найти все шесть форматов можно вообще в первой сотне строк.

Код. Как генерировались данные

Этот раздел для тех, кому надо разобраться в устройстве кода или изменить сгенерированные логи в ticket_logs.csv. Все действия сложены в logs_generator.py. Как запустить:

python logs_generator.py

На выходе получается файл ticket_logs.csv.

Конфигурационный файл config.yaml

В файле собраны все параметры, которые влияют на создание файла ticket_logs.csv:

  • zones коды зон, которые используются в генерируемых телефонных номерах.
  • seven_letter_words слова, которые используются для создания телефонных номеров с буквами.
  • letters_to_numbers_dict словарь соответствия цифр на клавиатуре телефона и алфавита. Вряд ли он изменится.
  • performances список спектаклей и их весов. Чем выше вес, тем чаще спектакль будет в логах ticket_logs.csv.

Полезные константы в файле logs_generator.py:

USERS_COUNT = 1000  # количество пользователей (можно сверять в решении main.py результат)RESULT_FILE_LOCATION = 'ticket_logs.csv'  # куда сохранять созданные логи

Как формируются телефонные номера

Весь процесс создания номеров сложен в классе PhonesGenerator. Для создания случайного номера (и вариаций его написания) вызовите метод generate_number:

from yaml import load, FullLoaderfrom phone_numbers.phone_numbers_generator import PhonesGeneratorwith open('config.yaml') as f:    config = load(f, Loader=FullLoader)PhonesGenerator(config).generate_number()

Метод вернёт словарь с набором телефонных номеров. Пример:

{
'base': '8804academy', 'case_1': '8-(804)-aca-de-my', 'case_2': '8-804-aca-de-my',
'case_3': '8804-aca-de-my', 'case_4': '+8804academy', 'case_5': '8-804-academy',
'case_6': '8-804-2223369'
}


При многократном вызове метода generate_number в первую очередь отдаются номера с буквами. Слова в случайном порядке берутся из файла config.yaml, ключ seven_letter_words. Когда слова заканчиваются, то отдаются только числовые номера. Но можно и сразу генерировать числовые, для этого достаточно указать параметр generate_number(with_letters=False):

{
'base': '88062214016', 'case_1': '8-(806)-221-40-16', 'case_2': '8-806-221-40-16',
'case_3': '8806-221-40-16', 'case_4': '+88062214016', 'case_5': '8-806-2214016',
'case_6': '8-806-2214016'
}


В logs_generator.py из этого набора случайно выбирается от одного до некоторого набора вариантов. Подходящие варианты для числовых номеров задаёт константа PHONE_CASES, для буквенных PHONE_CASES_WITH_LETTERS в файле logs_generator.py. Сами форматы определяют методы build_case_1_number, ..., build_case_6_number в классе PhonesGenerator. Они же добавляются в конце метода generate_number.

Как генерируются названия спектаклей

Список спектаклей и их весов сложен в файле config.yaml. Чем выше вес, тем чаще спектакль будет в логах ticket_logs.csv. Этот процесс заложен в функции random_performance в logs_generator.py. Состав спектаклей:

  • Оперы: Севильский цирюльник, Волшебная флейта, Норма, Травиата, Евгений Онегин, Аида, Кармен, Свадьба Фигаро, Риголетто.
  • Балеты: Жизель, Лебединое озеро, Щелкунчик, Спящая красавица, Ромео и Джульетта, Дон Кихот, Баядерка, Спартак.
  • Мюзиклы: Вестсайдская история, TODD, Юнона и Авось, Ночь перед Рождеством, Чикаго, Ла-Ла Ленд, Нотр-Дам де Пари, Кошки.

Недостатки

Код класса PhonesGenerator слишком завязан на число символов в номере это можно улучшить.

C. Рассчитать pFound

Решить в Контесте

В архиве содержится три текстовых файла:

  • qid_query.tsv id запроса и текст запроса, разделённые табуляцией;
  • qid_url_rating.tsv id запроса, URL документа, релевантность документа запросу;
  • hostid_url.tsv id хоста и URL документа.

Нужно вывести текст запроса с максимальным значением метрики pFound, посчитанной по топ-10 документов. Выдача по запросу формируется по следующим правилам:
  • С одного хоста может быть только один документ на выдаче. Если для запроса есть несколько документов с одним и тем же id хоста берется максимально релевантный документ (а если несколько документов максимально релевантны, берется любой).
  • Документы по запросу сортируются по убыванию релевантности.
  • Если у нескольких документов с разных хостов релевантность одинакова, их порядок может быть произвольным.

Формула для расчёта pFound:

pFound = $\sum_{i=1}^{10}$pLook[i] pRel[i]
pLook[1] = 1
pLook[i] = pLook[i 1] (1 pRel[i 1]) (1 pBreak)
pBreak = 0,15

Формат вывода

Текст запроса с максимальным значением метрики. Например, для open_task.zip правильный ответ:
гугл переводчик

Решение
Все вводные даны в условии. Что-то дополнительное придумывать не нужно достаточно аккуратно реализовать вычисление pFound в коде и не забыть взять максимум по хосту. Для решения очень удобно использовать библиотеку pandas с помощью неё легко группировать по запросам и хостам и вычислять агрегации.

import pandas as pd# считываем данныеqid_query = pd.read_csv("hidden_task/qid_query.tsv", sep="\t", names=["qid", "query"])qid_url_rating = pd.read_csv("hidden_task/qid_url_rating.tsv", sep="\t", names=["qid", "url", "rating"])hostid_url = pd.read_csv("hidden_task/hostid_url.tsv", sep="\t", names=["hostid", "url"])# делаем join двух таблиц, чтобы было просто брать url с максимальным рейтингомqid_url_rating_hostid = pd.merge(qid_url_rating, hostid_url, on="url")def plook(ind, rels): if ind == 0: return 1    return plook(ind-1, rels)*(1-rels[ind-1])*(1-0.15)def pfound(group): max_by_host = group.groupby("hostid")["rating"].max() # максимальный рейтинг хоста top10 = max_by_host.sort_values(ascending=False)[:10] # берем топ-10 урлов с наивысшим рейтингом pfound = 0    for ind, val in enumerate(top10): pfound += val*plook(ind, top10.values) return pfoundqid_pfound = qid_url_rating_hostid.groupby('qid').apply(pfound) # группируем по qid и вычисляем pfoundqid_max = qid_pfound.idxmax() # берем qid с максимальным pfoundqid_query[qid_query["qid"] == qid_max]

D. Спортивный турнир

Решить в Контесте
Ограничение по времени на тест 2 с
Ограничение по памяти на тест 256 МБ
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Пока Маша была в отпуске, её коллеги организовали турнир по шахматам по олимпийской системе. За отдыхом Маша не обращала особого внимания на эту затею, так что она еле может вспомнить, кто с кем играл (про порядок игр даже речи не идёт). Внезапно Маше пришла в голову мысль, что неплохо бы привезти из отпуска сувенир победителю турнира. Маша не знает, кто победил в финальной игре, но сможет без труда вычислить, кто в нём играл, если только она правильно запомнила играющие пары. Помогите ей проверить, так ли это, и определить возможных кандидатов в победители.

Формат ввода

В первой строке находится целое число 3n2161,n=2k1 количество прошедших игр. В последующих n строках по две фамилии игроков (латинскими заглавными буквами) через пробел. Фамилии игроков различны. Все фамилии уникальны, однофамильцев среди коллег нет.

Формат ввода

Выведите NO SOLUTION (без кавычек), если Маша неправильно запомнила игры, и по этой сетке нельзя получить турнир по олимпийской системе. Если турнирная сетка возможна, выведите две фамилии в одной строке фамилии кандидатов на первое место (порядок не важен).

Пример 1
Ввод Вывод
7
GORBOVSKII ABALKIN
SIKORSKI KAMMERER
SIKORSKI GORBOVSKII
BYKOV IURKOVSKII
PRIVALOV BYKOV
GORBOVSKII IURKOVSKII
IURKOVSKII KIVRIN
IURKOVSKII GORBOVSKII
Пример 2
Ввод Вывод
3
IVANOV PETROV
PETROV BOSHIROV
BOSHIROV IVANOV
NO SOLUTION
Примечания

Олимпийская система, также известная как плей-офф система организации соревнований, при которой участник выбывает из турнира после первого же проигрыша. Подробнее про олимпийскую систему можно почитать на Википедии.

Схема первого теста из условия:



Решение
Из количества игрn = 2^k 1легко получить количество раундов турнираk.Обозначим количество игр, которые сыгралi-й участник, черезn_i.Очевидно, что финалисты сыграли максимальное количество раз (они единственные играли во всехkраундах).Теперь научимся проверять, что данный нам набор встреч между участниками возможен в турнире по олимпийской системе.Заметим, что игра между участникамиiиjмогла произойти только в раундеmin(n_i, n_j),поскольку этот раунд был последним для кого-то из них (раунды для удобства нумеруются с единицы).Назовём псевдораундом номерrмножество игр(i, j), для которыхmin(n_i, n_j) = r. Проверку корректности будем делать в соответствии с таким утверждением:

Утверждение.Набор из2^k 1игр задаёт турнир по олимпийской системе тогда и только тогда,когда:

1. В каждом псевдораунде все участники различны.
2. Количество игр в псевдораунде r равно 2^{k r}.

Доказательство.Необходимость этих двух условий очевидна: псевдораунды соответствуют настоящим раундам турнира,а для настоящих раундов условия верны.Достаточность докажем индукцией поk.Приk=1есть одна играс двумя различными участниками это корректный олимпийский турнир.Проверим переходk1 -> k.

Во-первых, докажем, что каждый участник турнира играл в первом псевдораунде.Рассмотрим произвольного игрока,пусть он участвовал вqиграх.В каждом псевдораунде он мог сыграть не более одного раза,причём в псевдораундах послеq-го он не мог играть ни разу.Значит, он должен был сыгратьпо одному разу в каждом из псевдораундов1, 2, ..., q.Это, в частности, означает, что все люди сыграли в первомпсевдораунде, а всего игроков2^k.Теперь докажем, что в каждой из2^{k1}игр первого псевдораунда был ровно один участниксn_i = 1.Как минимум один такой участник в каждой игре должен быть по определению псевдораунда.

С другой стороны,есть не менее2^{k1}человек сn_i > 1 это участники следующего псевдораунда.Следовательно, людей сn_i = 1было ровно2^{k1}, по одному на каждую игру.Теперь легко понять, как должен выглядеть первый раундискомого турнира: назначим в каждой игре первого псевдораунда проигравшим участника сn_i = 1,а победителем участника сn_i > 1.Множество игр между победителями удовлетворяет условиюдляk1(после выбрасывания игр из первого псевдораунда всеn_iуменьшились на 1).Следовательно, этомумножеству соответствует турнир по олимпийской системе.

import sysimport collectionsdef solve(fname):    games = []    for it, line in enumerate(open(fname)):        line = line.strip()        if not line:            continue        if it == 0:            n_games = int(line)            n_rounds = n_games.bit_length()        else:            games.append(line.split())    gamer2games_cnt = collections.Counter()    rounds = [[] for _ in range(n_rounds + 1)]    for game in games:        gamer_1, gamer_2 = game        gamer2games_cnt[gamer_1] += 1        gamer2games_cnt[gamer_2] += 1    ok = True    for game in games:        gamer_1, gamer_2 = game        game_round = min(gamer2games_cnt[gamer_1], gamer2games_cnt[gamer_2])        if game_round > n_rounds:            ok = False            break        rounds[game_round].append(game)    finalists = list((gamer for gamer, games_cnt in gamer2games_cnt.items() if games_cnt == n_rounds))    for cur_round in range(1, n_rounds):        if len(rounds[cur_round]) != pow(2, n_rounds - cur_round):            ok = False            break        cur_round_gamers = set()        for gamer_1, gamer_2 in rounds[cur_round]:            if gamer_1 in cur_round_gamers or gamer_2 in cur_round_gamers:                ok = False                break            cur_round_gamers.add(gamer_1)            cur_round_gamers.add(gamer_2)    print ' '.join(finalists) if ok else 'NO SOLUTION'def main():    solve('input.txt')if name == '__main__':    main()



Чтобы порешать задачи других треков чемпионата, нужно зарегистрироваться здесь.
Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru