👩🏽‍⚕️ 🆖 🏁 Wo können analytische Aufgaben von Yandex-Teams gelöst werden? Wettbewerb und Analyse 🧓🏻 🚲 👨🏾‍💻

Die Testrunde der Yandex Cup Programmiermeisterschaft beginnt heute . Dies bedeutet, dass Sie das Yandex.Contest-System verwenden können, um Probleme zu lösen, die denen in der Qualifikationsrunde ähneln. Bisher hat das Ergebnis keinen Einfluss.

In der Post finden Sie die Bedingungen für die Aufgaben des Analytics Track und der Analysen, die bewusst in Spoilern versteckt sind. Sie können die Lösung sehen oder versuchen, die Aufgaben zuerst selbst zu erledigen. Die Überprüfung erfolgt automatisch - der Wettbewerb meldet sofort das Ergebnis und Sie haben die Möglichkeit, eine andere Lösung vorzuschlagen.

A. Zählen Sie die Lügner im Land

^{Löse im Wettbewerb}

10.000 Menschen leben im Staat. Sie sind unterteilt in Liebhaber der Wahrheit und Lügner. Wahrheitsliebhaber sagen die Wahrheit mit einer Wahrscheinlichkeit von 80% und Lügner mit einer Wahrscheinlichkeit von 40%. Der Staat beschloss, die Wahrheitsliebhaber und Lügner anhand einer Umfrage unter 100 Einwohnern zu zählen. Jedes Mal, wenn eine zufällig ausgewählte Person gefragt wird: "Sind Sie ein Lügner?" - und schreibe die Antwort auf. Eine Person kann jedoch mehrmals an der Umfrage teilnehmen. Wenn ein Bewohner bereits an der Umfrage teilgenommen hat, antwortet er genauso wie beim ersten Mal. Wir wissen, dass es 70% der Wahrheitsliebhaber und 30% der Lügner gibt. Wie hoch ist die Wahrscheinlichkeit, dass der Staat die Anzahl der Lügner unterschätzt, dh eine Umfrage zeigt, dass es weniger als 30% der Lügner gibt? Geben Sie Ihre Antwort in Prozent mit einem Punkt als Trennzeichen ein und runden Sie das Ergebnis auf das nächste Hundertstel (Beispiel für die Eingabe: 00.00).

Entscheidung

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. Theatersaison und Telefone

^{Entscheiden Sie sich für einen Wettbewerb Der}

internationale Ticketservice hat beschlossen, eine Bestandsaufnahme der Theatersaison vorzunehmen. Als eine der Metriken möchte der Projektmanager die Anzahl der Benutzer zählen, die Tickets für verschiedene Vorstellungen gekauft haben.

Beim Kauf eines Tickets gibt der Benutzer seine Telefonnummer an. Sie müssen die Show mit der größten Anzahl eindeutiger Telefonnummern finden. Und zählen Sie die Anzahl der übereinstimmenden eindeutigen Telefonnummern.

EingabeformatKaufprotokolle

sind in der Dateiticket_logs.csvverfügbar. Die erste Spalte enthält den Namen der Leistung aus der Servicedatenbank. Im zweiten - die Telefonnummer, die der Benutzer beim Kauf hinterlassen hat. Beachten Sie, dass aus Gründen der Verschwörung die Telefon-Ländercodes durch derzeit nicht versorgte Zonen ersetzt wurden.

Ausgabeformat

Die Anzahl der eindeutigen Nummern.

Entscheidung

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. Berechnen Sie pFound

^{Im Wettbewerb lösen}

DasArchiventhält drei Textdateien:

qid_query.tsv - die ID der Abfrage und der Text der Abfrage, getrennt durch Tabulatoren;
qid_url_rating.tsv - Anforderungs-ID, Dokument-URL, Dokumentrelevanz für die Anforderung;
hostid_url.tsv - Host-ID und Dokument-URL.

Es ist erforderlich, den Anforderungstext mit dem Maximalwert der pFound-Metrik anzuzeigen, der aus den Top-10-Dokumenten berechnet wird. Die Ausstellung erfolgt auf Anfrage nach folgenden Regeln:

Von einem Host kann nur ein Dokument ausgestellt werden. Wenn für die Anforderung mehrere Dokumente mit derselben Host-ID vorhanden sind, wird das relevanteste Dokument verwendet (und wenn mehrere Dokumente am relevantesten sind, wird eines verwendet).
Dokumente auf Anfrage werden in absteigender Reihenfolge ihrer Relevanz sortiert.
Wenn mehrere Dokumente von verschiedenen Hosts dieselbe Relevanz haben, kann ihre Reihenfolge beliebig sein.

Formel zur Berechnung von 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

Ausgabeformat

Der Anforderungstext mit dem maximalen Metrikwert. Für open_task.zip lautet die richtige Antwort beispielsweise:

Entscheidung

. - — 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. Sportturnier

^{Löse im Wettbewerb}

Zeitlimit für den Test	2 Sek
Speicherlimit pro Test	256 MB
Eingang	Standardeingabe oder input.txt
Ausgabe	Standardausgabe oder output.txt

Während Mascha im Urlaub war, organisierten ihre Kollegen ein Schachturnier nach dem olympischen System. Während sie sich ausruhte, schenkte Mascha diesem Unterfangen nicht viel Aufmerksamkeit, so dass sie sich kaum erinnern kann, wer mit wem gespielt hat (es gibt keine Frage der Reihenfolge der Spiele). Plötzlich hatte Mascha die Idee, dass es schön wäre, dem Gewinner des Turniers aus dem Urlaub ein Souvenir zu bringen. Mascha weiß nicht, wer das letzte Spiel gewonnen hat, aber sie kann leicht herausfinden, wer darin gespielt hat, wenn sie sich nur richtig an die spielenden Paare erinnert. Helfen Sie ihr, zu überprüfen, ob dies der Fall ist, und identifizieren Sie potenzielle Gewinner.

Eingabeformat

Die erste Zeile enthält eine ganze Zahl 3 ≤ n ≤ 2 ¹⁶ - 1, n = 2 ^k - 1 - die Anzahl der vergangenen Spiele. Die nächsten n Zeilen enthalten zwei Nachnamen der Spieler (in lateinischen Großbuchstaben), die durch ein Leerzeichen getrennt sind. Die Namen der Spieler sind unterschiedlich. Alle Nachnamen sind eindeutig, es gibt keine Namensvetter unter Kollegen.

Eingabeformat

Geben Sie "NO SOLUTION" (ohne Anführungszeichen) aus, wenn Masha die Spiele falsch gespeichert hat und es unmöglich ist, ein Turnier gemäß dem olympischen System in dieser Tabelle zu erhalten. Wenn das Turnierraster möglich ist, drucken Sie zwei Nachnamen in eine Zeile - die Namen der Kandidaten für den ersten Platz (die Reihenfolge ist nicht wichtig).

Beispiel 1

Eingang	Ausgabe
`7 GORBOVSKII ABALKIN SIKORSKI KAMMERER SIKORSKI GORBOVSKII BYKOV IURKOVSKII PRIVALOV BYKOV GORBOVSKII IURKOVSKII IURKOVSKII KIVRIN`	`IURKOVSKII GORBOVSKII`

Beispiel 2

Eingang	Ausgabe
`3 IVANOV PETROV PETROV BOSHIROV BOSHIROV IVANOV`	`NO SOLUTION`

Anmerkungen Das

olympische System, auch als Playoffs bekannt, ist ein Organisationssystem für Wettbewerbe, bei dem ein Teilnehmer nach der ersten Niederlage aus einem Turnier ausgeschieden ist. Sie können mehr über das olympische System auf Wikipedia lesen .

Schema des ersten Tests aus der Bedingung:

Entscheidung

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

Um die Probleme anderer Strecken der Meisterschaft zu lösen, müssen Sie sich hier registrieren .

Wo können analytische Aufgaben von Yandex-Teams gelöst werden? Wettbewerb und Analyse

A. Zählen Sie die Lügner im Land

B. Theatersaison und Telefone

C. Berechnen Sie pFound

D. Sportturnier

More articles: