🚵🏿 💃🏼 👩🏾‍⚖️ ¿Dónde resolver las tareas analíticas de los equipos de Yandex? Concurso y análisis 👩🏿‍🎨 ♍️ 🦀

La ronda de prueba del campeonato de programación de la Copa Yandex comienza hoy . Esto significa que puede utilizar el sistema Yandex.Contest para resolver problemas similares a los que estarán en la ronda de clasificación. Hasta ahora, el resultado no afecta a nada.

En la publicación, encontrará los términos de las tareas de la pista de análisis y los análisis, que están deliberadamente ocultos en spoilers. Puede ver la solución o intentar hacer las tareas usted mismo primero. La verificación es automática: el Concurso informará inmediatamente el resultado y tendrá la oportunidad de proponer otra solución.

A. Cuenta los mentirosos en el país

^{Resolver en concurso}

10,000 personas viven en el estado. Se dividen en amantes de la verdad y mentirosos. Los amantes de la verdad dicen la verdad con un 80% de probabilidad, y los mentirosos, con un 40% de probabilidad. El estado decidió contar a los amantes de la verdad y a los mentirosos según una encuesta de 100 residentes. Cada vez que se le pregunta a una persona seleccionada al azar: "¿Eres un mentiroso?" - y anote la respuesta. Sin embargo, una persona puede participar en la encuesta varias veces. Si un residente ya ha participado en la encuesta, responde igual que la primera vez. Sabemos que hay un 70% de amantes de la verdad y un 30% de mentirosos. ¿Cuál es la probabilidad de que el estado subestime el número de mentirosos, es decir, la encuesta mostrará que hay menos del 30% de mentirosos? Dé su respuesta en porcentaje con un punto como separador, redondee el resultado a la centésima más cercana (ejemplo de entrada: 00.00).

Decisión

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 y teléfonos

^{Decidir en concurso El}

servicio internacional de entradas ha decidido hacer balance de la temporada teatral. Como una de las métricas, el gerente de proyecto quiere contar la cantidad de usuarios que compraron boletos para diferentes presentaciones.

Al comprar un boleto, el usuario indica su número de teléfono. Debes encontrar el programa con la mayor cantidad de números de teléfono únicos. Y cuente la cantidad de números de teléfono únicos coincidentes.

Formato de entrada

Los registros de compras están disponibles en el archivoticket_logs.csv. La primera columna contiene el nombre de la actuación de la base de datos del servicio. En el segundo, el número de teléfono que dejó el usuario al comprar. Tenga en cuenta que, en aras de la conspiración, los códigos telefónicos de países se han reemplazado por zonas actualmente sin servicio.

Formato de salida

El número de números únicos.

Decisión

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 en concurso}

Elarchivocontiene tres archivos de texto:

qid_query.tsv: el ID de la consulta y el texto de la consulta, separados por tabulaciones;
qid_url_rating.tsv: ID de solicitud, URL del documento, relevancia del documento para la solicitud;
hostid_url.tsv: ID de host y URL del documento.

Es necesario mostrar el texto de la solicitud con el valor máximo de la métrica pFound, calculado a partir de los 10 documentos principales. La emisión a solicitud se forma de acuerdo con las siguientes reglas:

De un host solo puede haber un documento emitido. Si hay varios documentos para la solicitud con el mismo ID de host, se toma el documento más relevante (y si varios documentos son los más relevantes, se toma cualquiera).
Los documentos bajo demanda se clasifican en orden descendente de relevancia.
Si varios documentos de diferentes hosts tienen la misma relevancia, su orden puede ser arbitrario.

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 salida

El texto de la solicitud con el valor métrico máximo. Por ejemplo, para open_task.zip, la respuesta correcta es:

Decisión

. - — 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. Torneo deportivo

^{Resolver en concurso}

Límite de tiempo para la prueba	2 segundos
Límite de memoria por prueba	256 MB
Entrada	entrada estándar o input.txt
Salida	salida estándar o output.txt

Mientras Masha estaba de vacaciones, sus compañeros organizaron un torneo de ajedrez según el sistema olímpico. Mientras descansaba, Masha no prestó mucha atención a esta aventura, por lo que apenas puede recordar quién jugaba con quién (no se trata del orden de los juegos). De repente, a Masha se le ocurrió que sería bueno llevar un recuerdo de vacaciones al ganador del torneo. Masha no sabe quién ganó el juego final, pero puede descubrir fácilmente quién jugó en él, si tan solo recordara correctamente las parejas de juego. Ayúdela a comprobar si este es el caso e identificar posibles ganadores.

Formato de entrada

La primera línea contiene un número entero 3 ≤ n ≤ 2 ¹⁶ - 1, n = 2 ^k - 1 - el número de juegos pasados. Las siguientes n líneas contienen dos apellidos de los jugadores (en mayúsculas latinas) separados por un espacio. Los nombres de los jugadores son diferentes. Todos los apellidos son únicos, no hay homónimos entre compañeros.

Formato de entrada

Imprima "SIN SOLUCIÓN" (sin comillas) si Masha ha memorizado los juegos incorrectamente y es imposible conseguir un torneo según el sistema olímpico utilizando esta cuadrícula. Si la cuadrícula del torneo es posible, imprima dos apellidos en una línea: los nombres de los candidatos para el primer lugar (el orden no es importante).

Ejemplo 1

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

Ejemplo 2

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

Notas El

sistema olímpico, también conocido como playoffs, es un sistema de organización de competencias en el que un competidor es eliminado de un torneo después de la primera derrota. Puede leer más sobre el sistema olímpico en Wikipedia .

Esquema de la primera prueba de la condición:

Decisión

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 solucionar los problemas de otras pistas del campeonato, debes registrarte aquí .

¿Dónde resolver las tareas analíticas de los equipos de Yandex? Concurso y análisis

A. Cuenta los mentirosos en el país

B. Temporada de teatro y teléfonos

C. Calcular pFound

D. Torneo deportivo

More articles: