🚠 📨 🍉 Di mana harus menyelesaikan tugas analitik dari tim Yandex? Kontes dan analisis 👨‍👦 🐏 👚

Putaran uji coba kejuaraan pemrograman Yandex Cup dimulai hari ini . Ini berarti Anda dapat menggunakan sistem Yandex.Contest untuk menyelesaikan masalah yang serupa dengan yang akan terjadi di babak kualifikasi. Sejauh ini, hasilnya tidak berpengaruh apa-apa.

Di pos, Anda akan menemukan kondisi untuk tugas pelacakan dan analisis analitik, yang sengaja disembunyikan di spoiler. Anda dapat melihat solusinya atau mencoba melakukan tugas sendiri terlebih dahulu. Pemeriksaannya otomatis - Kontes akan segera melaporkan hasilnya, dan Anda akan memiliki kesempatan untuk mengusulkan solusi lain.

A. Hitung para pembohong di negara ini

^{Selesaikan dalam Kontes}

10.000 orang tinggal di negara bagian. Mereka terbagi menjadi pecinta kebenaran dan pembohong. Pencinta kebenaran mengatakan kebenaran dengan probabilitas 80%, dan pembohong - dengan probabilitas 40%. Negara memutuskan untuk menghitung pecinta kebenaran dan pembohong berdasarkan survei terhadap 100 penduduk. Setiap kali orang yang dipilih secara acak ditanya, "Apakah Anda pembohong?" - dan tuliskan jawabannya. Namun, satu orang dapat mengikuti survei beberapa kali. Jika sudah ada warga yang ikut survei, jawabnya sama seperti saat pertama kali. Kami tahu bahwa ada 70% pecinta kebenaran dan 30% pembohong. Seberapa besar kemungkinan negara akan meremehkan jumlah pembohong, yaitu, survei menunjukkan bahwa ada kurang dari 30% pembohong? Berikan jawaban Anda dalam persentase dengan titik sebagai pemisah, bulatkan hasilnya ke perseratus terdekat (contoh input: 00.00).

Keputusan

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. Musim teater dan telepon

^{Putuskan dalam Kontes Layanan}

tiket internasional telah memutuskan untuk mencatat musim teater. Sebagai salah satu metrik, manajer proyek ingin menghitung jumlah pengguna yang membeli tiket untuk berbagai pertunjukan.

Saat membeli tiket, pengguna menunjukkan nomor teleponnya. Anda perlu menemukan acara dengan jumlah nomor telepon unik terbesar. Dan hitung jumlah nomor telepon unik yang cocok.

Format input

Log pembelian tersedia di fileticket_logs.csv. Kolom pertama berisi nama kinerja dari database layanan. Yang kedua - nomor telepon yang ditinggalkan pengguna saat membeli. Perhatikan bahwa demi konspirasi, kode negara telepon telah diganti dengan zona yang saat ini belum terlayani.

Format output

Jumlah nomor unik.

Keputusan

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

^{Memecahkan di Kontes}

Thearsipberisi tiga file teks:

qid_query.tsv - id kueri dan teks kueri, dipisahkan oleh tab;
qid_url_rating.tsv - id permintaan, URL dokumen, relevansi dokumen dengan permintaan;
hostid_url.tsv - id host dan url dokumen.

Teks permintaan harus ditampilkan dengan nilai maksimum metrik pFound, dihitung dari 10 dokumen teratas. Penerbitan atas permintaan dibentuk sesuai dengan aturan berikut:

Dari satu host hanya ada satu dokumen yang dipermasalahkan. Jika ada beberapa dokumen untuk permintaan dengan host id yang sama, dokumen yang paling relevan diambil (dan jika beberapa dokumen paling relevan, salah satu akan diambil).
Dokumen atas permintaan diurutkan dalam urutan relevansinya.
Jika beberapa dokumen dari host yang berbeda memiliki relevansi yang sama, urutannya dapat berubah-ubah.

Rumus untuk menghitung 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

Format keluaran

Teks permintaan dengan nilai metrik maksimum. Misalnya, untuk open_task.zip, jawaban yang benar adalah:

Keputusan

. - — 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. Turnamen olahraga

^{Selesaikan dalam Kontes}

Batas waktu ujian	2 dtk
Batas memori per tes	256 MB
Memasukkan	input standar atau input.txt
Keluaran	keluaran standar atau keluaran.txt

Saat Masha sedang berlibur, rekan-rekannya menyelenggarakan turnamen catur sesuai dengan sistem Olimpiade. Saat beristirahat, Masha tidak terlalu memperhatikan usaha ini, jadi dia hampir tidak ingat siapa yang bermain dengan siapa (tidak ada pertanyaan tentang urutan permainan). Tiba-tiba Masha mendapat ide bahwa alangkah baiknya membawa oleh-oleh untuk pemenang turnamen dari liburan. Masha tidak tahu siapa yang memenangkan pertandingan terakhir, tetapi dia dapat dengan mudah mengetahui siapa yang bermain di dalamnya, jika saja dia mengingat pasangan permainannya dengan benar. Bantu dia memeriksa apakah ini masalahnya dan mengidentifikasi calon pemenang.

Format masukan

Baris pertama berisi bilangan bulat 3 ≤ n ≤ 2 ¹⁶ - 1, n = 2 ^k - 1 - jumlah pertandingan sebelumnya. N baris berikutnya berisi dua nama keluarga pemain (dalam huruf kapital Latin) yang dipisahkan oleh spasi. Nama-nama pemainnya berbeda. Semua nama keluarga unik, tidak ada nama yang sama di antara rekan kerja.

Format input

Cetak "NO SOLUTION" (tanpa tanda kutip) jika Masha salah menghafal permainan dan tidak mungkin mendapatkan turnamen sesuai dengan sistem Olimpiade menggunakan grid ini. Jika grid turnamen dimungkinkan, cetak dua nama keluarga pada satu baris - nama kandidat untuk tempat pertama (urutannya tidak penting).

Contoh 1

Memasukkan	Keluaran
`7 GORBOVSKII ABALKIN SIKORSKI KAMMERER SIKORSKI GORBOVSKII BYKOV IURKOVSKII PRIVALOV BYKOV GORBOVSKII IURKOVSKII IURKOVSKII KIVRIN`	`IURKOVSKII GORBOVSKII`

Contoh 2

Memasukkan	Keluaran
`3 IVANOV PETROV PETROV BOSHIROV BOSHIROV IVANOV`	`NO SOLUTION`

Catatan Sistem

Olimpiade, juga dikenal sebagai playoff, adalah sistem organisasi kompetisi di mana seorang pesaing dieliminasi dari turnamen setelah kekalahan pertama. Anda dapat membaca lebih lanjut tentang sistem Olimpiade di Wikipedia .

Skema tes pertama dari kondisi:

Keputusan

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

Untuk mengatasi masalah trek kejuaraan lainnya, Anda perlu mendaftar di sini .

Di mana harus menyelesaikan tugas analitik dari tim Yandex? Kontes dan analisis

A. Hitung para pembohong di negara ini

B. Musim teater dan telepon

C. Menghitung pFound

D. Turnamen olahraga

More articles: