company_banner

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

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

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

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

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

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

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

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

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

    При первом опросе: вероятность ответа «Да» от правдолюбов * доля правдолюбов = 0,2 * 0,7.
    Последующие опросы: вероятность ответа «Да» от правдолюбов * (доля правдолюбов – доля опрошенных правдолюбов) + вероятность ответа «Да» от правдолюбов * (доля опрошенных правдолюбов) = вероятность ответа «Да» от правдолюбов * доля правдолюбов = 0,2 * 0,7.

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

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

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

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

    Необходимо найти вероятность того, что по результатам опроса лгунов в стране окажется меньше 30 (30% от 100 опрошенных): P (x < 30). Для биномиального распределения с параметрами n = 100, p = 0,26 такая вероятность составляет 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 самый неочевидный, надо догадаться проверить наличие нечисловых символов в номере телефона. Надеюсь, что смысл этих букв участник быстро найдёт в интернете.

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

    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 ≤ 216 − 1, n = 2k − 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()



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

    Комментарии 1

      0
      С задачей B что-то пошло не так.
      Если не считать разными телефоны в разных форматах (требование из решения, а не из условия), то получается 202.
      И этот ответ принимается («Вердикт: OK», «Статус: Полное решение»), но не приносит баллов (только «птичку» — см. первый скриншот) ¯\_(ツ)_/¯
      Скриншоты


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

      Самое читаемое