# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: 'Python 3.8.11 64-bit (''fns_hack'': conda)'
#     name: python3
# ---

# # Task C (Monte-Carlo solution)

# В селе Азино очень любят играть в азартные игры.
# Правила одной из игр таковы. Игрок 125 раз бросает игральную шестигранную кость. Из полученной последовательности выпавших чисел выбираются все максимальные по включению подотрезки, где каждое число ровно на 1 больше предыдущего. За каждый такой подотрезок игрок получает выигрыш, равный 
# 100⋅max(0,(L−2)), где L -- длина подотрезка.
# Какую наибольшую целочисленную цену игрок может заплатить за участие в такой игре, чтобы матожидание его прибыли было положительным?

# My first solution for the case that any first value of a die roll after the break of sequence belongs to a new sequence. Apparently, I got this condition wrong because the answer got 0 points despite robust results across many runs of simulations

import numpy as np
wins = []
for i in range(1000000):
    sample = np.random.choice(np.arange(1, 7), size=125)
    #print(sample)
    gains = []
    idx = 1
    curr = 1
    while idx < len(sample):
        if sample[idx] == sample[idx-1] + 1:
            curr += 1
        else: 
            gains.append(curr)
            curr = 1
        idx +=1
    #print(gains)
    money = list(map(lambda x: max(0, x-2), gains))
    wins.append(sum(money))
result = (np.array(wins) *100).mean()
print(result)

# A solution for the case when a first value after the break doesn't belong to the new sequence. The result is unstable (integer part alters between 27 and 28). As of now, I coudn't come up with an analytical solution for this problem.

import numpy as np
wins = []
for i in range(1000000):
    sample = np.random.choice(np.arange(1, 7), size=125)
    #print(sample)
    gains = []
    idx = 1
    curr = 0
    while idx < len(sample):
        if sample[idx] == sample[idx-1] + 1:
            curr += 1
        else: 
            gains.append(curr)
            curr = 0
        idx +=1
    #print(gains)
    money = list(map(lambda x: max(0, 100*x-200), gains))
    wins.append(sum(money))
result = np.array(wins).mean()
print(result)

# # Task D. Fraud in crowd-sourcing

# Одним из популярных способов разметки данных является краудсорсинг. Краудсорсинговые платформы, такие как Toloka, позволяют заказчикам размещать задания по разметке данных, а исполнителям выполнять эти задания за вознаграждение от заказчика.
#
# Довольно распространенный тип краудсорсинговых заданий — бинарная классификация изображений, где исполнителю нужно выбрать один из двух вариантов, например, указать, есть ли на картинке котик.
#
# Один из заказчиков решил использовать для борьбы с недобросовестными исполнителями (фродерами) механизм контрольных заданий. На каждую страницу с заданиями добавляется одно контрольное задание, для которого известен правильный ответ. Ответы исполнителя на такие задания сравниваются с эталонными, после чего исполнитель может быть заблокирован, если его ответы не будут соответствовать правилу контроля качества.
#
# Заказчик настроил следующее правило контроля качества:
# Если среди первых 10 ответов на контрольные задания более 30% неверных, исполнитель блокируется.
#
# Далее после каждых новых 5 контрольных ответов выбираются 10 последних контрольных ответов исполнителя, и если среди них более 30% неверных, исполнитель блокируется.
# В каждом задании заказчика можно дать один из двух ответов: «Да» или «Нет». Заказчик готовит набор из 100 контрольных заданий. Каждый раз, когда исполнителю нужно будет показать контрольное задание, оно будет случайно равновероятно выбираться из тех контрольных заданий, которые исполнитель еще не выполнял.
#
# Какое наибольшее число контрольных заданий с эталонным ответом «Да» может быть в подготовленном наборе контрольных заданий, чтобы фродер, всегда отвечающий «Да», с вероятностью не менее 80% был заблокирован после выполнения не более 25 контрольных заданий?

# Solution outline:
#
# Fraudster has to take 5 runs of the test. In every successive 10 tasks that a fraudster has to accomplish, he will fail if there are 3 or less positive examples (or, equivalently, 4 or more negative). I denote this probability of a failure as $P$. Then number of a run when he first fails follows geometric distribution $X \sim G_P$. Probability that he'll get caught during first 5 attempts is c.d.f. of X at 5. Thus, the following should hold:
#
# $F(5) = 1-(1-P)^5 \ge 0.8$
#
# or
#
# $1-P({he\ passed\ 10\ tasks})^5 \ge 0.8$
#
# $P({he\ passed\ 10\ tasks}) = P({there's\ at\ most\ 3\ negatives\ among\ 10\ tasks})= \frac{\sum_{i=0}^{3}{K \choose i}{100-K \choose  10-i}}{100 \choose 10}$,
#
# where K denotes number of negatives among all 100 samples. Now we just need to find such K, that $F_K \ge 0.8$ and $F_{K-1} < 0.8$. And value 100-K would correspond to maximum of positives in the sample.

from math import comb
# k is number of negatives
k=28
s = 0
for i in range(4):
    s += comb(k, i) * comb(100-k, 10-i)
# fail here means fail of a run of tests to identify the fraud.
p_fail = s / comb(100, 10)
p_success_all = 1 - p_fail ** 5
print(p_fail)
print(p_success_all)
print('max positives:', 100-k)

# And this is my first solution which had a mistake: I put 4 instead of 5 as a power in c.d.f calculation (it corresponds to another interpretation of geometric distribution r. v. that counts number of failures before the first success).

from math import comb
# k is number of negatives
k=30
s = 0
for i in range(4):
    s += comb(k, i) * comb(100-k, 10-i)
p_fail = s / comb(100, 10)
p_success_all = 1 - p_fail ** 4
print(p_fail)
print(p_success_all)
print('max positives:', 100-k)

# # Task E. Time of delivery

# Время ожидания заказа в Яндекс.Еде можно разложить на 4 составляющие:
# 1) время выполнения заказа в ресторане
# 2) время на поиск курьера для выполнения заказа
# 3) время на дорогу курьера до ресторана
# 4) время на дорогу курьера от ресторана до клиента.
#
# При этом:
# - задача 3) начинается сразу после задачи 2)
# - задача 4) начинается сразу после задачи 1) и 3)
# - задачи 1) и 2) начинаются одновременно.
#
# В упрощенной модели можно считать, что каждому этапу соответствует некоторое вероятностное распределение на время выполнения процесса в минутах, а именно:
# 1. равномерное распределение на [10;30]
# 2. равномерное распределение на [2;7]
# 3. равномерное распределение на [5;20]
# 4. равномерное распределение на [5;15].
#
# Какое минимальное время на доставку заказа стоит указывать Яндекс Еде, чтобы хотя бы 95% заказов выполнялись без опозданий? В ответ введите число, округленное до 3 знаков после десятичного разделителя.

# ## Outline of solution
# Denote time to deliver the order as Y
#
# $Y = X_4 + max(X_1;\  X_2+X_3)$
#
# Then we have to calculate c.d.f of p.d.f of Y incrementally, step by step. It's a long and tedious proccess involving Simpson's distrubution and some tricks.
#
# Resulting dictribution of $Z=max(X_1;\  X_2+X_3)$ part has several subintervals and behaves differently on them. But, it seemed to me that calculating convolution with $X_4$ only for the last subinterval $z \in [27;30]$ would be enough to get 0.95 percentile of final distribution. So I derived analitycal solution which yielded an answer:  $p_{0.95}=45-\sqrt{20}\approx 40.528$.
#
# The answer proved to be wrong apparently because value of Y=40.52 overlaps with penultimate subinterval of Z or due to a miscalculation.
#

import numpy as np
for _ in range(10):
    size = 100_000_000
    X1 = np.random.uniform(low=10, high=30, size=size)
    X2 = np.random.uniform(low=2, high=7, size=size)
    X3 = np.random.uniform(low=5, high=20, size=size)
    X4 = np.random.uniform(low=5, high=15, size=size)
    Y = X4 + np.max([X1, X2 + X3], axis=0)
    Y.sort()
    print(Y[int(0.95*size)])

# Quick Monte-Carlo simulation confirms that analytical derivation is not far off from the truth.

# # Task F. Analytics

# Участник чемпионата Yandex Cup за каждую решенную задачу получает 2 монеты, которые он может обменять на буквы из набора {А Н Л И Т К}. Цель каждого участника — не только победить, но и составить название одного из направлений — АНАЛИТИКА.
#
# За 1 монету участник может купить одну букву из набора {А Н Л И Т К}, при этом буквы выдаются независимо и равновероятно.
#
# Для решения задачи необходимо ответить на два вопроса и указать в поле ввода сумму ответов, округленную до 3 знаков после десятичного разделителя.
#
# Какое минимальное количество задач должен решить участник, чтобы вероятность собрать заветное слово АНАЛИТИКА была не менее 0.5?
# Какова вероятность собрать слово, если человек решит то количество задач, которое получилось в ответе на вопрос 1?

# I modeled occurences of each letter as a random vector following a multinomial distribution given multisets of n letters drawn out of alphabet with cardinality 6. For each n we need to count number of positive outcomes and multiply the result by $\frac{1}{6^n}$ (probability of each outcome).
#
# Since we know that at $n = 9$ we have a single positive outcome, we start investigating n=10, 11..., appending all combinations with replacement of n-9 letters to this initial outcome and evaluating if it's positive.

# +
from itertools import combinations_with_replacement
from copy import copy
from math import factorial
TRIES = 22
right = [3, 2, 1, 1, 1, 1]
goods = []
for comb in combinations_with_replacement(range(6), r=TRIES - 9):
    variant = copy(right)
    for i in comb:
        variant[i] += 1
    goods.append(variant)
#print(goods)
def perms(arr):
    n = sum(arr)
    result = factorial(n)
    for i in arr:
        result = result / factorial(i)
    return result
for i in goods: 
    if sum(i) != TRIES : print('wrong')
print(len(goods))
t_goods = [tuple(x) for x in goods]
#print(sorted(t_goods))
goods = list(set(t_goods))

print(len(set(t_goods)))
#print(goods)
answer = list(map(perms, goods))
print(sum(answer) / 6 ** TRIES) 


StarcoderdataJupyterScriptsDedupFiltered