Хабрахабр

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

Сегодня начинается пробный раунд чемпионата по программированию 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.

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

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

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. Форматы в пунктах 1–4 видны при первом взгляде на данные и удаляются стандартными методами вроде 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 PhonesGenerator with open('config.yaml') as f: config = load(f, Loader=FullLoader) PhonesGenerator(config).generate_number()

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

При многократном вызове метода 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 pfound qid_pfound = qid_url_rating_hostid.groupby('qid').apply(pfound) # группируем по qid и вычисляем pfoundqid_max = qid_pfound.idxmax() # берем qid с максимальным pfound qid_query[qid_query["qid"] == qid_max]

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

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

Формат ввода

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

Формат ввода

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

Пример 1

Пример 2
Примечания

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

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

Решение

Из количества игр 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 есть одна игра с двумя различными участниками — это корректный олимпийский турнир. Проверим переход k – 1 -> k. 

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

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

import sysimport collections def 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()

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

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»