Оффлайн
- Регистрация
- 21.07.20
- Сообщения
- 40.408
- Реакции
- 1
- Репутация
- 0
You must be registered for see links
. Это означает, что можно с помощью системы Яндекс.Контест решать задачи, подобные тем, которые будут в квалификационном раунде. Пока результат ни на что влияет. В посте вы найдёте условия задач трека аналитики и разборы, которые сознательно спрятаны в спойлеры. Вы можете подглядеть решение либо сначала попробовать сделать задачи самостоятельно. Проверка происходит автоматически — Контест сразу сообщит результат, и у вас будет возможность предложить другое решение.
A. Посчитать лгунов в стране
[SUP]
You must be registered for see links
[/SUP]В государстве живёт 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. Посчитать можно вот тут:
You must be registered for see links
.Ответ в процентах, округлённых до сотых: 78,95.
B. Театральный сезон и телефоны
[SUP]
You must be registered for see links
[/SUP]Международный сервис по продаже билетов решил подвести итоги театрального сезона. В качестве одной из метрик руководитель проекта хочет посчитать количество пользователей, которые покупали билеты на разные спектакли.
При покупке билета пользователь указывает номер своего телефона. Необходимо найти спектакль с наибольшим числом уникальных телефонных номеров. И посчитать количество соответствующих уникальных телефонных номеров.
Формат ввода
Логи покупок доступны в файле
You must be registered for see links
. В первом столбце название спектакля из базы сервиса. Во втором — номер телефона, который оставил пользователь при покупке. Отметим, что в целях конспирации телефонные коды стран заменены на необслуживаемые в настоящий момент зоны.Формат вывода
Число уникальных номеров.
Решение
Технические особенности данных
Подробный вариант решения лежит в
You must be registered for see links
.Пользователи оставляют телефонные номера в разных форматах. В качестве набора данных берутся случайно сгенерированные номера из необслуживаемых кодов. По данным из
You must be registered for see links
были взяты необслуживаемые зоны 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 самый неочевидный, надо догадаться проверить наличие нечисловых символов в номере телефона. Надеюсь, что смысл этих букв участник быстро найдёт в интернете.
Количество данных относительно небольшое, чтобы при желании можно было даже просмотреть каждую строчку вручную. Найти все шесть форматов можно вообще в первой сотне строк.
Код. Как генерировались данные
Этот раздел для тех, кому надо разобраться в устройстве кода или изменить сгенерированные логи в
You must be registered for see links
. Все действия сложены в logs_generator.py. Как запустить:python logs_generator.py
На выходе получается файл
You must be registered for see links
.Конфигурационный файл config.yaml
В файле собраны все параметры, которые влияют на создание файла
You must be registered for see links
:- zones — коды зон, которые используются в генерируемых телефонных номерах.
- seven_letter_words — слова, которые используются для создания телефонных номеров с буквами.
- letters_to_numbers_dict — словарь соответствия цифр на клавиатуре телефона и алфавита. Вряд ли он изменится.
- performances — список спектаклей и их весов. Чем выше вес, тем чаще спектакль будет в логах
You must be registered for see links.
Полезные константы в файле logs_generator.py:
USERS_COUNT = 1000 # количество пользователей (можно сверять в решении main.py результат)
RESULT_FILE_LOCATION = 'ticket_logs.csv' # куда сохранять созданные логи
Как формируются телефонные номера
Весь процесс создания номеров сложен в классе PhonesGenerator. Для создания случайного номера (и вариаций его написания) вызовите метод generate_number:
from yaml import load, FullLoader
from phone_numbers.phone_numbers_generator import PhonesGenerator
with 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. Чем выше вес, тем чаще спектакль будет в логах
You must be registered for see links
. Этот процесс заложен в функции random_performance в logs_generator.py. Состав спектаклей:- Оперы: «Севильский цирюльник», «Волшебная флейта», «Норма», «Травиата», «Евгений Онегин», «Аида», «Кармен», «Свадьба Фигаро», «Риголетто».
- Балеты: «Жизель», «Лебединое озеро», «Щелкунчик», «Спящая красавица», «Ромео и Джульетта», «Дон Кихот», «Баядерка», «Спартак».
- Мюзиклы: «Вестсайдская история», «TODD», «Юнона и Авось», «Ночь перед Рождеством», «Чикаго», «Ла-Ла Ленд», «Нотр-Дам де Пари», «Кошки».
Недостатки
Код класса PhonesGenerator слишком завязан на число символов в номере — это можно улучшить.
C. Рассчитать pFound
[SUP]
You must be registered for see links
[/SUP]В
You must be registered for see links
содержится три текстовых файла:- qid_query.tsv — id запроса и текст запроса, разделённые табуляцией;
- qid_url_rating.tsv — id запроса, URL документа, релевантность документа запросу;
- hostid_url.tsv — id хоста и URL документа.
Нужно вывести текст запроса с максимальным значением метрики pFound, посчитанной по топ-10 документов. Выдача по запросу формируется по следующим правилам:
- С одного хоста может быть только один документ на выдаче. Если для запроса есть несколько документов с одним и тем же id хоста — берется максимально релевантный документ (а если несколько документов максимально релевантны, берется любой).
- Документы по запросу сортируются по убыванию релевантности.
- Если у нескольких документов с разных хостов релевантность одинакова, их порядок может быть произвольным.
Формула для расчёта pFound:
pFound =
pLook[1] = 1
pLook = 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 и вычисляем pfound
qid_max = qid_pfound.idxmax() # берем qid с максимальным pfound
qid_query[qid_query["qid"] == qid_max]
D. Спортивный турнир
[SUP]
You must be registered for see links
[/SUP]Ограничение по времени на тест | 2 с |
Ограничение по памяти на тест | 256 МБ |
Ввод | стандартный ввод или input.txt |
Вывод | стандартный вывод или output.txt |
Формат ввода
В первой строке находится целое число 3 ≤ n ≤ 2[SUP]16[/SUP] − 1, n = 2[SUP]k[/SUP] − 1 — количество прошедших игр. В последующих n строках — по две фамилии игроков (латинскими заглавными буквами) через пробел. Фамилии игроков различны. Все фамилии уникальны, однофамильцев среди коллег нет.
Формат ввода
Выведите «NO SOLUTION» (без кавычек), если Маша неправильно запомнила игры, и по этой сетке нельзя получить турнир по олимпийской системе. Если турнирная сетка возможна, выведите две фамилии в одной строке — фамилии кандидатов на первое место (порядок не важен).
Пример 1
Ввод | Вывод |
7 GORBOVSKII ABALKIN SIKORSKI KAMMERER SIKORSKI GORBOVSKII BYKOV IURKOVSKII PRIVALOV BYKOV GORBOVSKII IURKOVSKII IURKOVSKII KIVRIN | IURKOVSKII GORBOVSKII |
Ввод | Вывод |
3 IVANOV PETROV PETROV BOSHIROV BOSHIROV IVANOV | NO SOLUTION |
Олимпийская система, также известная как плей-офф — система организации соревнований, при которой участник выбывает из турнира после первого же проигрыша. Подробнее про олимпийскую систему можно почитать на
You must be registered for see links
.Схема первого теста из условия:
Решение
Из количества игр 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 sys
import 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()
Чтобы порешать задачи других треков чемпионата, нужно зарегистрироваться
You must be registered for see links
.