Задачи пробного тура чемпионата
по програм­мированию трека «Аналитика»

В архиве содержится три текстовых файла:

• qid_query.tsv — id запроса и текст запроса, разделённые табуляцией;
• qid_url_rating.tsv — id запроса, URL документа, релевантность документа запросу;
• hostid_url.tsv — id хоста и URL документа.

Нужно вывести текст запроса с максимальным значением метрики $\mathrm{pFound}$, посчитанной по топ-10 документов.
Если для запроса есть несколько документов с одним и тем же id хоста — оставить только максимально релевантный документ (а если несколько документов максимально релевантны, выбрать любой).
Документы по запросу сортируются по убыванию релевантности после выбора одного документа для хоста. Если у нескольких документов с разных хостов релевантность одинакова, их порядок может быть произвольным.

Формула для расчёта $\mathrm{pFound}$:

Формат вывода

Текст запроса с максимальным значением метрики.
Например, для open_task.zip правильный ответ:
гугл переводчик

	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]

	

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

Формат ввода

В первой строке находится целое число $3\le n\le 2^{16}-1\text{, }n=2^k-1$ — количество прошедших игр. В последующих $n$ строках — по две фамилии игроков (латинскими заглавными буквами) через пробел. Фамилии игроков различны. Все фамилии уникальны, однофамильцев среди коллег нет.

Формат вывода

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

Пример 2

Пример 1

Примечания

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

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

Из количества игр $n=2^k-1$ легко получить количество раундов турнира $k$. Обозначим количество игр, которые сыграл i-й участник, через $n_{\mathrm{i}}\text{. }$ Очевидно, что финалисты сыграли максимальное количество раз (они единственные играли во всех $k$ раундах). Теперь научимся проверять, что данный нам набор встреч между участниками возможен в турнире по олимпийской системе. Заметим, что игра между участниками $i$ и $j$ могла произойти только в раунде $\min (n_{\mathrm{i}}\text{, }{n}_{\mathrm{j}})\text{, }$ поскольку этот раунд был последним для кого-то из них (раунды для удобства нумеруются с единицы). Назовём псевдораундом номер $r$ множество игр $(i\text{, }j)\text{, }$ для которых $\min (n_{\mathrm{i}}\text{, }{n}_{\mathrm{j}})=r\text{. }$ Проверку корректности будем делать в соответствии с таким утверждением:

Утверждение. Набор из $n=2^k-1$ игр задаёт турнир по олимпийской системе тогда и только тогда, когда:

1. В каждом псевдораунде все участники различны.
2. Количество игр в псевдораунде $r$ равно $2^{\{k-r\}}\text{. }$

Доказательство. Необходимость этих двух условий очевидна: псевдораунды соответствуют настоящим раундам турнира, а для настоящих раундов условия верны. Достаточность докажем индукцией по $k$. При $k=1$ есть одна игра с двумя различными участниками — это корректный олимпийский турнир. Проверим переход $k–1->k\text{. }$ Во-первых, докажем, что каждый участник турнира играл в первом псевдораунде. Рассмотрим произвольного игрока, пусть он участвовал в $q$ играх. В каждом псевдораунде он мог сыграть не более одного раза, причём в псевдораундах после $q$-го он не мог играть ни разу. Значит, он должен был сыграть по одному разу в каждом из псевдораундов 1, 2, ..., $q$. Это, в частности, означает, что все люди сыграли в первом псевдораунде, а всего игроков $2^k\text{. }$ Теперь докажем, что в каждой из $2^{\{k-r\}}\text{. }$ игр первого псевдораунда был ровно один участник с $n_{\mathrm{i}}=1\text{. }$ Как минимум один такой участник в каждой игре должен быть по определению псевдораунда. С другой стороны, есть не менее $2^{\{k-r\}}$ человек с $n_{\mathrm{i}}>1$ — это участники следующего псевдораунда. Следовательно, людей с $n_{\mathrm{i}}=1\text{. }$ было ровно $2^{\{k-r\}}$ по одному на каждую игру. Теперь легко понять, как должен выглядеть первый раунд искомого турнира: назначим в каждой игре первого псевдораунда проигравшим участника с $n_{\mathrm{i}}=1\text{, }$ а победителем — участника с $n_{\mathrm{i}}>1\text{. }$ Множество игр между победителями удовлетворяет условию для $k–1$ (после выбрасывания игр из первого псевдораунда все $n_{\mathrm{i}}\text{, }$ уменьшились на 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()