Сегодня начинается пробный
раунд чемпионата по программированию
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.
На каждом шаге вероятность получить ответ Да, я лгун складывается из вероятности получить ответ Да:
От правдолюбов, которых не спрашивали до этого: 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. Как запустить:
На выходе получается файл ticket_logs.csv.
Конфигурационный файл config.yaml
В файле собраны все параметры, которые влияют на создание файла ticket_logs.csv:
Полезные константы в файле logs_generator.py:
Как формируются телефонные номера
Весь процесс создания номеров сложен в классе PhonesGenerator. Для создания случайного номера (и вариаций его написания) вызовите метод generate_number:
Метод вернёт словарь с набором телефонных номеров. Пример:
При многократном вызове метода generate_number в первую очередь отдаются номера с буквами. Слова в случайном порядке берутся из файла config.yaml, ключ seven_letter_words. Когда слова заканчиваются, то отдаются только числовые номера. Но можно и сразу генерировать числовые, для этого достаточно указать параметр generate_number(with_letters=False):
В 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. Состав спектаклей:
Недостатки
Код класса PhonesGenerator слишком завязан на число символов в номере это можно улучшить.
Подробный вариант решения лежит в 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 =
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 |
IURKOVSKII GORBOVSKII |
| Ввод | Вывод |
3 |
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).Следовательно, этомумножеству соответствует турнир по олимпийской системе.
Утверждение.Набор из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()
Чтобы порешать задачи других треков чемпионата, нужно зарегистрироваться здесь.
