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

Сегодня начинается пробный раунд чемпионата по программированию 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, 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. Чем выше вес, тем чаще спектакль будет в логах 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 и вычисляем pfound
qid_max = qid_pfound.idxmax() # берем qid с максимальным pfound

qid_query[qid_query["qid"] == qid_max]

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

^{Решить в Контесте}

Ограничение по времени на тест	2 с
Ограничение по памяти на тест	256 МБ
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

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

Формат ввода

В первой строке находится целое число 3 ≤ n ≤ 2¹⁶ − 1, n = 2^k − 1 — количество прошедших игр. В последующих 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 есть одна игра с двумя различными участниками — это корректный олимпийский турнир. Проверим переход 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()

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

Источник: https://habr.com/ru/company/yandex/blog/519846/

Вернуться к списку

Интересные статьи

Ещё один велосипед: пишем свой автозагрузчик классов для Битрикс

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

Разбор UI/UX на примере прототипа в Figma и основные принципы

Кому адресована статья В данной публикации я хочу помочь начинающим и «не очень» бизнес-аналитикам, менеджерам проектов, владельцам продуктов, желающим сделать свой первый сайт и все...

Гибкие процессы в IT команде

Всем привет, меня зовут Алексей Федоров, я тимлид команды финансов в Ситимобил. В этой статье я хочу поделиться тем, как устроен процесс гибкой разработки в нашей команде.

Коммерческие факторы ранжирования в 1С-Битрикс

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

Книга «Классические задачи Computer Science на языке Python»

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