Решил поднимать квалификацию в data science и машинном обучении, в ШАД экзамены в этом году я завалил, не успел приготовить математику, да и по программированию задачки попались сложные для меня, а вот в Академию больших данных от Mail.ru ещё есть шанс попасть. К тому же по отзывам учат там на убой. С небольшими накладками, но удалось решить 6 задач из 6 на экзамене по программированию, во многом благодаря тому, что дали по-сути безлимитное время. Публикую все мои решения, для тех кто не хочет ломать глаза о местную подсветку синтаксиса репозиторий здесь: https://github.com/holyketzer/ctci_v6/tree/master/python/made_2020
A. N-битовое разреженное число
N-битовое разреженное число — это число, в бинарной записи которого присутствует ровно N единиц - все остальные нули. Например число 137 — 3-битовое разреженное, потому что в двоичной системе записи выглядит как 10001001. Рассмотрим все 2-битовые разреженные числа, упорядоченные по возрастанию. Необходимо найти k-тое по порядку число в этой последовательности. Ответ необходимо дать по модулю числа 35184372089371 (остаток от деления на это число).
Очень долго думал над ней, переугорел (видимо после лекций Савватеева по математике), вывел адскую формулу через решение квадратного уравнения, чтобы считать количество знаков в разреженном числе в зависимости от его номера, в итоге получилось:
import math
import sys
n = int(sys.stdin.readline().strip())
def level(n):
return math.floor((math.sqrt(8*n + 1) - 1) / 2) + 1
for i in range(n):
ii = int(sys.stdin.readline().strip()) - 1
l = int(level(ii))
o = int(ii - (l * (l - 1) / 2))
x = '1' + '0' * (l - o - 1) + '1' + '0' * o
print(int(x, 2) % 35184372089371)
B. Беспилотные автобусы на Манхеттене
Правительство Нью-Йорка решило запустить в городе беспилотные автобусы. Было решено начать с Манхеттена и поручить Добрыне разработать маршрутную карту. Посмотрев на узкие улочки Манхеттена, Добрыня пришел к выводу, что не на каждом перекрестке автобусу хватит места, чтобы совершить поворот, поэтому первым делом Добрыня нашел все удобные для поворота перекрестки и обозначил их на карте. Также Добрыня решил, что для сокращения рисков нужно минимизировать количество поворотов на маршруте каждого автобуса. Учитывая, что улицы на Манхеттене образуют сетку, и места для разворота на 180º на перекрестках нет, остался единственный вариант формы маршрута --- прямоугольной. Придя к такому умозаключению, Добрыня задумался, а сколько вообще прямоугольных маршрутов через удобные перекрестки можно построить Помогите Добрыне ответить на этот вопрос.
Поначалу почитал условия и перешёл сразу к C, так как не особо люблю геометрию в такого рода задачах и субъективно решаю такие задачи хуже. Но после решения C посмотрел на статистику попыток решения в интерфейсе соревнования, которая красноречиво говорила, что B проще чем все следующие, ладно будем решать. Задача сводится к поиску правильных прямоугольников среди группы точек, немного подумав пришёл к алгоритму группировки точек по осям и поиску всех возможных комбинаций пары точек Y для пары точек X.
import math
import sys
from collections import defaultdict
import operator as op
from functools import reduce
def combination(n, r):
r = min(r, n-r)
numer = reduce(op.mul, range(n, n - r, -1), 1)
denom = reduce(op.mul, range(1, r + 1), 1)
return numer // denom
n = int(sys.stdin.readline().strip())
for i in range(n):
k = int(sys.stdin.readline().strip())
res = 0
points_by_x = defaultdict(set)
for j in range(k):
x, y = [int(i) for i in sys.stdin.readline().strip().split(' ')]
points_by_x[x].add(y)
xx = list(points_by_x.keys())
xx.sort()
for i, x in enumerate(xx):
for j in range(i + 1, len(xx)):
inter = points_by_x[x].intersection(points_by_x[xx[j]])
if len(inter) > 1:
res += combination(len(inter), 2)
print(res)
C. Казино Гальтона
Рулетка Гальтона представляет собой треугольную пирамиду с ячейками (см картинку ниже). На каждой ячейке написано число - стоимость этой ячейки. Сверху в самую первую ячейку кидают шарик. Шарик из текущей ячейки может равновероятно скатиться в одну из двух соседних ячеек уровнем ниже. Когда шарик скатывается на самый нижний уровень, подсчитывается сумма стоимостей всех ячеек, в которых побывал шарик. Эта сумма - выигрыш игрока в казино. Чтобы казино не разорилось, необходимо контролировать, чтобы средний выигрыш игрока не был слишком большим. Ваша задача - для данной рулетки Гальтона вычислить средний выигрыш игроке в ней (математическое ожидание). Ответ необходимо дать в виде несократимой дроби. Если средний выигрыш равен нулю, то ответом считается дробь 0/1.
Задача сводится к поиску всех возможных маршрутов шарика через пирамиду, и подсчёта очков на каждом из маршрутов, поначалу я пытался делать что-то рекурсивное, но потом понял что можно сделать через циклы если идти снизу вверх по пирамиде.
import copy
import math
import sys
def solve(arr, curr_sum = 0, level = 0, index = 0):
res = copy.deepcopy(arr)
last_index = len(res) - 1
for i in range(len(arr[last_index])):
res[last_index][i] = (arr[last_index][i], 1)
for row, line in reversed(list(enumerate(arr[0:-1]))):
for col, item in enumerate(line):
lsum, lcount = res[row + 1][col]
rsum, rcount = res[row + 1][col + 1]
res[row][col] = ((lcount + rcount) * arr[row][col] + lsum + rsum, lcount + rcount)
return res[0][0]
def truncate(n, m):
k = math.gcd(n ,m)
return n // k, m // k
n = int(sys.stdin.readline().strip())
for i in range(n):
h = int(sys.stdin.readline().strip())
arr = []
for j in range(h):
arr.append([int(i) for i in sys.stdin.readline().strip().split(' ')])
sum, count = solve(arr)
sum, count = truncate(sum, count)
print(sum, count)
D. Немножко сломанный HTML
Было замечено, что у разработчиков веб-сайтов очень частая ошибка - это случайное добавление одного лишнего тега в html документ, который делает его некорректным. В рамках кампании по улучшению качества разрабатываемого программного обеспечения, было принято решение о разработке программы для автоматического исправления подобного рода ошибок. HTML-документ - это последовательность открывающих и закрывающих тегов. Открывающий тег - это последовательность английских букв, обособленных треугольными скобками с двух сторон. Пример - . Закрывающий тег - это тоже самое, что и открывающих тег, но с дополнительным символом слеша после левой треугольной скобки. Пример - . Тег является закрывающим тегом к , если X = Y ( тогда - это открывающих тег для ). Все теги регистронезависимые - это означает, что и - это один и тот же тег. Каждый тег определяет элемент на странице. Элемент может быть пустой - это означает, что после открывающего тега элемента, сразу стоит закрывающий. Элементы могут быть вложенными друг в друга. Это означает, что между открывающим и закрывающим тегом находятся еще какое-то количество элементов. При этом для корректного документа должны выполняться следующие свойства: Для одного открывающего тега может быть ровно один закрывающий тег. Для одного закрывающего тега может быть ровно один открывающий тег. Элементы могут быть только строго вложенными друг в друга - перехлест элементов запрещен (например ). HTML-документ считается сломанным, если какое-то из этих свойств нарушается. Например, для данного тега не нашлось открывающего\закрывающего тега или существует перехлест в тегах. Для заданного HTML документа необходимо выяснить, является ли он сломанным или нет. Если документ является сломанным, то нужно узнать, не был ли он сломан случайно разработчиком (разработчик мог случайно добавить один лишний тег). То есть, если документ сломан, нужно проверить, можно ли его починить, удалив ровно один тег.
Эта задача сломала голову многим, в частности их-за небольшой ошибки в условиях (или скорее в тестах), так как в требованиям к формату вывода было написано выводить теги в верхнем регистре, а как позже выяснилось, тестовая система считала правильными ответы без преобразования регистра.
Вообще когда я брался за эту задачу, то времени оставалось уже около часа (из 4-х обещаных), а задачи оставалось ещё целых 3, и я не был уверен что успею решить хоть одну. После нескольких бесплодных попыток решения, я решил рискнуть и перешёл на F так как она казалась проще E (по количеству баллов). В итоге где-то в процессе решения F я обнаружил что время кончилось, но решения отправлять ещё можно, в MADE-чатике писали что-то про целые сутки, ну что ж халява, тогда решаем дальше!
В итоге решив все задачи, эту я дорешивал ещё очень долго и одна из моих попыток всё таки выбила 100 баллов на перепроверке через неделю, но во время экзамена у меня было 0 баллов, это ужасно деморализовало.
Я рассуждал так что если читать теги иди по порядку и отбрасывать корректно закрытые пары, и находить некорректные теги то задачу можно решить, но в итоге я умудрился найти кейс который некорректно работал на моём алгоритме и выдавал INVALID вместо ALMOST.
1 3 <B> <A> </B>
но я заметил если в случае INVALID для контроля прогнать этот алгоритм задом наперёд, то он находит ALMOST. На этом хрупком предположении я и строил своё решение, если до этого ничего кроме списка считаных тегов без пары в памяти хранить не приходилось, то здесь уже нужно было сохранить все теги, для этого я интернировал их и надеялся, что у меня не будет проблем на миллионе строк. В итоге это сработало.
import sys
def is_open_tag(tag):
return len(tag) > 1 and tag[0] == '<' and tag[1] != '/' and tag[-1] == '>'
def is_close_tag(tag):
return len(tag) > 1 and tag[1] == '/'
def convert_to_open_tag(tag):
return tag[0:1] + tag[2:]
def convert_to_close_tag(tag):
return tag[0:1] + '/' + tag[1:]
x = int(sys.stdin.readline().strip())
for i in range(x):
s = int(sys.stdin.readline().strip())
all_tags = []
tags = []
invalid_closes = []
for j in range(s):
tag = sys.intern(sys.stdin.readline().strip().upper())
all_tags.append(tag)
if is_open_tag(tag):
tags.append(tag)
else:
if len(tags) > 0 and tags[-1] == convert_to_open_tag(tag):
del tags[-1]
else:
invalid_closes.append(tag)
if len(tags) == 0 and len(invalid_closes) == 0:
print('CORRECT')
elif len(tags) + len(invalid_closes) == 1:
if len(tags) > 0:
print('ALMOST ' + tags[0])
else:
print('ALMOST ' + invalid_closes[0])
else:
tags = []
invalid_opens = []
for tag in reversed(all_tags):
if is_close_tag(tag):
tags.append(tag)
else:
if len(tags) > 0 and tags[-1] == convert_to_close_tag(tag):
del tags[-1]
else:
invalid_opens.append(tag)
if len(tags) == 0 and len(invalid_opens) == 0:
print('CORRECT')
elif len(tags) + len(invalid_opens) == 1:
if len(tags) > 0:
print('ALMOST ' + tags[0])
else:
print('ALMOST ' + invalid_opens[0])
else:
print('INCORRECT')
E. Обиженные пассажиры
В одной компании, предоставляющей услуги такси, решили раздать бонусы для повышения лояльности N пользователей с самыми большими суммарными опозданиями по вине компании за последний месяц. Для решения этой задачи необходимо проанализировать логи событий, связанных с заказами такси. Каждое событие в логах описывается одной строкой, содержащей несколько слов, разделенных пробельными символами (слово является непустой последовательностью строчных латинских букв, цифр, нижних подчеркиваний и дефисов). Первое слово в строке всегда определяет тип события. Всего есть 4 типа событий: ordered —событие заказа такси. Описывается словами 1.1. order_id (идентификатор заказа, строка), 1.2. user_id (идентификатор пользователя, строка), 1.3. ordered_at (время заказа в Unix time*, целое число), 1.4. X (ожидаемое время подачи машины в минутах, целое число), 1.5. Y (ожидаемая длительность поездки в минутах, целое число) arrived — машина подана пользователю. Описывается словами 2.1. order_id (идентификатор заказа, строка), 2.2. arrived_at (время подачи машины, в Unix time, целое число) started — пользователь сел в машине и началась поездка. Описывается словами order_id и started_at аналогично событию arrived. finished — поездка завершилась. Описывается словами order_id и finished_at аналогично событию started. момент времени в Unix time —это целое число секунд, прошедших с полуночи 1 января 1970 года. Считается, что пользователь опоздал, если поездка закончилась позже, чем ориентировочное время окончание поездки, рассчитанное исходя из предполагаемого времени подачи машины X, бесплатного времени ожидания K (измеряется в минутах) и предполагаемой длительности поездки Y. При этом важно учитывать только опоздания, произошедшие по вине компании: если пользователь не садился в машину дольше K минут после подачи, мы считаем его виноватым в своем опоздании, даже если сама поездка тоже оказалась дольше, чем прогнозировалось. Обратите внимание, что логи пишутся на разных компьютерах и сливаются в единое хранилище несинхронно, поэтому события никак не упорядочены.
Эту задачу я пытался решить последней, так как боялся больше всего, в итоге она мне показалась самой лёгкой, здесь вообще никаких хитрых алгоритмов, просто аккуратно прочитай и сагрегируй данные и посчитай ответ
import math
import sys
from collections import defaultdict
class Order:
def __init__(self, order_id):
self.order_id = order_id
self.user_id = None
self.ordered_at = None
self.x = None # X (ожидаемое время подачи машины в минутах, целое число),
self.y = None # Y (ожидаемая длительность поездки в минутах, целое число)
self.arrived_at = None
self.started_at = None
self.finished_at = None
def full(self):
return not(not(self.finished_at != None and self.started_at != None and self.arrived_at != None and self.ordered_at != None))
def late(self, k):
if self.started_at > self.arrived_at + (60 * k):
return 0
else:
return max(0, self.finished_at - (self.ordered_at + (60 * (self.x + self.y + k))))
def __repr__(self):
return self.__str__()
def __str__(self):
return str({
'order_id': self.order_id,
'user_id': self.user_id,
'ordered_at': self.ordered_at,
'x': self.x,
'y': self.y,
'arrived_at': self.arrived_at,
'started_at': self.started_at,
'finished_at': self.finished_at,
})
def find_or_add_order(orders, order_id):
if order_id in orders:
return orders[order_id]
else:
order = Order(order_id)
orders[order_id] = order
return order
x = int(sys.stdin.readline().strip())
for j in range(x):
e, n, k = [int(i) for i in sys.stdin.readline().strip().split(' ')]
# e - количество событий
# n - кол-во пользователей с самыми большими суммарными опозданиями по вине компании за последний месяц
# k - бесплатного времени ожидания K (измеряется в минутах)
orders = {}
for jj in range(e):
event, *params = sys.stdin.readline().strip().split(' ')
if event == 'ordered':
order_id, user_id, ordered_at, x, y = params
order = find_or_add_order(orders, order_id)
order.user_id = user_id
order.ordered_at = int(ordered_at)
order.x = int(x)
order.y = int(y)
elif event == 'arrived':
order_id, arrived_at = params
order = find_or_add_order(orders, order_id)
order.arrived_at = int(arrived_at)
elif event == 'started':
order_id, started_at = params
order = find_or_add_order(orders, order_id)
order.started_at = int(started_at)
elif event == 'finished':
order_id, finished_at = params
order = find_or_add_order(orders, order_id)
order.finished_at = int(finished_at)
else:
raise Exception("unexpected event type " + event)
users = defaultdict(list)
for order_id in orders.keys():
order = orders[order_id]
if order.full():
users[order.user_id].append(order)
lates = []
for user_id in users.keys():
total_late = 0
user_orders = users[user_id]
for order in user_orders:
total_late += order.late(k)
if total_late > 0:
lates.append((total_late, user_id))
lates = sorted(lates, key=lambda x: (-x[0], x[1]))
if len(lates) > 0:
print(' '.join(map(lambda pair: pair[1], lates[0:n])))
else:
print('-')
F. Продукты для застолья
Маруся организует застолье, и ей необходимо приготовить блюда для гостей, поэтому она составила меню: какие блюда и в каком количестве она собирается приготовить. Теперь ей необходимо обзавестись продуктами для готовки, поэтому Маруся составляет заказ в онлайн-магазине продуктов. К сожалению, в составленном ею меню слишком много блюд с замысловатыми рецептами, к тому же часть продуктов Маруся уже купила и сложила в холодильник, так что она совершенно запуталась. Вам необходимо помочь Марусе составить заказ. Маруся передала вам всю необходимую для этого информацию: Меню, в котором написан перечень из N блюд и их количеств. Кулинарная книга, в которой содержится K рецептов. i-й рецепт содержит R_i ингредиентов и в каком количестве они нужны. Обратите внимание, что одно блюдо может выступать как ингредиент для другого. Например, рецепты лазаньи и пасты болоньезе включают в себя соус болоньезе, для которого в книге содержится отдельный рецепт. Опись холодильника, содержащую перечень из F продуктов и их количества. Вам необходимо проанализировать эту информацию и составить заказ в магазине — список продуктов и их количество. Обратите внимание, что Маруся ненавидит полуфабрикаты, поэтому если для какого-то ингредиента есть рецепт в книге, то она его приготовит сама, и его не нужно покупать в магазине. Также можно быть уверенным, что в холодильнике Маруси нет таких полуфабрикатов.
Здесь хитрее, я предположил чтобы корректно решить её, надо использовать граф зависимостей, и на его основе определить порядок разбора блюд, сначала обрабатывать те которые состоят из простых ингредиентов, потом уже те которые из составных + кеш который содержит рецепты всех блюд выраженные в базовых ингредиентах, алгоритм построения графа зависимостей я нагуглил, чтобы долго не мучится.
С этой задачей я маленько попотел, проблема в том что моё решение падало с переполнением стека на рекурсии, насколько я понял, и всякие хитрости типа sys.setrecursionlimit(10000) не работали. Хотя возможно там возникал какой-то бесконечный цикл на хитром кейсе. В итоге немного переписав логику подсчёта для случая с базовыми ингредиентами мне удалось сдать и её.
import math
import sys
from collections import defaultdict
sys.setrecursionlimit(10000) # looks like it hadn't any effect
class Graph:
def __init__(self):
self.graph = defaultdict(list)
self.uniq_vertices = set()
# function to add an edge to graph
def add_edge(self, u, v):
self.graph[u].append(v)
self.uniq_vertices.add(v)
self.uniq_vertices.add(u)
def topological_sort(self):
# Create a vector to store indegrees of all
# vertices. Initialize all indegrees as 0.
in_degree = defaultdict(int)
# Traverse adjacency lists to fill indegrees of vertices. This step takes O(V + E) time
for i in self.graph:
for j in self.graph[i]:
in_degree[j] += 1
# Create an queue and enqueue all vertices with
# indegree 0
queue = []
for i in self.uniq_vertices:
if in_degree[i] == 0:
queue.append(i)
# Initialize count of visited vertices
cnt = 0
# Create a vector to store result (A topological
# ordering of the vertices)
top_order = []
# One by one dequeue vertices from queue and enqueue
# adjacents if indegree of adjacent becomes 0
while queue:
# Extract front of queue (or perform dequeue)
# and add it to topological order
u = queue.pop(0)
top_order.append(u)
# Iterate through all neighbouring nodes
# of dequeued node u and decrease their in-degree
# by 1
for i in self.graph[u]:
in_degree[i] -= 1
# If in-degree becomes zero, add it to queue
if in_degree[i] == 0:
queue.append(i)
cnt += 1
# Check if there was a cycle
if cnt != len(self.uniq_vertices):
raise Exception("There exists a cycle in the graph")
else :
# Print topological order
return top_order
def merge(res, res2):
for key in res2.keys():
res[key] += res2[key]
return res
def mult(res, count):
for item in res.keys():
res[item] *= count
return res
def count_for(dish, reciepts, cache):
if dish in cache:
return cache[dish].copy()
res = defaultdict(int)
if dish in reciepts:
reciept = reciepts[dish]
for item in reciept.keys():
if item in reciepts:
res = merge(res, mult(count_for(item, reciepts, cache), reciept[item]))
else:
res[item] += reciept[item]
cache[dish] = res.copy()
return res
else:
return { dish: 1 }
x = int(sys.stdin.readline().strip())
for i in range(x):
n, k, f = [int(i) for i in sys.stdin.readline().strip().split(' ')]
cache = {}
dishes = {}
graph = Graph()
for ii in range(n):
dish, count = sys.stdin.readline().strip().split(' ')
dishes[dish] = int(count)
reciepts = {}
for ii in range(k):
dish, r = sys.stdin.readline().strip().split(' ')
r = int(r)
reciept = {}
for ri in range(r):
ingidient, amount = sys.stdin.readline().strip().split(' ')
reciept[ingidient] = int(amount)
graph.add_edge(ingidient, dish)
reciepts[dish] = reciept
fridge = {}
for ii in range(f):
ingidient, amount = sys.stdin.readline().strip().split(' ')
fridge[ingidient] = int(amount)
order = defaultdict(int)
ordered_dish_list = graph.topological_sort()
for dish in ordered_dish_list:
if dish in dishes:
sub_res = count_for(dish, reciepts, cache)
mult(sub_res, dishes[dish])
order = merge(order, sub_res)
else:
count_for(dish, reciepts, cache)
for item in order.keys():
if item in fridge:
order[item] = order[item] - fridge[item]
items = list(order.keys())
items.sort()
for item in items:
if order[item] > 0:
print(item, order[item])
В итоге в в рамках 4 часов мне бы удалось решить лишь 3 первых задачи, но щедрость и доброта организаторов не знает границ )
Кстати это был первый раз когда используя Питон на экзамене я чувствовал себя достаточно комфортно, я бы даже сказал мне понравилось, когда уже знаешь всякие идиоматические штучки типа defaultdict (по началу вообще не мог понять как питонисты живут без нашего родного Hash.new { |h, k| h[k] = <what ever you want> }), или как работает сортировка tuple-ов в Питоне (спасибо собесу Яндекса), то жизнь становится значительно лучше.
В математике я никогда не был силён, и хоть типа «решил» 7 задач, но если из них будет 2-3 верных решения, то это уже достижение. По ML умудрился набрать 166 баллов, так что думаю шансы поступить есть.