🧑🏽 👨‍👨‍👦‍👦 🤞🏼 Onde resolver tarefas analíticas das equipes Yandex? Concurso e análise 🔣 🔽 🙆🏾

A rodada de teste do campeonato de programação da Yandex Cup começa hoje . Isso significa que você pode usar o sistema Yandex.Contest para resolver problemas semelhantes aos que estarão na fase de qualificação. Até agora, o resultado não afeta nada.

Na postagem, você encontrará os termos das tarefas de acompanhamento e análises analíticas, que estão deliberadamente escondidas em spoilers. Você pode ver a solução ou tentar fazer as tarefas sozinho primeiro. A verificação é automática - o Concurso reportará imediatamente o resultado e você terá a oportunidade de propor outra solução.

A. Conte os mentirosos do país

^{Resolva em Concurso}

10.000 pessoas moram no estado. Eles estão divididos em amantes da verdade e mentirosos. Os amantes da verdade dizem a verdade com 80% de probabilidade, e os mentirosos - com 40% de probabilidade. O estado decidiu contar os amantes da verdade e mentirosos com base em uma pesquisa com 100 residentes. Cada vez que uma pessoa selecionada aleatoriamente é questionada, "Você é um mentiroso?" - e escreva a resposta. No entanto, uma pessoa pode participar da pesquisa várias vezes. Se um residente já participou da pesquisa, ele responde da mesma forma que da primeira vez. Sabemos que existem 70% dos amantes da verdade e 30% dos mentirosos. Qual a probabilidade de que o estado subestime o número de mentirosos, ou seja, uma pesquisa mostrará que há menos de 30% dos mentirosos? Dê sua resposta em porcentagem com um ponto como separador, arredonde o resultado para o centésimo mais próximo (exemplo de entrada: 00,00).

Decisão

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. Temporada de teatro e telefones

^{Decidir no concurso O}

serviço internacional de ingressos decidiu fazer um balanço da temporada teatral. Como uma das métricas, o gerente de projeto deseja contar o número de usuários que compraram ingressos para apresentações diferentes.

Ao comprar a passagem, o usuário indica seu número de telefone. Você precisa encontrar o programa com o maior número de números de telefone exclusivos. E conte o número de números de telefone exclusivos correspondentes.

Formato de entrada

Os registros de compra estão disponíveis no arquivoticket_logs.csv. A primeira coluna contém o nome do desempenho do banco de dados de serviço. Na segunda - o número de telefone que o usuário deixou no momento da compra. Observe que, por causa da conspiração, os códigos de país dos telefones foram substituídos por zonas atualmente não atendidas.

Formato de saída

O número de números exclusivos.

Decisão

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. Calcular pFound

^{Resolver no concurso}

Oarquivocontém três arquivos de texto:

qid_query.tsv - id da consulta e texto da consulta, separados por tabulações;
qid_url_rating.tsv - id do pedido, URL do documento, relevância do documento para o pedido;
hostid_url.tsv - id do host e url do documento.

É necessário exibir o texto da solicitação com o valor máximo da métrica pFound, calculado a partir dos 10 principais documentos. A emissão mediante solicitação é formada de acordo com as seguintes regras:

De um host, pode haver apenas um documento em questão. Se houver vários documentos para a solicitação com o mesmo id de host, o documento mais relevante será obtido (e se vários documentos forem os mais relevantes, qualquer um será obtido).
Os documentos sob demanda são classificados em ordem decrescente de relevância.
Se vários documentos de hosts diferentes tiverem a mesma relevância, sua ordem pode ser arbitrária.

Fórmula para calcular pFound:

pFound =

\sum_{i = 1}^{10}

$\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

Formato de saída

O texto da solicitação com o valor máximo da métrica. Por exemplo, para open_task.zip, a resposta correta é:

Decisão

. - — 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. Torneio de esportes

^{Resolva no concurso}

Limite de tempo para o teste	2 segundos
Limite de memória por teste	256 MB
Entrada	entrada padrão ou input.txt
Resultado	saída padrão ou output.txt

Enquanto Masha estava de férias, seus colegas organizaram um torneio de xadrez de acordo com o sistema olímpico. Enquanto descansava, Masha não prestou muita atenção a essa aventura, então ela mal consegue lembrar quem jogou com quem (não há dúvida sobre a ordem dos jogos). De repente, Masha teve a ideia de que seria bom levar uma lembrança de férias para o vencedor do torneio. Masha não sabe quem ganhou o jogo final, mas ela pode facilmente descobrir quem jogou nele, se apenas se lembrasse corretamente dos pares de jogo. Ajude-a a verificar se esse é o caso e identificar vencedores em potencial.

Formato de entrada

A primeira linha contém um inteiro 3 ≤ n ≤ 2 ¹⁶ - 1, n = 2 ^k - 1 - o número de jogos anteriores. As próximas n linhas contêm dois sobrenomes dos jogadores (em letras latinas maiúsculas) separados por um espaço. Os nomes dos jogadores são diferentes. Todos os sobrenomes são únicos, não há homônimos entre os colegas.

Formato de entrada

Imprima "SEM SOLUÇÃO" (sem aspas) se Masha tiver memorizado os jogos incorretamente e for impossível obter um torneio de acordo com o sistema olímpico usando esta grade. Se a grade do torneio for possível, imprima dois sobrenomes em uma linha - os nomes dos candidatos ao primeiro lugar (a ordem não é importante).

Exemplo 1

Entrada	Resultado
`7 GORBOVSKII ABALKIN SIKORSKI KAMMERER SIKORSKI GORBOVSKII BYKOV IURKOVSKII PRIVALOV BYKOV GORBOVSKII IURKOVSKII IURKOVSKII KIVRIN`	`IURKOVSKII GORBOVSKII`

Exemplo 2

Entrada	Resultado
`3 IVANOV PETROV PETROV BOSHIROV BOSHIROV IVANOV`	`NO SOLUTION`

Notas O

sistema olímpico, também conhecido como playoffs, é um sistema de organização de competição em que um competidor é eliminado de um torneio após a primeira derrota. Você pode ler mais sobre o sistema olímpico na Wikipedia .

Esquema do primeiro teste da condição:

Decisão

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()

Para resolver os problemas das outras pistas do campeonato, você precisa se registrar aqui .

Onde resolver tarefas analíticas das equipes Yandex? Concurso e análise

A. Conte os mentirosos do país

B. Temporada de teatro e telefones

C. Calcular pFound

D. Torneio de esportes

More articles: