Работа: Бизнес аналитик стажер в Москве — Июль 2021 – 174 вакансии |

Работа: Бизнес аналитик стажер в Москве — Июль 2021 - 174 вакансии | Аналитика

Работа: бизнес аналитик стажер в москве — июль 2021 – 174 вакансии |

Решение

Найдём вероятность пересечения классическим подходом — поделим число маршрутов с пересечением на общее число возможных маршрутов. Пусть

— длина ребра квадратной сетки. Тогда общее число возможных маршрутов:

Вывод формулы описан

. А вот как узнать число маршрутов с пересечением реки для каждого

? Озадачившись этим вопросом, я решил взять несколько длин сетки поменьше, нарисовать поля и вручную подсчитать, сколько маршрутов пересекают реку, надеясь проследить зависимость (Очень рекомендую вам также сейчас взять листочек и ручку и поэкспериментировать с рисованием маленьких сеток и путей).

Пусть имеется сетка размером 3 на 3 клетки. Побочная диагональ сетки занята рекой, путник стоит в левом нижнем углу.

Как только я сделал рисунок, понял, что намного проще будет отследить маршруты, реку не пересекающие, а именно маршруты ниже реки. Затем можно будет умножить их число на 2, учтя таким образом и зеркальные маршруты выше реки. Так как мы знаем вдобавок и общее число маршрутов, найдём и количество пересекающих реку. Но вернёмся к главной задаче — нам нужна зависимость между $n$ и числом путей с переходом реки.На рисунке выше для случая 3×3 я отметил синим некоторые «сухопутные» маршруты, доступные путнику: отмеченные маршруты проходят по рёбрам клеток с горизонтальной координатой 2, на левые и верхние рёбра клеток раньше путник не заступает. Таких маршрутов 3, т. е. $n$. Теперь разберёмся с маршрутами, что проходят через клетку столбца 1.

Дополнительный анализ:  Аналитик назвал «честный» курс рубля: Рынки: Экономика:

Новые пути я отметил красным. Итак, понятно, что если путник свернёт на левое и затем верхнее ребро клетки (1, 0), ему далее будут доступны лишь 2 из трёх путей через клетки с горизонтальной координатой 2, ведь двигаться можно лишь вверх и вправо — третий же путь лежит ниже.

Возьмём сетку 4 на 4 и продолжим распутывать клубок. Стало понятно, что добавление новой клетки какого-либо столбца увеличивает число путей на то количество маршрутов, которое проходит через следующий столбец не ниже верхнего ребра добавленной клетки.


Крайний правый столбец вновь даёт нам

маршрутов. Верхнее ребро клетки (2, 0) добавит нам

маршрут. Верхнее ребро клетки (2, 1) добавит

маршрута. Верхнее ребро клетки (1, 0) добавит столько маршрутов, сколько добавили клетки (2, 0) и (2, 1) вместе. При желании можно нарисовать сетку побольше и продолжить считать маршруты тем же алгоритмом. Наша задача — подсчитать маршруты для сетки 100×100. Для этого можно написать программку, которая примет на вход

и построит матрицу

, начиная со столбца

и далее для каждой клетки предыдущих столбцов подсчитывая число добавленных клеткой путей, основываясь на данных предыдущего столбца. Таким образом, количество не пересекающих реку путей будет найдено.

Код
import numpy as np
import math

def routes_total(n): # Общее число путей
    return math.factorial(2*n) / (math.factorial(n)**2)

def fill_matrix(n): # Число путей, не пересекающих реку с одной стороны реки
    net = np.zeros((n, n)) 
    net[0, 0] = n # Крайний столбец даёт n путей
    for i in range(n-2):
        net[1, i] = n - i - 1 

    for i in range(2, n):
        for j in range(n - i - 1): 
            net[i, j] = 0
            for g in range(j, n - i   1):
                net[i, j]  = net[i - 1, g]
    
    # Сумму полученных чисел умножаем на 2, чтобы учесть другую сторону реки
    return (2 * sum(sum(net))) 

# Хотим долю пересекающих реку путей - вычитаем результат из 1
print(1  - fill_matrix(100) / routes_total(100))

Условие задачи


Государство Линейного Распределения представляет собой множество городов, некоторые из которых соединены дорогами.

Однажды королю Государства стало известно, что в его границы собирается вторгнуться Народ Точек Разрыва. Так как Государство не было готово к обороне, король принял нелёгкое решение — разделить Государство на много маленьких, каждое из которых будет самостоятельно защищать свои границы.

Было решено, что два города можно и нужно оставить в одном государстве, если из одного города можно будет добраться во второй, даже если Народ Точек Разрыва захватит одну дорогу между двумя любыми городами Государства Линейного Распределения. Во всех остальных случаях — города должны оказаться в разных государствах.

На каждой дороге, которая будет пересекать границу каких-либо двух новых государств, необходимо поставить бастион. Это нужно на случай, если одно из этих государств будет захвачено Народом Точек Разрыва. Тогда второе сможет продолжать оборонять свои границы. Иными словами, бастион будет поставлен на дороге, которая соединяет города из разных государств.

Король попросил вас дать ему список дорог, на которых необходимо поставить бастионы.

Формат ввода и вывода в программе
Формат ввода

Первая строка входного файла содержит два натуральных числа

$n$

и

$m$

— количества городов и дорог в Государстве Линейного Распределения соответственно.

$(1 leq n leq 20000, 1 leq m leq 200000)$

. Следующие m строк содержат описание дорог по одной строке. Дорога номер i описывается двумя натуральными числами

$b_i, e_i$

— номерами городов, которые эта дорога соединяет

$(1 leq b_i, e_i leq n)$

Формат вывода

Первая строка выходного файла должна содержать одно натуральное число b — количество дорог, на которых необходимо поставить бастионы. На следующей строке выводится b целых чисел — номера дорог, на которых будут установлены бастионы, по возрастанию. Дороги нумеруются с единицы в том порядке, в котором они заданы во входном файле.

Такие условия были даны изначально, в коде решения, который я приведу ниже, ввод производится с клавиатуры, а вывод — в консоль.

Формат ввода

Первая строка входного файла содержит два натуральных числа

— количества городов и дорог в Государстве Линейного Распределения соответственно.

. Следующие m строк содержат описание дорог по одной строке. Дорога номер i описывается двумя натуральными числами

— номерами городов, которые эта дорога соединяет

Заключение


Вот такие задачи должен уверенно решать претендующий на стажировку в Яндексе специалист. На приведённый выше набор заданий давалось 5 часов — довольно небольшой, по моему мнению, срок, но каждый работает в своём темпе.

Мои решения были проверены, и они дают корректные ответы, однако я не сомневаюсь, что есть и более эффективные способы справиться с предложенными задачами. Если вы готовы предложить более быстрое или более понятное решение или же нашли у меня ошибку — не стесняйтесь об этом написать.

Всем желаю найти себе позицию по душе!

Формат вывода

Первая строка выходного файла должна содержать одно натуральное число b — количество дорог, на которых необходимо поставить бастионы. На следующей строке выводится b целых чисел — номера дорог, на которых будут установлены бастионы, по возрастанию. Дороги нумеруются с единицы в том порядке, в котором они заданы во входном файле.

Такие условия были даны изначально, в коде решения, который я приведу ниже, ввод производится с клавиатуры, а вывод — в консоль.

Оцените статью
Аналитик-эксперт
Добавить комментарий