Яндекс алгоритм задачи: Алгоритм. Примеры задач

Алгоритм. Примеры задач

---

A. Время в зазеркалье

Отправить решение задачи на платформе Яндекс.Контест

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

В офисе, где работает Бомбослав, установлены стильные дизайнерские часы. Их циферблат имеет стандартную разметку: на окружности расположены 60 делений, соответствующих минутам, 12 из которых (начиная с расположенного вверх от центра окружности, далее равномерно с шагом в пять делений) сделаны крупнее остальных, то есть соответствуют часам. Стильными эти часы делает тот факт, что циферблат не содержит никаких цифр, так как предполагается, что всем хорошо известно, какое деление соответствует какому значению текущего времени.

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

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

Формат ввода

В единственной строке входных данных записаны два целых числа h и m(0≤h≤11, 0≤m≤59) — положение часовой стрелки и положение минутной стрелки в отражённом циферблате соответственно. h=0 означает, что часовая стрелка указывает вертикально вверх, h=3 соответствуют стрелке, направленной строго направо, h=6 — стрелка смотрит вертикально вниз, h=9 — строго налево. Аналогичные указания верны для минутной стрелки для значений m=0, m=15, m=30и m=45

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

Выведите два целых числа x и y(0≤x≤11, 0≤y≤59) — реальное значение текущего времени на часах.

Пример 1

Пример 2

Примечания

На картинке изображён первый тестовый пример. Левый циферблат соответствует тому, что видит Бомбослав, а правый — реальному положению стрелок. Часовая стрелка изображена красным цветом, а минутная синим.

Решение

Решение

Рассмотрим движение «прямой» и «отражённой» стрелки. За то время, которое «прямая» стрелка повернётся на некоторый угол, «отражённая» повернётся на тот же угол, но в другую сторону, то есть суммарный угол поворота стрелок равен полному обороту. Для каждой стрелки независимо вычислим её позицию. Для часовой это 12 минус текущая позиция, а для минутной — 60 минус текущая позиция. В обоих случая надо не забыть заменить 12 или 60 на ноль.

B. Фактор палиндромности

Отправить решение задачи на платформе Яндекс.Контест

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

Аркадий — большой фанат использования машинного обучения в любой задаче. Он верит в безграничную силу волшебства этой популярной молодой науки. Именно поэтому Аркадий постоянно придумывает всё новые и новые факторы, которые можно вычислить для различных объектов.

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

Формат ввода

В единственной строке входных данных записана одна строка из базы Аркадия — непустая последовательность строчных букв английского алфавита. Длина строки составляет не менее 2 и не превосходит 200 000 символов.

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

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

Пример 1

Пример 2

Примечания

Говорят, что строка a=a1a2 … an) лексикографически меньше строки b=b1b2 … bm) если верно одно из двух условий:

• либо nm и a1=b1, a2=b2,  …, an=bn,  то есть первая строка является префиксом второй;
• либо есть такая позиция 1≤i≤min(n,m), что a1=b1, a2=b2 …, ai-1=bi-1 и ai=bi,  то есть, в первой позиции, в которой строки различаются, в первой строке стоит меньшая буква.

Решение

Решение

Пусть существует какая-то подстрока, являющаяся палиндромом. Если мы уберём первый и последний символ палиндрома, оставшаяся строка тоже будет палиндромом. Будем повторять процесс до тех пор, пока не останется строка из двух или трёх букв (в зависимости от чётности).

Подстрок длины два или три всегда линейное количество, и суммарная их длина также линейна, поэтому среди таких строк ответ можно выбрать наивным алгоритмом. Если же ни одна из подстрок такой длины не является палиндромом, то выведем -1.

C. Разделите их все

Отправить решение задачи на платформе Яндекс.Контест

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

После работы Оля и Толя решили вместе сходить в тир. После прохождения вводного инструктажа и получения оружия они оказались на позициях для стрельбы, а напротив них находятся n мишеней. Все мишени можно считать фигурами, нанесёнными на бесконечную плоскость, при этом каждая мишень является кругом или прямоугольником, мишени могут накладываться и пересекаться произвольным образом.

Перед тем как начать стрельбу, Оля и Толя хотят убедиться, что они смогут однозначно идентифицировать результаты своих выстрелов.

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

Формат ввода

В первой строке входных данных записано целое число n(1≤n≤100 000) — количество мишеней. Каждая из последующих n строк содержит целое число ti(0≤ti≤1),  обозначающее тип мишени. Если ti=0,  то мишень является кругом и далее следуют три целых числа ri, xi и yi,  определяющие радиус и координаты центра круга соответственно (1≤ri≤1000, −10 000≤xi, yi≤10 000) Если же ti=1,  то мишень является прямоугольником, который затем определяют восемь целых чисел x1,i, y1,i, x2,i, y2,i, x3,i, y3,i, x4,i, y4,i — координаты всех четырёх вершин (−10 000≤xj,i, yj,i≤10 000),  перечисленных в порядке обхода по часовой стрелке или против часовой стрелки. Гарантируется, что данные четыре вершины образуют прямоугольник ненулевой площади.

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

Если существует прямая, которая поделит каждый из имеющихся кругов и прямоугольников на две части одинаковой площади, выведите “Yes”. В противном случае выведите “No”.

Пример 1

Пример 2

Пример 3

Решение

Решение

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

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

Если среди построенного множества точек не более двух различных, то ответ точно положительный. В противном случае рассмотрим любую пару различных точек и проверим, что все остальные точки лежат на определяемой этой парой прямой. Наиболее удобный способ проверить, что три точки a, b и c (a≠b) лежат на одной прямой ~— использовать векторное произведение векторов b-a и c-a.  Итоговая сложность решения: O(n). 

D. Задача для собеседования

Отправить решение задачи на платформе Яндекс.Контест

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

Алексей регулярно проводит собеседования с кандидатами на позицию стажёра. И хотя он провёл уже не одну сотню собеседований, в последнее время этот процесс даётся ему нелегко — кандидаты стали без труда решать все годами протестированные и отработанные задачи Алексея!

Делать нечего, и в преддверии очередного собеседования Алексей придумал новую задачу. Имеется числовая последовательность, на первом шаге состоящая из двух чисел 1. На каждом следующем шаге между каждыми двумя соседними элементами добавляется новый элемент, равный их сумме. После первых нескольких шагов последовательность выглядит следующим образом:

• 1 1
• 1 2 1
• 1 3 2 3 1
• 1 4 3 5 2 5 3 4 1

На собеседовании Алексей хочет попросить кандидата написать программу, которая по заданному числу n будет определять, сколько раз число n будет встречаться в последовательности на n-м шаге? Алексей ещё не научился решать свою задачу, но слышал, что кандидат, с которым он сейчас будет проводить собеседование, добился высоких результатов в спортивном программировании, поэтому, скорее всего, легко справится с этим вопросом.

Формат ввода

Во входных данных записано единственное число n(1≤n≤1013). 

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

Выведите одно целое число, равное количеству вхождений числа n в описанную в условиях последовательность на шаге n.

Пример 1

Пример 2

Решение

Решение

Докажем несколько лемм.

Лемма 1. Числа, оказавшиеся на каком-то шаге соседними, являются взаимно простыми.

Докажем по индукции. База очевидна (1 и 1 взаимно просты). Пусть доказано для n шагов. Все числа, выписанные на n+1 -м шаге, являются суммой двух соседних на n-м шаге чисел, то есть суммой двух взаимно простых чисел. Но НОД (a+b, b)=НОД (a, b)=1.  Лемма доказана.

Лемма 2. Никакая упорядоченная пара соседних чисел (a, b) не может возникнуть в последовательности более одного раза (ни на одном шаге, ни на разных).

Пусть это не так, тогда отметим номер k шага, на котором в первый раз возникло повторение (то есть повторилась пара, существующая на этом или на предыдущем шаге). Пусть пара (p, q) возникла на k-м и на i≤k -м шаге. Но тогда, если p>q , то p было построено как сумма соседей q и p-q (если pq , то q было построено как сумма p и q-p ), то есть на k-1 -м и на i-1-м шагах также существовало повторение, что противоречит нашему предположению. Лемма доказана.

Лемма 3. Любая упорядоченная пара взаимно простых чисел неизбежно будет соседней на некотором шаге.

Пусть мы имеем числа pq, стоящие рядом на некотором шаге и пусть p>q (без ограничения общности). Тогда p было получено как сумма p-q+q , то есть на предыдущем шаге рядом стояли p-q и q. Если p-qq , то два шага назад справа от q стояло число 2q-p , если p-q>q , то слева от p-q стояло число p-2q и так далее. Так как p и q взаимно просты, то на каком-то шаге этот процесс, по сути являющийся разновидностью алгоритма Евклида, приведёт к тому, что с одной стороны окажется 1, а с другой — некоторое натуральное число. Но пара (1, x) или (x, 1) для любого x будет соседней последовательности на x-м шаге. А так как действия восстанавливаются однозначно, то это значит, что и исходная пара (p, q) в какой-то момент встретится в качестве соседней.

Таким образом, каждая упорядоченная пара взаимно простых чисел ровно один раз встречается в качестве соседей в заданной последовательности. Поэтому задача сводится к подсчёту количества упорядоченных пар взаимно простых чисел, дающих в сумме n. Так как если p и n взаимно просты, то и p и (n-p взаимно просты, то количество таких пар можно поставить в однозначное соответствие количеству чисел, взаимно простых с n, или значению функции Эйлера от n.

Подсчёт же количества таких чисел является известной задачей и опирается на мультипликативность функции Эйлера: если n=p1k1·p2k2· … ·pnkn , то взаимно простых с n чисел будет (p1k1-p1k1-1)·(p2k2-p2k2-1)· … (pnkn-pnkn-1) Раскладываем n на простые множители за время O(n) .

E. Резервное копирование

Отправить решение задачи на платформе Яндекс.Контест

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

Для обеспечения сохранности пользовательских данных Аркадий постоянно изобретает и тестирует новые схемы организации резервного копирования. В этот раз он пронумеровал все имеющиеся у него компьютеры с данными от 1 до n и для каждого компьютера с номером от 1 до n-1 назначил резервный компьютер pi При этом он строго соблюдал правило, что номер компьютера для резервного копирования всегда больше номера самого компьютера, то есть pi>i . По этой причине у компьютера с номером n компьютера для резервного копирования нет.

В ходе текущего эксперимента Аркадий выбрал некоторую конфигурацию значений pi и будет последовательно отключать компьютеры по одному каждую секунду. Эксперимент заканчивается, когда Аркадий отключает компьютер с номером n. Изначально на каждом компьютере находится некоторый блок данных размера 1. При отключении компьютера с номером x изначально расположенный на нём блок данных размера 1 передаётся на компьютер с номером px , при этом, если на компьютере номер x находились другие блоки данных (полученные от других компьютеров при их отключении), то они исчезают. Если же компьютер px уже отключен, то и блок данных с компьютера x никуда не передаётся и тоже исчезает.

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

Формат ввода

В первой строке входных данных записано целое число t(1≤t≤20) — количество тестовых примеров.

Далее следует t описаний тестовых примеров, каждое описание начинается со строки содержащей два целых числа n и k(1≤n≤100 000, 2≤k≤10) — количество компьютеров, участвующих в эксперименте и предельное количество блоков данных на одном компьютере соответственно. Вторая строка содержит n-1 число p1, p2, … pn-1(i+1≤pi≤n) .

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

Для каждого из t тестовых примеров выведите одно целое число — максимально возможную продолжительность эксперимента, то есть максимальный номер секунды, на которой Аркадий может отключить компьютер с номером n.

Пример

Решение

Решение

В задаче нам дано корневое дерево, на каждом шагу одна из вершин дерева удаляется. При этом, если корень вершины ещё не был удалён, его значение увеличивается на 1 (изначально все значения равны 1). Если значение какой-то вершины становится равным k, то именно она удаляется на следующем шаге. Требуется максимизировать номер шага на котором будет удалена корневая вершина.

Заметим, что если у корневой вершины менее k-1 потомка, то можно удалить все вершины дерева, перед тем как трогать вершину номер n. В противном случае все дети корня разделяются на три множества: те, чьи поддеревья будут удалены полностью, те, у которых корень останется нетронутым, и одно поддерево, после удаления корня которого мы удаляем и саму вершину n. Сделаем обход в глубину нашего дерева и будем поддерживать три значения динамического программирования:

a(v) равняется количеству вершин, которые можно удалить в данном поддереве, если можно удалить вершину v и не обязательно последней. Несложно заметить, что a(v) равняется размеру поддерева.

b(v) равняется количеству вершин, которые можно удалить в данном поддереве, если вершина v должна остаться нетронутой. Равняется a(v)-1 , если у вершины v менее k-1 сына. В противном случае нужно выбрать каких-то k-2 потомка, для которых будет использовано значение a(u) и для всех остальных использовать b(u) . В качестве таких k-2 потомков выгодно взять вершины с максимальной разницей a(u)-b(u) .

c(v) равняется количеству вершин, которые можно удалить в данном поддереве, если можно удалить вершину v, но она должна быть последней удалённой вершиной поддерева. Величина c(n) и будет являться ответом на задачу. Требуется выбрать какие-то k-2 потомка, для которых будет использовано значение a(u) , одного потомка, для которого мы используем c(u) и для всех остальных к ответу добавится b(u) . Переберём, для какого из потомков будет использовано c(u) (то есть кто будет последним удалённым потомком, после чего будет удалена и вершина v). Теперь среди оставшихся требуется взять сумму всех значений b(u) и k-2 максимальных a(u)-b(u) . Для этого достаточно иметь предподсчитанными сумму всех b(u) и список сыновей, упорядоченных по a(u)-b(u) . Если вершина x, для которой мы решили взять значение c(x) попадает в вершины с максимальной разностью, то использовать следующую k-1 вершину (такая обязательно есть, иначе мы просто уничтожаем всё поддерево).

Итоговая сложность решения O(n log n)

F. Процессоры-лжецы

Отправить решение задачи на платформе Яндекс.Контест

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

Для испытания новых алгоритмов машинного обучения Евгений использует n·m процессоров, расположенных в единичных клетках платы размера n×m . Таким образом, процессоры занимают n рядов, по m процессоров в каждом. При этом два процессора считаются соседними, если они расположены в соседних клетках одного ряда, или на одной и той же позиции в соседних рядах.

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

Теперь перед Евгением стоит задача определить, какие из процессоров постоянно выдают неверную информацию, но сначала он хочет оценить масштаб проблемы. Для этого он послал каждому из процессоров вопрос: верно ли, что среди соседних ему процессоров есть и исправные процессоры, и процессоры-лжецы? На удивление Евгения, все процессоры ответили на такой запрос утвердительно.

Теперь он хочет узнать, какое минимальное количество процессоров-лжецов может находится на плате?

Формат ввода

В единственной строке входных данных записаны два целых числа n и m(1≤n≤7, 1≤m≤100) — количество рядов в плате и количество процессоров в одном ряду соответственно.

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

Выведите одно целое число — минимальное возможное количество процессоров-лжецов на плате, при котором каждый процессор мог сообщить Евгению, что среди его соседей есть и исправные процессоры и процессоры-лжецы.

Пример 1

Пример 2

Примечания

Одним из возможных решений в первом тесте является (испорченные процессоры отмечены как 1):
100
001

Решение

Решение

Воспользуемся тем фактом, что n≤7 и будем вычислять динамику по профилю. Пусть мы заполнили первых i столбцов таблицы, причём на первых i-1 столбце все процессоры вернули ожидаемый результат. Тогда, для того чтобы продолжить заполнять таблицу нам важно лишь знать, какие из процессоров врут среди последних двух столбцов.

Посчитаем dp(i, m1, m2) , где i меняется от 1 до m, а m1 и m2~— битовые маски от 0 до 2n-1 . Значением динамики будет минимальное количество процессоров-лжецов, которое потребуется, чтобы заполнить первые i столбцов так, чтобы среди первых i-1 столбца все процессоры вернули ожидаемый результат, а состояние процессоров в последнем и предпоследнем столбце были равны m1 и m2 соответственно. Всего различных состояний O(m·22n) . Наконец, для вычисления перехода будет перебирать новую маску m3 и пробовать перейти в состояние dp(i+1, m2, m3) .

Работая с масками с помощью предподсчёта и битовых операций получим результат O(m·23n) . Работу программы можно значительно ускорить, если предпосчитать все корректные переходы их каждой пары масок (m1, m2) (то есть запомнить все подходящие к ним маски m3 ).

Упражнение: придумайте, как получить решение за время O(nm22n) .

Разбор квалификационного раунда Яндекс.Алгоритм 2017 — Алгоритм 2017

Этот раунд был подготовлен разработчиками минского офиса Яндекса.

Рассмотрим решение, которое работает с квадратичной асимптотикой. Для этого будем действовать в соответствии с условием задачи: заведем счетчик последней закрытой задачи, будем проходить по списку задач от начала до конца, увеличивая счетчик, когда проходим через элемент массива задач, соответствующий следующей задаче. Из-за достаточно больших ограничений это решение не укладывается по времени.

Рассмотрим, в каком случае, мы уже не найдем никакой подходящей задачи до конца списка. Оказывается, только в том случае, когда после закрытия задачи с номером x следующая задача с номером (x+1) расположена ближе к началу списка. Следовательно, для решения задачи нужно по каждому номеру задачи узнать ее позицию в списке задач, а затем подсчитать количество различных номеров x таких, что позиция задачи с номером (x+1) меньше, чем позиция задачи с номером x.

К найденному количеству нужно добавить первый проход по списку задач. Итоговая трудоемкость алгоритма .

Задача “Междугороднее общение” не содержит особой алгоритмической идеи, поэтому нужно аккуратно реализовать описанное в условии задачи поведение системы бронирования.

Мы можем зафиксировать число от 0 до 23 (час, в который будем проверять возможность организации встречи). После этого в каждом из городов нужно проверить наличие свободной переговорки.

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

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

Первое решение основано на подсчете количества раз, сколько раз тест с номером x будет запущен. В исходной системе каждой тест запускается один раз, а в новой системе 2^d(x), где d(x) расстояние от корневого тест до теста с номером x. Это утверждение несложно доказывается методом математический индукции, также заметить этот факт можно было внимательно изучив описание тестовых примеров из условия. Для подсчете d(x) достаточно обойти дерево любым обходом.

Второй метод решения основан на динамическом программировании. Пусть T(x) равно суммарному времени работы теста с номером x, т.е. времени работы тестов, от которых он зависит, и времени проверки a_x. Запишем соотношение:

Для вычисления ответа T(1) также достаточно одного обхода дерева (в данном случае DFS).

Трудоемкость решения задачи .

Сразу следует рассмотреть такую задачу: на какое количество слагаемых можно разбить число n, если все слагаемые должны быть степенями двойки с целыми неотрицательными степенями. Покажем, что для любого целого k от popcount(n) до n это возможно (где popcount(n) это количество установленных бит в двоичной записи n).

Очевидно, что нельзя использовать меньшее чем popcount(n) число слагаемых, и большее n. Если у нас есть разложение в x слагаемых (x < n), то среди них есть слагаемое 2^t с положительной степенью t. Его мы можем заменить на два слагаемых 2^t-1, получив разложение с (x+1) слагаемым. Разложение из popcount(n) слагаемых строится из двоичного представления числа.

Для решения задачи будет перебирать длину последовательности k (k ≥ 1), пока не найдем подходящее. Как показано выше, нужно найти минимальное k, что popcount(kn) ≤ k, а после этого построить требуемое разложение. Для ограничений задачи k не превосходит 60 (60 ⋅ (2⁵⁰ — 1) < 2⁶⁰ — 1 = 2⁰ + 2¹ + … + 2⁵⁹).

Требуется чтобы в графе соединений не было мостов, следовательно степень всех вершин не менее двух. А так как сумма степеней всех вершин равна 2 ⋅ n + 2, то у нас возможны два случая:

• есть одна вершина степени 4;
• есть две вершины степени 3.

Рассмотрим первый случай. Граф представляет собой объединение двух циклов длины (m + 1) и (n — m) с общей вершиной. В этом случае нам нужно выбрать какие вершины попадут в первый цикл (остальные попадут во второй), и в каком порядке вершины окажутся на этих циклах. Общая формула имеет следующий вид

Рассмотрим второй случай. В графе есть две вершины степени три, которые соединены между собой цепочками ребер, на которых расположены все остальные (n-2) вершины. Сразу обратим внимание, что соединение с нулем дополнительных вершин (ребро) может быть только одно. Пусть на соединениях расположены a, b и c вершины (a ≤ b ≤ c). Рассмотрим несколько случаев:

• 0 ≤ a < b < c, тогда количество соединений равно C(n-2, a) C(n — 2 — a, b) ;
• 0 < a = b < c, тогда количество соединений равно C(n-2, a) C(n — 2 — a, b) ;
• 0 ≤ a < b = c, тогда количество соединений равно C(n-2, a) C(n — 2 — a, b) ;
• 0 < a = b = c, тогда количество соединений равно C(n-2, a) C(n — 2 — a, b) .

Собирая все формулы вместе, получаем итоговый результат.

Для решения этой задачи обратимся к строковой терминологии. Бордером строки s называется какая строка y, что x начинается и заканчивается на y.

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

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

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

Следовательно, для полного решения задачи нам осталось научиться проверять, есть ли дополнительное вхождение максимального по длине бордера (длины ). Чтобы такое вхождение было, должна найтись позиция j (j < i), в которой . Для быстрой проверки такого неравенства достаточно хранить префиксный максимум значений префикс-функции.

Трудоемкость решения задачи линейная от длины текста.

Как проходят алгоритмические секции на собеседованиях в Яндекс

Алгоритмическая секция с написанием кода на доске или бумаге — один из важнейших этапов собеседования разработчиков для получения работы в Яндексе. Мы решили подробнее рассказать о том, как устроены эти секции, чтобы помочь будущим кандидатам в подготовке. Кроме того, надеюсь, многие из тех, кто не решается прийти в Яндекс на собеседование, опасаясь слишком сложных испытаний, после этого рассказа поймут, что в действительности всё не так уж и страшно!

Так что мы подготовили для вас следующие материалы:

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

Как мы собеседуем разработчиков

Собеседование любого разработчика состоит из нескольких этапов:

• предварительная секция с рекрутером;
• техническое скайп-интервью;
• несколько очных секций;
• финальные интервью с нанимающими менеджерами.

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

Очные секции — основной этап. Именно очные секции дают ответ на вопрос о том, что умеет кандидат. Алгоритмическая секция — одна из очных технических секций. Помимо алгоритмических, бывают и другие очные испытания: скажем, кандидаты в старшие разработчики обязательно проходят секцию по архитектуре, а будущие руководители ещё и отвечают на вопросы по управлению командами и проектами. Вообще, если у кандидата есть какая-то сильная сторона в специфической области (машинном обучении, низкоуровневой оптимизации, разработке высоконагруженных систем, мобильной разработке или любой другой) — мы обязательно организуем секцию с профильным специалистом.

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

Зачем писать код на доске или бумаге

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

Первое из них — умение быстро разбираться с работоспособностью кода «на глаз». Представьте себе, что при написании каждого цикла, возникающего в программе, разработчику требуется потратить время на то, чтобы проверить его работоспособность трассировкой; или что при падении сервиса в продакшене ему всегда обязательно нужно запустить код под дебаггером. Ясно, что написание и отладка даже несложных программ будут занимать у него непозволительно много времени. Конечно, полезно уметь читать код и при код-ревью.

Второе важное свойство — способность заранее продумывать план решения и затем следовать ему. Если плана нет, это будет приводить к большому количеству исправлений, зачёркиваний (на бумаге) и переписыванию больших кусков кода. В реальной жизни всё это сильно замедляет разработку, но отчасти маскируется скоростью работы в редакторе кода. Доска и бумага в этом смысле являются беспощадными поверхностями.

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

Алгоритмические секции и спортивное программирование

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

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

Контест для подготовки к собеседованию

Специально для того, чтобы вы могли примерно представить себе содержание задач, которые мы даём на алгоритмических секциях, мы собрали контест, который можно использовать при подготовке к собеседованиям. Попробуйте решить все задачи, ни разу не запустив дебаггер; написать решение в Notepad’е без подсветки синтаксиса; придумать как можно более короткое решение, которые пройдёт все тесты; продумать все возможные проблемы заранее и сдать решение с первого раза.

Контест содержит пять задач. Вы можете попробовать решить их самостоятельно, а можете заранее прочитать разбор: это всё равно будет полезно, т.к. вы сможете потренировать свой навык безошибочного кодирования заранее известного алгоритма.

Разбор задач контеста

Задача A. Камни и украшения

Даны две строки строчных латинских символов: строка J и строка S. Символы, входящие в строку J, — «драгоценности», входящие в строку S — «камни». Нужно определить, какое количество символов из S одновременно являются «драгоценностями». Проще говоря, нужно проверить, какое количество символов из S входит в J.

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

Алгоритм достаточно простой: из строки с «драгоценностями» необходимо построить множество, затем пройтись по строке с «камнями» и каждый символ проверить на вхождение в это множество. Используйте такую реализацию множества, чтобы гарантировать линейную сложность полученного решения, несмотря на то, что входные строки очень короткие и поэтому возможно сдать даже квадратичный по сложности алгоритм.

Задача B. Последовательно идущие единицы

Требуется найти в бинарном векторе самую длинную последовательность единиц и вывести её длину.

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

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

Постарайтесь использовать лишь константный объём дополнительной памяти.

Задача C. Удаление дубликатов

Дан упорядоченный по неубыванию массив целых 32-разрядных чисел. Требуется удалить из него все повторения.

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

При решении этой задачи также не нужно использовать дополнительную память.

Задача D. Генерация скобочных последовательностей

Дано целое число . Требуется вывести все правильные скобочные последовательности длины , упорядоченные лексикографически (см. https://ru.wikipedia.org/wiki/Лексикографический_порядок). В задаче используются только круглые скобки.

Это пример относительно сложной алгоритмической задачи. Будем генерировать последовательность по одному символу; в каждый момент мы можем к текущей последовательности приписать либо открывающую скобку, либо закрывающую. Открывающую скобку можно дописать, если до этого было добавлено менее n открывающих скобок, а закрывающую — если в текущей последовательности количество открывающих скобок превосходит количество закрывающих. Такой алгоритм при аккуратной реализации автоматически гарантирует лексикографический порядок в ответе; работает за время, пропорциональное произведению количества элементов в ответе на n; при этом требует линейное количество дополнительной памяти.

Примером неэффективного алгоритма был бы следующий: сгенерируем все возможные скобочные последовательности, а затем выведем лишь те из них, что окажутся правильными. При этом объём ответа не позволит решить задачу быстрее, чем тот алгоритм, что приведёт выше.

Задача E. Анаграммы

Эта достаточно простая задача — типичный пример задачи, для решения которой необходимо использовать ассоциативные массивы. При решении нужно учитывать, что символы могут повторяться, поэтому необходимо использовать не множества, а словари. Поэтому решение будет следующим: составим из каждой строки по словарю, который для каждого символа будет хранить количество его повторений; затем сравним получившиеся словари. Если они совпадают, необходимо вывести единицу, в противном случае — ноль.

Альтернативное решение: отсортируем входные строки, а затем сравним их. Это решение хуже в том, что оно работает медленнее, а также меняет входные данные. Зато такое решение не использует дополнительной памяти.

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

Задача F. Слияние сортированных списков

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

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

В этой задаче многие испытывают сложности с форматом ввода. Обратите внимание на то, что первые элементы строк не описывают элементы массивов, они описывают длины массивов!

FAQ по контесту

A: Я точно написал правильный код, но тесты не проходят; наверное, в них ошибка?
Q: Нет, все тесты правильные. Подумайте: вероятно, вы не предусмотрели какую-нибудь необычную ситуацию.

A: Я пишу на языке X, ему точно требуется больше памяти в задаче Y. Поднимите лимиты!
Q: Все лимиты выставлены таким образом, что решение возможно с использованием любого из доступных языков. Попробуйте проверить, не зачитываете ли вы случайно входной файл целиком в задачах со строгими лимитами по используемой памяти.

A: Некоторые задачи можно решить намного проще из-за указанных ограничениях. Зачем вы так?
Q: Мы специально упростили ввод в некоторых задачах, чтобы участникам было проще сосредоточиться на реализации алгоритма и не думать, например, о скорости загрузки данных или каких-то других вещах, важных в спортивном программировании. Постарайтесь реализовать именно те алгоритмы, которые мы рекомендуем — только в такой ситуации вы получите от контеста максимальную пользу.

A: Не хочу проходить контест. Можно я не буду?
Q: Конечно! Контест не является обязательным к решению всеми кандидатами. Впрочем, я всё равно рекомендую его порешать: это в любом случае будет полезно.

A: Что ещё посоветуете для подготовки?
Q: Прочитайте наши советы на официальной странице про собеседования в Яндекс: https://yandex.ru/jobs/ya-interview. От себя добавлю, что решение задачек на leetcode.com является крайне полезным для любого практикующего разработчика, независимо от того, планирует ли он в ближайшее время проходить интервью или участвовать в соревнованиях по программированию. Даже небольшое количество практики позволяет почувствовать себя увереннее при решении рабочих задач.

Заключение

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

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

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

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

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

Вы проводите алгоритмические секции для разработчиков всех специальностей?
Да. Алгоритмические секции проводятся для бекенд-разработчиков, аналитиков, мобильных и фронтенд-разработчиков, разработчиков инфраструктуры и методов машинного обучения, и так далее.

ШАД, Алгоритмы и структуры данных | by Vyacheslav Khorkov

Начало обучения было запланировано на сентябрь 2017 года, и у меня было около двух месяцев на подготовку. Может показаться странным, а зачем готовиться к обучению? Курс Алгоритмы и Структуры Данных предполагает, что студент уже знает базовые алгоритмы и структуры данных, а также “много разной математики”. Но это явно не про меня.

Также мне заранее сказали, что скорее всего вся практика будет сдаваться на языке программирования C++. Я немного изучал язык С на первом курсе университета лет 10 назад, а из С++ знал только cin и cout. Этого явно было достаточно, чтобы успешно завалить этот курс.

Я решил начать свою подготовку с общих теоретических знаний и выбрал для этого книгу “Алгоритмы” Санджой Дасгупта, Христос Пападимитриу, Умеш Вазирани. Не только потому, что мне понравились фамилии авторов, но и по рекомендациям это была самая простая книга об алгоритмах. Я бегло прочитал её за неделю. Книга оказалась очень полезной по разным причинам. К примеру, на меня снизошло прозрение в операциях по модулю.

Затем я начал смотреть различные видеолекции, в частности и старые лекции ШАД на YouTube. На это ушло много времени, я часто пересматривал одно и тоже пытаясь понять хоть что-то. Хочу признаться, это было очень тяжело. Чувствовалась нехватка знаний. Со временем я понял — пора переходить к практике так как я стал забывать, что смотрел в самом начале.

В качестве практики я решил разобрать и написать простые структуры данных и алгоритмы на Swift. Мне очень помог Swift Algorithm Club. Для мотивации я решил каждый день что-то выкладывать на Github в свой репозиторий специально созданный для этих целей.

Активность в августе

После этого я наткнулся на статью на Habrahabr и понял, что курс “Основы разработки на C++: белый пояс” мне идеально подходит. Курс рассчитан на 5 недель, но у меня было только две. Этого оказалось вполне достаточно, если ударно учиться по выходным и после работы.

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

В середине сентября я пошел на первый семинар в университет. Пропуска у меня еще не было и я кое-как объяснил охраннику что я пришел учиться в школу. Мне нужно было попасть в аудиторию 611. Я заблудился, и начал всех спрашивать как пройти. Мне попадались студенты, которые или не говорят на русском или говорили мне — это на 6 этаже. Но я то уже пробовал подниматься на самый верх и знал, что в этом здании всего 4 этажа…

С горем пополам я нашел нужную аудиторию. Вторым моим удивлением стало то, что в ней было около 50 человек и казалось что все уже знали друг друга, кроме меня. Позже я понял, что этот курс преподается не только для студентов ШАД, но и для магистрантов МатМеха. На последние семинары приходило всего человек 10.

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

Также рассказали сколько балов нужно получить на зачет/хорошо/отлично. Что балы дают в основном за решение задач и рассказ решения на семинаре у доски. Также очень важны review-задачи.

По началу было очень сложно, но я затрайхардил.

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

Основной язык на котором нужно было сдавать был С++. Система тестирования также жёстко проверяла стиль кода. Нельзя было использовать однобуквенные переменные, даже в циклах. Никаких using namespace std, ограничения на ширину строк, пробелы вместо табуляции и тп. На каждую задачу прогонялось около 100 тестов, которые были закрыты. Система сообщает только номер проваленного теста.

Задачи условно можно поделить на три типа. Offline задачи — когда ваше решение практически не проверяется до окончания срока сдачи, и только после этого прогоняются все тесты без возможности внести исправления. Review задачи — когда код проверяется преподавателем, а также возможно необходимо описать алгоритм в уже объявленном интерфейсе с различными особенностями C++. И простые задачи, которые можно было отправлять на тестирование до 100 попыток.

Решение прошло 91 из 100 тестов поэтому вы получаете …… 0 балов

В целом на каждую задачу я тратил около 10 часов, ближе к концу я справлялся по шустрее. Конечно всё зависит от конкретной задачи, но в целом почти все они были довольно сложными (для меня). В эти часы я также включаю просмотр видео и разбор теории. Семинары это ещё минус 3–4 часа свободного времени в неделю, если учитывать дорогу.

Так как я iOS разработчик все задачи я решал в Xcode. На мой взгляд это бесконечно удобная среда разработки, в которой приятно писать любой код (и почти не падает, да).

Я пересмотрел огромное количество лекций ШАД за разные годы, видео на YouTube из различных летних школ, зарубежных институтов (Princeton, Massachusetts, Harvard, etc.), и вот этого замечательного парня. В совокупности всё оказалось очень полезным.

Для написание теории в PDF я выбрал приложение Bear. Ограничений на формат не было, главное описать алгоритм, сложность и объяснить что он конечен и корректен. А в Bear просто приятно делать заметки.

Отрывок теории в PDF.

Я не пропустил ни одного семинара. К сожалению, один семинар совпал с iOSParty, но таинственным образом преподаватель его отменил. В конце семестра я даже пару раз объяснял решения задач у доски с мелом, как настоящий школьник.

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

Когда я не смог вовремя решить одну из задач мне было очень интересно узнать как её решили другие. Я почти бегом бежал на семинар и всё равно умудрился опоздать как раз на 10–15 минут, за которые и была рассказана моя задача. Очень порадовало, что преподаватель просто взял и объяснил мне её после занятия. Правда я всё равно не понял. Ничего. Позже я разобрался с ней дома.

Надеюсь это не послужит спойлером для будущих студентов.

В итоге я смог решить 21 задачу из 24. Сдал 3 review и написал 21 PDF с теорией. Были ещё дополнительные небольшие задачи и одна очень сложная задача, которую не решал никто и мы её даже не разбирали. Этого с не плохим запасом хватило на отлично.

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

Хочется заметить, что ШАД это школа только по своим размерам. На самом деле учиться в ней приходится исключительно самостоятельно, иначе вы обречены на провал. В практических задачах часто требуется фантазия чтобы увидеть определенную структуру или алгоритм. Это не просто задачи по типу “Напишите сортировку”, как я изначально ожидал. Было действительно сложно и мне всё понравилось.

Очень частый вопрос: “А тебе это всё пригодиться хотя бы?”. В моей работе скорее всего нет, это маловероятно. Я считаю, что это основы которые просто полезно знать любому программисту. Computer Science, расширение кругозора и всё вот это. Сейчас я перетаскиваю кнопки в iOS, а чем захочу заниматься в будущем неизвестно.

Это конец первого семестра, а я отправляюсь на второй) Обещали графы для взрослых. Не уверен, что смогу уделять также много времени и в целом потяну обучение. Я обязательно поделюсь новыми впечатлениями о втором семестре уже этим летом! Но, это не точно.

Открытый чемпионат «Яндекс.Алгоритм» выиграл 18-летний белорус — Российская газета

Триумфом белорусской и российской школ программирования завершился в Петербурге финал открытого чемпионата «Яндекс. Алгоритм».

Из более чем трех тысяч участников чемпионата, представлявших 84 государства, до финала добрались 25 человек из 9 стран: России, Беларуси, Украины, Польши, Китая. Тайваня, Южной Кореи, Словакии и Германии. Беларусь представляли двое: выпускник Белорусского госуниверситета нынешнего года Андрей Малевич и 18-летний уроженец Гомеля Геннадий Короткевич.

С полным правом участниками состязаний можно назвать еще и минчан Романа Удовиченко и Алексея Толстикова, с той лишь разницей, что они задачи не решали, а составляли их.

Собрались сильнейшие программисты в одном из самых красивых зданий Северной столицы — во Дворце Великого князя Владимира Александровича, что соседствует на Дворцовой набережной с Эрмитажем. Организаторы решили подарить праздник и участникам, и гостям чемпионата, частью которого, несомненно, стало пребывание в стенах общепризнанного архитектурного шедевра ХIХ века.

— Это наш первый полноценный чемпионат, с участниками со всего мира, с солидным призовым фондом, — рассказал «СОЮЗу» один из руководителей Яндекса Михаил Левин. — Турнир мы проводили в Доме ученых — с надеждой на то, что кто-то из побывавших здесь нынче программистов со временем станет настоящим академиком в своем деле…

Финальная игра включала шесть задач, которые требовалось решить за строго определенное время -100 минут. На мировом студенческом чемпионате, для сравнения, для этого отводилось пять часов. При этом там, на чемпионате мира, трудилась команда из трех человек, здесь же каждый был один на один с хитроумными заданиями.

Еще одно отличие двух этих турниров — возраст участников. У нынешнего никаких ограничений не было. А что такое возраст в программировании? Опыт! Отсюда и более острое соперничество. Изучаешь список финалистов, и буквально каждый второй в нем — чемпион или призер мирового первенства. Например, Ю Вон Сок из Южной Кореи впервые завоевал это звание еще в 1997 году, когда иные его нынешние соперники только родились. Словак Михал Форишек — в 1998 году. Поляк Павел Порыс — в 2001-м…

Один из составителей задач, 27-летний минчанин Алексей Толстиков, рассказал «СОЮЗу», каково оно вообще — готовить такого рода математические «упражнения». Алексей, к слову, окончив несколько лет назад БГУ, остался там преподавателем кафедры вычислительной математики.

— Создание компьютерной задачи — процесс достаточно трудоемкий, может занять немало времени, — признался Алексей. — От нескольких часов до несколько суток. Тут важна еще и оригинальность идеи. Разного рода турниров среди программистов в мире проходит сейчас достаточно много. Нельзя повторяться. Я работал вместе с Ромой Удовиченко, он окончил наш университет в нынешнем году, в июле стал серебряным призером мирового студенческого чемпионата, получил предложение работать в минском офисе Yandex. Начало успешной карьере, на мой взгляд, положено. Из шести задач для данного финала в Петербурге — две наши с ним. Остальные составляли коллеги из России, Японии, Польши.

— Белорусские программисты не первый год входят в число сильнейших в мире. На ваш взгляд, что этому способствует?

— У нас сильная математическая школа еще с советских времен, она не только сохранила свои традиции, но и развивает их. Во многих городах Беларуси действуют клубы программистов для детей, работают увлеченные своим делом преподаватели. При этом нет необходимости беспокоиться о том, где потом применить свои знания. У добившихся определенных результатов молодых программистов проблемы с трудоустройством практически не существует. Пример? Андрей Малевич. Будучи еще студентом БГУ, он получил предложение работать в США, в Facebook.

На финале чемпионата в Петербурге Андрей считался одним из фаворитов. Несмотря на молодость, ему нет и 25, успел заявить о себе стабильно успешными выступлениями на престижных турнирах. Слово «стабильно» тут ключевое. В программировании важно регулярно показывать высокие результаты.

На этот раз ему, правда, не удалось пробиться в тройку призеров. Совсем немного он уступил многоопытному Ши Бисюнь из Тайваня. В Петербурге Ши Бисюнь, решив три задачи, стал бронзовым призером. «Серебро» у россиянина Евгения Капуна — также три задачи в активе. А победителем стал, как многие и ожидали, Геннадий Короткевич. Он тоже решил три из шести задач. Но с меньшим, чем у основных соперников штрафом.

— Этот чемпионат требовал большой скорости в решении, — сказал после награждения победитель. — В принципе я доволен результатами, хотя мог бы выступить лучше, если бы был чуть быстрее. Мог бы решить четыре задачи. Главные соперники для меня всегда — именно задачи, а не другие участники…

О Геннадии «СОЮЗ» уже рассказывал. Он обратил на себя внимание специалистов еще в школьные годы. Участник и победитель многих турниров. В прошлом году поступил в Петербурге в Национальный исследовательский университет. С ним связывают надежды специалисты России и Беларуси. Сам он о своем будущем предпочитает не распространяться. Вообще не слишком словоохотлив. С алгоритмами, похоже, ему найти язык гораздо проще.

Основная миссия Яндекса – помогать пользователям решать задачи

Основная миссия Яндекса – помогать пользователям решать задачи

Вчера на РИФ.Кавказ состоялась секция «Яндекс.Новости. Эпоха новостных агрегаторов».

«Основная миссия Яндекса – помогать пользователям решать задачи. А для решения разных задач используются разные виды данных. Для обработки каждого из них нужны свои алгоритмы. Алгоритмы Яндекс-Новостей – специализированный поиск для обработки новостных сообщений. Для новостного сообщения важные такие характеристики, как текст, время публикации и источник. Таким образом, алгоритм, который обрабатывает новостные сообщения, должен быстро понимать, о чем эта новость, оценить ее свежесть и важность»

 – заявила Ирина Халлилулина, заместитель руководителя «Яндекс.Новости».

Она также рассказала о том, что когда на нескольких ресурсах появляется информация об одном событии, специальный алгоритм объединяет их и создает «сюжет». В топ-5 Яндекса попадают новости, опубликованные в большом количестве источников.

«Специализированное ранжирование помогает понять, каким событиям СМИ уделяют наибольшее внимание и как они эти события оценивают»

 – добавила Ирина Халлилулина.

«Издания предоставляют нам свой контент, мы его обрабатываем, структурируем, на основании чего делаем определенные продукты. Пользователи, приходя к нам, получают первичную информацию о событиях и уходят на сайты изданий, становясь их читателями»

 – сообщила она.

В рамках данной секции Руководитель Управления по информационной политике администрации Главы и Правительства РД Зубайру Зубайруев заявил, что на данный семинар были приглашены представители пресс-служб министерств и ведомств, а также муниципалитетов и региональных СМИ.

«Яндекс дает возможность продвигать информацию не только за пределы республики, но также найти большое количество читателей внутри Дагестана»

 – заявил Зубайру Зубайруев.

Он также отметил, что на данный момент почти все ведомства Республики стали партнерами Яндекса. И добавил, что необходимо пресс-службам органов исполнительной власти региона работать в единой связке, совместно продвигая положительную информацию, чтобы она попала в том «Яндекса».

«Для этого я вам предлагаю писать сразу две уникальные новости – одну для своего сайта, другую – для РИА “Дагестан”. Потому что ваша задача – доставить информацию до более широкой аудитории»

 – порекомендовал он.

Своим советом поделился и Директор РИА «Дагестан» Магомед Магомедов. Он порекомендовал также забывать о федеральных новостях. По его словам, если своевременно выдать информацию, способную заинтересовать читателя, то можно выйти в федеральный топ «Яндекса».

 

 

Яндекс раскрыл алгоритм формирования быстрых ответов и проговорился про description

Для ряда поисковых запросов наличие страниц в поисковой выдаче не требуется.

Yandex раскрыл алгоритм формирования фактовых ответов, а еще проговорился про формирование description.

Как поисковая система формирует быстрые ответы?

Рассмотрим тему далее.

1 — Колдунщики Яндекса. Что это?

Что такое колдунщики Яндекса? Колдунщики — это элементы поисковой выдачи, которые отвечают на поисковый запрос прямо на странице с результатами поиска. Это может быть прогноз погоды, картинка, перевод слова и многое другое. В результате пользователь проводит быстрый поиск, и в большинстве из случаев не посещает сайты.

Пример колдунщика в поисковой выдаче:

В поисковой выдаче Google есть блоки с подобными ответами.

Еще поисковые системы совершенствуются, переходят от поиска по ключевым фразам к поиску по смыслам (алгоритм BERT).

В результате поисковые системы монополизируют трафик. Рекомендованный материал в блоге MegaIndex на тему монополизации трафика по ссылке далее — Аналитические данные о поисковой выдаче Google, которые могут изменить планы на продвижение.

На языке инженеров такие блоки называются блоками с фактовыми ответами.

Как такие блоки формируются, чем различаются и что важного произошло в этой области за последнее время?

2 — Алгоритм Fact Snippet. Как формируются фактовые ответы

Сначала были имплементированы блоки без интерактивных функций, то есть блоки без взаимодействий. Например:

Ответы на подобные запросы встречаются в поисковой выдаче с высокой частотой. В результате многие сайты потеряли трафик. Например, поисковый запрос:

мой ip адрес

Раньше трафик забирал 2ip. Теперь трафик забрал Yandex.

Рассмотрим детали. Весь процесс создания таких блоков в поисковой системе выглядел так:

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

Затем система получила еще ряд улучшений.

Был разработан алгоритм Fact Snippet. Сначала алгоритм должен был использовать текст из description. Имеется ввиду текст, который генерируется алгоритмом поисковой системы вне зависимости от фактического description. Но информативное описание страницы не во всех случаях является прямым ответом на вопрос.

Поэтому в Яндекс сделали так. Сначала нейросетевая модель была обучена на уже известных ответах. Затем происходит так — нейросетевая модель строит векторы ответов для найденных в поиске страниц и сравнивает их с вектором запроса.

Большинству запросов не требуется фактовый ответ. Поэтому в Yandex улучшили алгоритм для отсева нефактовых запросов. Задача была решена.

Дальше в Yandex поставили задачу по выходу за пределы фактов. Появился алгоритм Fact Snippet 2.

Пример ответа в поисковой выдаче:

Если упростить, то Fact Snippet 2.0 — это тот же Fact Snippet, но без требования найти исчерпывающий ответ.

В Fact Snippet 2.0 адаптированы оба этапа так, чтобы находить ответы на более широкий срез вопросов.

Такие ответы не претендуют на энциклопедическую полноту, но всё равно полезны. Иногда хорошие ответы есть в иных источниках. Например, на картах. К примеру, зачем предлагать адрес организации текстом, если можно показать интерактивную карту, номер телефона и отзывы. Проблему решает блендерный классификатор.

В результате еще больше ключевых фраз охвачены. В поисковой выдаче еще больше быстрых ответов. Но нет предела желанию монополизировать трафик. Алгоритм еще улучшили.

Переформулировки запросов. Часть поисковых запросов остались не охвачены. Существенная доля — таких ключевых фраз является переформулировками уже известных фраз. Например:

в какое время зубы меняет щука

и

когда щука меняет зубы

Данную задачу решает механизм поиска алиасов. Работает так:

• Берутся все запросы, на которые есть ответы;
• Преобразуются в векторы и кладутся в индекс k-NN. Применяется оптимизированная версия индекса HNSW, которая позволяет искать быстрее;
• Строятся векторы запросов, на которые нет ответа по прямому совпадению;
• Ищется топ N наиболее похожих запросов в k-NN;
• Далее топ прогоняется через катбустовый классификатор тройки: запрос пользователя, запрос из k-NN, ответ на запрос из k-NN;
• Если вердикт классификатора положительный — запрос считается алиасом запроса из k-NN, поисковая система может вернуть уже известный ответ.

Главная задача заключается в написании факторов классификатора. Самые сильные:

• Векторы запросов;
• Расстояния Левенштейна;
• Пословные эмбеддинги;
• Факторы на основе разнообразных колдунщиков по каждому из запросов;
• Расстояние между словами запросов.

Кстати определить смысловую близость запросов можно и другими способами. Например, если два запроса отличаются друг от друга одним словом, то как вариант можно проверить, как отличаются результаты поиска по этим запросам (посмотреть на число совпадающих ссылок в топе).

В быстром режиме искать алиасы не просто из-за ограничений по техническим ресурсам, потому применяют BERT. Сделали так:

• Собрали BERT-моделью очень много (сотни миллионов) искусственных оценок;
• Обучили на них более простую нейронную сеть DSSM, которая очень быстро работает в рантайме.

В результате с некоторой потерей точности удалось получить сильный фактор.

3 — Нейросуммаризация поиска. Сайты больше будут не нужны

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

Интересный нюанс

В ходе разбора работы алгоритма фактовых ответов Яндекс рассказал про формирование текста для сниппетов страниц. Поисковая система способна автоматически создавать текст для сниппета.

Как создается текст? Алгоритм ищет лучший фрагмент текста на странице. Применяется модель CatBoost, которая оценивает близость фрагмента текста и запроса.

По сути алгоритм нацелен на то, чтобы выдать в тексте сниппета фактический ответ.

Здесь открывается поле для манипуляций. Значение для сниппета задается через description. Например, для сайта indexoid:

Но прописывать значение для description является необязательным условием для индексации страницы.

В результате поисковой есть вариант:

• Создать группы страниц без описания. Например, копии страниц лидеров поиска;


• Выявить какой именно фрагмент текста является лучшим ответом на ключевую фразу;
• Применить полученные данные в текстовой оптимизации страниц сайта.

Еще пример:

• Создать группы страниц без описания. Например, группы страниц на одну тему, но с разным текстом;
• Выявить какой именно фрагмент текста является лучшим ответом на ключевую фразу;
• Применить полученные данные в текстовой оптимизации страниц сайта.

По сути, поисковый алгоритм сравнивает два вектора: вектор запроса и вектор текста документа.

Чем ближе векторы в многомерном пространстве, тем ближе смыслы текстов по данным поисковой системы.

Выводы

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

В поисковой системе Google двигаются аналогичным образом. Рекомендованный материал в блоге MegaIndex на тему поиска по смыслу по ссылке далее — ГУГЛ БЕРТ.

Fact Snippet работает в два этапа. В Fact Snippet 2 принцип подобный, но есть нюансы. Этапы в Fact Snippet следующие:

• На первом этапе с помощью лёгкой модели оценивается фактовость запроса, иными словами проверяется фактовый ответ или нет;
• Если да, ответ выводится в поисковой выдаче.

Для Fact Snippet 2.0 адаптированы оба этапа так, чтобы искать решение по более широкому срезу вопросов. Такие ответы не претендуют на энциклопедическую полноту, но всё равно полезны.

Сниппеты сайтов влияют на кликовые факторы.

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

Ссылка на сервис — Анализ сниппетов.

Что вы думаете о тенденциях? Какие шаги предпринимаете? Напишите в комментариях.

Все решено — Чемпионат Яндекс.Алгоритм по программированию отмечает победителей в Берлине — блог компании Яндекс

Ежегодный чемпионат Яндекса по программированию «Яндекс.Алгоритм» выявил своих победителей. Победителем стал Геннадий Короткевич из Беларуси (в настоящее время студент Санкт-Петербургского университета ИТМО) с четырьмя решениями из возможных шести и -66 минут штрафного времени. Он получил свои заслуженные 300 000 рублей (около 6 000 евро из общего призового фонда в 10 800 евро) — второй раз подряд он стал обладателем гран-при Яндекса.Алгоритм.

Казухиро Хосака (Токийский университет, Япония) также решил четыре задачи, но со штрафным временем -90 минут, и получил 150 000 рублей (около 3 000 евро) призового фонда и второе место. А студент Циньши Ван из Университета Цинхуа (Пекин, Китай) забрал оставшиеся 90 000 (1800 евро), решив четыре задачи со штрафным временем -125 минут и заняв третье место.

Финальный раунд Яндекс.Алгоритма прошел 1 августа в отеле Radisson Blu SAS в Берлине, рядом с недавно открывшимся R&D офисом Яндекса в столице Германии.

Начав в 2011 году всего с нескольких программистов, тренирующих свои алгоритмические мускулы в специальном мероприятии, организованном Летней школой Яндекса, в этом году Яндекс.Алгоритм увидел, что 3890 участников из 72 стран борются за место в финале. Удача, подкрепленная талантом и мастерством, была на стороне 25 участников из Беларуси, Казахстана, Украины, России, Польши, Китая, Тайваня, Японии и США, вышедших в финал.

Конкуренция в финале, как и ожидалось, была жесткой, и некоторые из сильнейших игроков мира в соревновательном программировании показали, чего они стоят по сравнению с предыдущим Яндексом.Победители алгоритмов, а также многократные чемпионы других известных международных чемпионатов, в том числе ACM ICPC и TopCoder Open, а также практические компьютерные инженеры, работающие в Facebook и Google. Сотрудники Яндекса исключаются из участия в соответствии с условиями конкурса.

Все задачи конкурса, включая шесть алгоритмических задач в финальном раунде, были разработаны командой профессиональных компьютерных инженеров и активных конкурентоспособных программистов из Университета Карнеги-Меллона, МГУ, Санкт-Петербург.Петербургский государственный университет, Google и Яндекс. Здесь вы можете увидеть проблемы и решения. Специалисты Яндекса, участвовавшие в конкурсе, не только имеют практический опыт решения задач, аналогичных тем, которые представлены в конкурсе, но и делятся своими знаниями со студентами Школы анализа данных Яндекса.

Школа анализа данных Яндекса — это бесплатная магистерская программа по информатике и анализу данных, предлагаемая Яндексом выпускникам инженерных, математических, компьютерных или смежных специальностей.С момента основания в 2007 году школу окончили триста двадцать два студента. Школа анализа данных, штаб-квартира которой находится в Москве, в Яндексе, является партнером ведущих исследовательских центров и имеет филиалы в других городах России, Украины и Беларуси.

Анализ онлайн-раунда 1 Яндекс.Алгоритма

В первом онлайн-раунде конкурса Яндекс.Алгоритм 609 участников представили хотя бы одно решение и 396 представили хотя бы одно правильное решение. Задачи Non-Squares и Kingdom Division были довольно простыми, и обе дали примерно 300 правильных ответов.Задача Stacks of Coins была относительно простой и была решена 145 участниками. Остальные три задачи оказались сложнее. Наклейки могли быть очень сложной проблемой со строкой, но небольшой размер ввода позволил использовать решение динамического программирования, которое 22 участника правильно поняли. Помощники решали 13 участников; требовался бинарный поиск, жадность и некоторые базовые структуры данных, чтобы уложиться в срок. Во время конкурса никто не смог решить State Roads , что было аккуратной теоретико-графической задачей с простой кодировкой, но довольно сложной задачей. хитрое решение.

Поздравляем Kenny_HORROR, который был единственным, кто решил пять задач, и Petr, tourist и eatmore, которые решили четыре задачи и с отрицательным штрафным временем также вышли в финальный раунд.

Набор задач этого раунда был предоставлен вам польской командой: Томаш Идзиашек ( Дивизия Королевства ), Якуб Лецкий ( Государственные дороги ), Марцин Пилипчук ( Помощники ) и Якуб Радошевский ( Не- Квадраты , стопки монет ).Особая благодарность профессору Костасу Илиопулосу за идею проблемы Наклейки .

Решения, данные испытаний и анализ были подготовлены marek.cygan, monsoon и jakubr.

Задача A (Помощники)

В этой задаче нам нужно найти минимальное количество дней, за которое можно выполнить n исследовательских задач. Задача i может быть выполнена профессором с использованием p _i дней подряд или может быть делегирована ассистенту, который выполнит ее с использованием a _i дней подряд.Каждый привлеченный ассистент может выполнить только одно задание, а профессору нужен один день, чтобы найти такого ассистента.

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

Легко видеть, что существует оптимальный график, в котором профессор сначала ищет помощников, а затем выполняет неназначенные задачи. Более того, это означает, что нам не нужно беспокоиться о том, выполняет ли профессор свои задачи в течение последовательных дней.Формально говоря, если существует оптимальный график, в котором профессор назначает задачи ассистентам, а он выполняет оставшиеся задачи (но не обязательно в последовательные дни), то существует оптимальный график, в котором профессор делегирует задачи из T во время сначала # T дней, а затем он выполняет оставшиеся задачи (каждую задачу в последовательные дни). Следовательно, если профессор делегирует задачи из T , то он завершит оставшиеся задачи до крайнего срока тогда и только тогда, когда.

Теперь покажем алгоритм, который проверит, существует ли такой T . Мы рассматриваем дни d = k , k — 1, …, 1, и в течение нескольких дней мы будем делегировать задачи помощникам. Предположим, что мы находимся в день d , и мы уже делегировали задачи в течение дней после d . Позвольте быть набором задач, которые могут быть назначены в день d , так что помощник выполнит их до крайнего срока. Основное наблюдение заключается в следующем: если не пусто, то мы можем в день d жадно назначить задачу, которая максимизирует значение p _i .

Теперь докажем. Предположим, что существует график S , который в дни после d совпадает с нашим планом. Если расписание S назначает задачу и в день d , то все готово. В противном случае в расписании S в день d профессор назначает задачу j ≠ i или сам выполняет задачу j (в этом случае возможно j = i ).

В первом случае профессор ставит задание j ≠ i .Затем (поскольку помощник завершит работу до крайнего срока) и (мы предполагаем, что S совпадает с нашим планом на следующие дни). Из нашего жадного выбора получаем, что p _i ≥ p _j . Если в S профессор назначает задачу i в день d ‘, тогда d ‘ ≤ d (поскольку, и S совпадает с нашим планом в следующие дни), и мы можем поменять местами в S — дни, в которые мы назначаем задачи i и j .В противном случае, если в S профессор сам выполняет задачу i , то мы можем изменить S следующим образом: мы делегируем задачу i в день d и выполняем задачу j в те дни, в которые профессор выполнил задание i (мы можем это сделать, так как p _i ≥ p _j ).

Во втором случае профессор выполняет задание j в день d .Если j = i , то мы также можем делегировать эту задачу в день d (с). В противном случае, если j ≠ i , мы можем делегировать задачу i в день d и вернуть недостающий день для выполнения задачи j в тот момент, когда профессор работал над задачей i ( делегируя или выполняя его) в расписании S .

Во всех случаях мы получаем правильный оптимальный график, в котором профессор делегирует задачу и в день d , поэтому ключевое наблюдение доказано.

Как быстро мы сможем реализовать описанный выше алгоритм? Выбор максимума из набора может быть реализован с помощью двоичной кучи, упорядоченной по номерам p _i . При переходе с дня d + 1 на день d мы добавляем элементы из в кучу (т.е. задачи с a _i = k — d ; нам нужно отсортировать задачи по a _i для этого), и мы удаляем максимальный элемент (и добавляем его к T ).

Обратите внимание, что нам не нужно повторять все дни, но мы можем начать с дня d = мин ( k , n ), поскольку нет необходимости назначать задачи после n -й день. Таким образом, все решение (с фиксированным k ) работает вовремя.

Мы можем улучшить его, выполняя итерации не по дням, а по задачам, отсортированным по возрастанию по p _i . Каждый раз, когда мы пытаемся назначить задачу и в последний день с {1, 2,…, d _i } где d _i = мин ( k — a _i , n ), в котором еще не назначена задача . Нетрудно заметить, что полученный набор T будет таким же, как и в предыдущем алгоритме. Это назначение может быть выполнено за почти линейное время, используя структуру для непересекающихся множеств. Каждый набор содержит свободный день d и все дни после него, в которые назначена какая-либо задача.Теперь постановка задачи сводится к нахождению набора, который содержит d _i , получению минимального элемента d ‘в этом наборе, назначению задачи i в течение дня d ‘ и объединению набора с набор, содержащий элемент d ‘- 1.

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

Задача B (Подразделение Королевства)

В этой задаче мы должны разделить сетку n × м на максимальное количество частей различных размеров, образованных связанными наборами единичных квадратов. Нам нужно представить пример такого деления, используя символы из для обозначения результирующих частей. Решение этой проблемы может быть получено в три естественных шага.

На первом этапе мы на мгновение забываем о необходимости подключения и спрашиваем, какие размеры деталей дадут максимальный результат.Ответ прост, размеры должны быть равны 1, 2, 3, … Если последняя часть меньше требуемой, мы соединяем ее с предпоследней частью.

На втором этапе мы отмечаем, что разделение, предложенное на предыдущем этапе, действительно возможно. Мы можем покрыть всю сетку змеиным узором, а затем разрезать змею в соответствующих местах, чтобы сформировать соответствующие части, которые, безусловно, будут соединены друг с другом, см. Рисунок слева.

Третий шаг — пометить детали буквами «от», чтобы никакие две соседние части не имели одинаковых этикеток.Заманчиво было бы обозначить их в том порядке, в котором они появляются в змее. Однако в некоторых случаях такая маркировка не работает.

Одно из возможных правильных решений — пометить каждую часть наименьшей буквой, которая не встречается среди ее соседей (и выполнить маркировку в змеином порядке). Другая идея состоит в том, чтобы обозначить детали в первом ряду буквами A и B, во втором ряду используйте буквы C и D, в третьем ряду используйте буквы E и F, в четвертом ряду снова A и B и так на (см. рисунок справа).Начиная с того момента, когда каждая часть покрывает хотя бы один ряд, мы можем придерживаться только двух букв, A и B. В последнем разметке мы используем только 6 различных букв.

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

Конечно, описанный выше алгоритм может быть легко реализован за время O ( нм, ).

Задача C (Неквадраты)

В этой задаче нам нужно проверить, может ли данное положительное целое число n быть представлено как произведение k целых положительных чисел, все из которых не являются целыми квадратами.Назовем такое представление неквадратным.

Общий подход может заключаться в динамическом программировании над набором делителей n . Все делители n можно найти во времени. Пусть D ( n ) будет числом делителей n . Получается, что для n ≤ 10 ⁹ мы имеем D ( n ) ≤ 1344.

Мы вычисляем двумерный логический массив, где истинно тогда и только тогда, когда делитель d может можно представить как произведение j неквадратов.В вычислении используется следующая логическая формула, которая работает для j ≥ 1 и:

Временная сложность этого решения обусловлена ​​структурой данных, подобной карте, необходимой для отслеживания делителей n . Сложность памяти O ( D ( n ) k ).

Можно также улучшить время работы этого решения, отметив, что параметр k фактически ограничен, который в нашем случае равен 29. Действительно, ответ всегда «НЕТ» (аргумент в пользу этого можно вывести из следующего решения).

Существует также гораздо более простое решение, которое исследует разложение n на простые множители. Пусть n = p ₁ ^{α ₁} p ₂ ^{α ₂} … p _m ^{α _m} где p _i — различные простые числа. Тогда решение будет следующим:

1. Если α ₁ + α ₂ +… + α _m < k , затем выведите «NO».
2. В противном случае, если m > 1, выведите «YES».
3. В противном случае мы имеем m = 1. Если k — α ₁ четное, то выведите «YES», иначе выведите «NO».

Приведем обоснование этого решения. Пункт (1) следует из того факта, что любой неквадратный делитель должен иметь простой множитель. Для m = 1 нам просто нужно проверить, можно ли представить α ₁ как сумму нечетных целых k , что возможно тогда и только тогда, когда четность k и α ₁ является одно и тоже.Это дает пункт (3) алгоритма.

Наконец, рассмотрим пункт (2). Нам нужно показать, что если α ₁ + α ₂ + … + α _m ≥ k и m > 1, то существует неквадратное представление n . Возьмем в качестве первых k — 1 неквадратных делителей простые делители числа n : сначала α ₁ умножить на делитель p ₁ , затем α ₂ умножить на делитель p ₂ и так далее.В качестве последнего делителя, d , мы берем произведение всех оставшихся простых множителей. Если d не является целым квадратом, у нас есть запрошенное представление. В противном случае мы меняем последний делитель на d / p _m и первый делитель на p ₁ p _m , получая таким образом представление.

Это решение требует только найти разложение на простые числа n и работает во времени.

Задача D (стопки монет)

В этой задаче m золотые и серебряные монеты расположены в n стопки разной высоты. Мы должны переставить монеты так, чтобы было максимальное количество одноцветных стопок (в одноцветной стопке есть только золотые или только серебряные монеты). Нам разрешено выполнять любое количество операций по замене двух монет, находящихся на одной высоте в разных стопках.

Пусть k обозначает результат, то есть максимальное количество одноцветных стопок, которые могут быть сформированы.Давайте выполним двоичный поиск k . Отныне у нас остается проблема с решением: учитывая k , проверить, действительно ли оно. Очевидно, что оптимальным вариантом будет сделать k наименьшей из стопок одноцветной.

Поскольку количество операций не ограничено, нашу задачу можно переформулировать следующим образом. Пусть h будет высотой k -й наименьшей стопки. Для каждого уровня высоты 1, …, h мы знаем общее количество золотых и серебряных монет на этом уровне.Нам нужно проверить, достаточно ли этих чисел для создания одноцветных стопок k . Эта задача сведется к вычислению пересечения интервалов O ( h ).

Сначала рассмотрим каждый уровень высоты отдельно. Предположим, что на этом уровне доступны g _i золотых и s _i серебряных монет, а наименьшие стопки k содержат всего t _i монет на этом уровне.Используя эти числа, мы можем вычислить интервал [ a _i , b _i ] такой, что если и только если можно взять золотые монеты размером x и t _i — x серебряные монеты для формирования i -го уровня выбранных стопок. Обратите внимание, что такой интервал подразумевает интервал [ t _i — b _i , t _i — a _i ] для количества серебра. монеты.

Наконец, нам нужно убедиться, что интервалы для разных уровней позволяют найти верное решение. Мы выполняем итерацию от самого нижнего до самого верхнего уровня. Для заданного уровня i нам нужно пересечь интервал [ a _i , b _i ] с [ a _{i — 1} , b _{и — 1} ] и аналогично интервалы для серебряных монет. Таким образом, мы получаем один обновленный интервал [ a _i , b _i ], который затем используем для обновления интервалов для более высоких уровней.

Все решение работает в срок.

Эта задача также имеет решение для линейного времени. Пусть g _i будет общим количеством золотых монет, находящихся на i -м уровне над землей. Пусть g ‘ _i будет максимальным количеством стопок, которые могут быть сформированы так, чтобы в них были все золотые монеты на уровне i и ниже. Его можно легко вычислить, используя следующую повторяемость:

Аналогичным образом мы определяем s _i и s ‘ _i для серебряных монет.

Пусть h _i будет высотой i -й стопки, и предположим, что стопки сортируются по высоте без возрастания, то есть h ₁ ≥ h ₂ ≥ … ≥ ч _n . Мы перебираем стопки и «раскрашиваем» их (делая их одноцветными), когда это возможно. Предположим, мы рассматриваем стопку и , и мы уже раскрасили стопки с номерами 1, 2, …, и — 1 таким образом, что у нас есть стопки золота G и серебряные стопки S .

i -я стопка может быть окрашена в золото тогда и только тогда, когда g ‘ _{h i} > G . В таком случае мы показываем, что существует оптимальное решение, в котором эта стопка окрашена в золотой цвет, а стопки 1, 2, …, и — 1 окрашены так же, как в нашем решении. Рассмотрим любое оптимальное решение, в котором стопки 1, 2, …, и — 1 окрашены так же, как в нашем решении. Пусть j ≥ i будет наивысшим стеком золота в этом оптимальном решении (он должен существовать, иначе мы можем добавить стек i и получить лучшее решение).Теперь мы можем поменять местами все монеты из стека j в стопку i и, начиная с g ‘ _{h j + 1} ≥ g ‘ _{h i} > G , у нас также есть достаточно много золотых монет для обмена в стек i выше уровня h _j .

Точно так же, если мы не можем покрасить i -ю стопку в золото, но мы можем покрасить ее в серебро (т.е. s ‘ _{h i} > S ), существует оптимальное решение, в котором мы можем это сделать.

В противном случае у нас будет г ‘ _{h i} + s ‘ _{h i} ≤ G + S , что означает, что мы не можем раскрасить больше более G + S стопки высотой не менее h _i .

Так как мы можем сортировать высоты стопок, используя сортировку счетом, вышеупомянутый алгоритм выполняется за время O ( n + m ).

Задача E (Государственные дороги)

В этой задаче нам дается график в динамической настройке. Набор узлов V фиксирован, но ребра графа со временем добавляются и удаляются. Мы должны ответить на запросы следующего типа: учитывая набор узлов и момент времени, проверить, образуют ли эти узлы один или несколько целых связанных компонентов графа в этот момент времени.

Мы представляем рандомизированное решение этой задачи, которое очень просто кодировать, но при этом довольно сложно. Для каждого ребра, добавляемого к графу, мы случайным образом выбираем целочисленный вес. Для каждого узла мы храним произведение весов всех ребер, примыкающих к этому узлу. Обратите внимание, что такие значения могут быть обновлены за время O (1) после вставки и удаления ребер.

Теперь важнейшее наблюдение состоит в том, что { u ₁ , u ₂ ,…, u _k } образует ряд целых связанных компонентов тогда и только тогда, когда каждое ребро в графе смежно точно с нулем или двумя узлами u _i . Следовательно, чтобы ответить на запрос, мы вычисляем:

, где обозначает -операцию. Если указанное выше значение не равно нулю, мы знаем, что ответ — «НЕТ». В противном случае с большой вероятностью ответ будет «ДА». Вероятность неправильного положительного ответа — это где M — максимальный вес ребра.Эта вероятность оказывается достаточно малой для M = 2 ³² или M = 2 ⁶⁴ .

Все решение работает в линейном времени в зависимости от размера входа.

Задача F (Наклейки)

В этой задаче нам дается n видов наклеек s ₁ , …, s _n , где каждый s _i — это слово длиной d .Нас спрашивают, какое минимальное количество наклеек необходимо для наклеивания данного слова t длиной m .

Мы представляем простое решение этой проблемы с помощью динамического программирования. Обозначьте dp [ i ] минимальное количество наклеек, необходимое для наклеивания в точности суффикса t [ i .. m ] и тем же номером, но когда мы позволяем наклейкам переполняться и закрывать позиции от т [ i — d .. i — 1] (но не обязательно с правильными буквами). Ответ на проблему — dp [1].

Давайте посмотрим, как вычислить dp [ i ]. Позиция i t в какой-то момент должна быть закрыта наклейкой, наклеенной в этом месте. Поскольку все наклейки имеют одинаковую длину, мы можем ограничиться вставкой этой наклейки как последней или как первой. Это дает нам два случая:

1. Для некоторых j мы имеем s _j = t [ i .. i + d — 1]. Таким образом, мы можем вставить суффикс t [ i + d .. m ], возможно, покрывающий буквы от t [ i .. i + d — 1], а затем вставить с _j в позиции i . В этом случае мы используем наклейки.
2. У нас есть s _j [1 .. d ‘] = t [ i .. i + d ‘ — 1] для некоторых j и некоторых d ‘≤ d .Таким образом, мы можем вставить s _j в позицию i , а затем вставить t [ i + d ‘.. m ] с ограничением, что мы не можем изменять буквы перед положением i. + д ‘. В данном случае мы используем стикеры 1 + dp [ i + d ‘].

Если для каждой позиции i мы знаем максимальное значение l [ i ], то есть t [ i .. i + l [ i ] — 1] — это префикс некоторой наклейки, тогда случай (1) возможен, если d = l [ i ], и исход из случая (2) равно мин _{1 ≤ j ≤ l [ i ]} (1 + dp [ i + j ]).

Вычисляем аналогично, но теперь вместо набора всех стикеров мы рассматриваем набор всех суффиксов стикеров. Таким образом, мы вычисляем l [ i ] как максимальное число, такое что t [ i .. i + l [ i ] — 1] — это инфикс некоторой наклейки.

Приведенное выше решение может быть реализовано с временной сложностью O ( mnd ² ). Удивительно, но эта проблема может быть решена за линейное время относительно размера ввода, даже с наклейками разной длины, но такое решение намного сложнее.

Яндекс объявляет об обновлении основного алгоритма

Яндекс объявил об обновлении своей поисковой системы.Обновление называется Vega. Обновление предлагает много подробностей о том, как работают современные поисковые системы.

Основные улучшения в Яндексе

Яндекс называет свое обновление Vega. В этом обновлении 1500 улучшений. Из этих улучшений Яндекс выделил два, которые, по их словам, существенно влияют на результаты поиска.

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

Связано: The Ultimate Guide to Yandex SEO

Crowd Sourcing Search Result Raters

Google нанимает подрядчиков, прошедших инструктаж по оценке качества Google, для оценки результатов поиска. Яндекс полагается на свою краудсорсинговую платформу Яндекс.Толока.

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

Реклама

Читать ниже

«Люди, или« оценщики », уже давно помогают обучать наши платформы машинного обучения с помощью нашей краудсорсинговой платформы Яндекс.Толока.

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

Человеческий вклад в обучение алгоритму

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

Изменение, внесенное Яндексом, заключалось в том, чтобы нанимать экспертов по определенной теме для анализа работы экспертов по оценке с целью повышения ее точности.Это означает, что данные для обучения, предоставленные алгоритму, будут лучше, поскольку они были проверены и подтверждены экспертом.

Реклама

Продолжить чтение ниже

Поскольку данные обучения Яндекса просматриваются тематическими экспертами, алгоритм (предположительно) будет более точным, поскольку данные обучения улучшены.

Вот как это объяснил Яндекс:

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

Профессионалы, оценивающие оценщиков, варьируются от ИТ-администраторов для запросов данных до гидрологов для запросов, относящихся к рекам.

Эксперты-оценщики используют более сотни критериев для оценки работы оценщиков…

Обучая наши алгоритмы машинного обучения экспертным оценкам, наша поисковая система учится ставить релевантную информацию выше в результатах благодаря работе высококвалифицированной группы отдельных лиц ».

Связано: Интервью с поисковой командой Яндекса

Расширение поискового индекса с помощью кластеризации

Яндекс представил очень интересный способ обработки тематически похожих веб-страниц.Вместо того, чтобы искать ответ по всему индексу, Яндекс сгруппировал веб-страницы в тематические кластеры. Утверждается, что это улучшает и ускоряет результаты поиска, позволяя поисковой системе выбирать ответ из тематически релевантных страниц.

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

Технология кластеризации Яндекса позволила Яндексу удвоить свой поисковый индекс, не влияя на скорость выбора веб-страницы.

Реклама

Продолжить чтение ниже

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

Прогнозирование поисковых запросов и результатов

Интересным нововведением в Яндексе является использование алгоритмов для прогнозирования того, что пользователь спросит, и для «предварительного рендеринга» результатов по этому поисковому запросу.Хотя об этом было объявлено в контексте обновления Vega, на самом деле это было реализовано в марте 2019 года.

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

Реклама

Продолжить чтение ниже

«С марта мобильные пользователи Яндекса на Android выполняли поиск с использованием технологии предварительного рендеринга, которая предсказывает запрос пользователя и выбирает релевантные результаты, когда пользователь вводит текст.”

По теме: 9 Часто задаваемые вопросы о Яндексе SEO и PPC

Поиск современной информации

Яндекс — это российская поисковая система, которая использует нейронные сети и машинное обучение. Я считаю, что хорошо разбираться в технологиях, используемых во всем мире, потому что это позволяет мне быть в курсе того, что определяет современный поиск информации (бизнес поисковых систем) сегодня.

Анонс официального обновления алгоритма Яндекс читайте здесь:

https: // яндекс.com / company / blog / vega

Искусственный интеллект и алгоритмы машинного обучения Яндекса

1. Matrixnet, 2009
2. Палех, 2016
3. Королев, 2017
4. CatBoost, 2017
5. Оптимизация для алгоритмов искусственного интеллекта Яндекса

Ранее в этом месяце , Google представила свой последний алгоритм искусственного интеллекта BERT, который считается самым большим обновлением Google со времен RankBrain и затрагивает 10% всех поисковых запросов.

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

BERT подробно освещался в Search Engine Journal как Роджер Монтти, так и Мэтт Саузерн.

Однако алгоритмы искусственного интеллекта и машинного обучения Google — не единственные, которые используются поисковыми системами по всему миру.

Машинное обучение — это общий термин, охватывающий широкий спектр алгоритмов, которые учатся на наборах данных, чтобы предоставить:

• Рекомендации.
• Решения.
• Прогнозы.

Реклама

Продолжить чтение ниже

Он широко используется для ряда задач не только поисковыми системами, но также:

• Рекомендации по музыке и фильмам на потоковых платформах.
• Прогнозы использования энергии в разных штатах.

Поисковые системы используют это для обработки данных из Интернета и некоторых автономных источников в случае Яндекса, чтобы предоставить пользователям лучшие результаты поиска и удобство работы.

Прошло десять лет с тех пор, как Яндекс впервые представил машинное обучение в поиске, запустив Matrixnet.

С тех пор поисковая система продолжила улучшать свои возможности AI и ML с дальнейшими обновлениями, включая Palekh и Korolyov.

Matrixnet, 2009

Matrixnet работает, беря тысячи переменных и «факторов ранжирования» и присваивая им разные веса в зависимости от:

• Местоположение пользователя.
• Поисковый запрос.
• Установленные намерения пользователя

Реклама

Продолжить чтение ниже

Это сделано для того, чтобы возвращать пользователю более релевантные и точные результаты.

Ощутимое влияние Matrixnet заключалось в том, что для более коротких запросов с множеством общих интерпретаций некоммерческий контент стал занимать более заметное место на страницах результатов поиска по сравнению с более коммерческим контентом (и коммерческими веб-сайтами).

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

В тот же период, когда Яндекс запустил Matrixnet, поисковая система также принимала меры для обеспечения лучших результатов для пользователей в зависимости от местоположения.(Для кого-то во Владивостоке нет смысла получать местные результаты для Москвы, так как это 113 часов на машине!)

Они сделали это с помощью алгоритма Арзамаса, который в том году был заменен Снежинском, а затем в 2010 году — Обинском.

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

Это заметно повлияло на веб-сайты с дверными проемами с указанием местоположения и местным спамом с цитированием.

Палех, 2016

В 2016 году (через год после RankBrain) Яндекс представил алгоритм Палеха. Палех использовал глубокие нейронные сети, чтобы лучше понять смысл поискового запроса.

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

Эта технология наиболее полезна для сложных запросов, таких как поиск фильмов по неточным описаниям их сюжетов.

Королев, 2017

На основе алгоритма Палеха Яндекс выпустил обновление Королева в августе 2017 года.

По словам Андрея Стыскина, руководителя поиска Яндекса:

«Королев умеет сопоставлять значение запроса со смыслом страниц, в отличие от того, как Палех работал только с заголовками. Он также улучшает 150 страниц, которые анализировал Палех, благодаря своей способности работать с 200 000 страниц одновременно ».

Подобно тому, как работает RankBrain, Королев становится более эффективным и точным с каждой получаемой инкрементной точкой данных, а все результаты затем передаются в основной алгоритм Matrixnet.

Реклама

Продолжить чтение ниже

Одновременно с объявлением Королева Яндекс также объявил, что Matrixnet начала:

• Принимать во внимание данные своей краудсорсинговой платформы Толока (представьте себе версию Amazon Mechanical Turks).
• Обработка больших объемов анонимных пользовательских данных для дальнейшего улучшения и изменения наборов данных, из которых были доступны алгоритмы машинного обучения.

Королев также ввел понятие семантических (контекстных) векторов в поиске, что позволило ему выполнять «анализ смысла», когда пользователь отправляет запрос.Это позволило поиску учитывать предполагаемое значение всех запросов, которые привели пользователей на определенные страницы.

Это означало, что:

• На этапе индексации каждая страница была преобразована в семантические / контекстные векторы.
• Новые запросы могут быть поняты быстрее и эффективнее, с более точными результатами, чтобы не создавать негативных впечатлений от поиска.

CatBoost, 2017

В 2018 году Яндекс представил преемника алгоритма машинного обучения Matrixnet — CatBoost.

Объявление

Продолжить чтение ниже

По сравнению с Matrixnet, CatBoost (с открытым исходным кодом) может:

• Более точные прогнозы.
• Большая диверсификация результатов.
• Нечисловые вспомогательные переменные, такие как типы облаков, породы кошек и виды растений.

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

На сегодняшний день CatBoost также используется вне поисковой системы Яндекса такими организациями, как Cloudflare и CERN.

Используется там, где требуется усиление градиента на деревьях решений с уменьшенным риском переобучения, для таких задач, как борьба с заполнением учетных данных ботами.

Оптимизация для алгоритмов искусственного интеллекта Яндекса

Алгоритмы машинного обучения Яндекса — это лишь небольшая часть обновлений, которые поисковая система внесла за эти годы для борьбы со ссылочным спамом и некачественным контентом, как и Google.

Как и в случае с процессами Google RankBrain (а ​​теперь и с BERT), нет реального способа напрямую оптимизировать алгоритмы машинного обучения, поскольку они учитывают Интернет в целом.

Реклама

Продолжить чтение ниже

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

Дополнительные ресурсы:

Алгоритмические задачи в интерфейсе.Примеры и конкурс Яндекса / Sudo Null IT News

Вчера стартовал новый Яндекс Блиц — на этот раз конкурс будет интересен разработчикам интерфейсов. Обладателям мест с первого по пятое мы предложим пройти нам по упрощенной схеме: один раздел собеседования вместо четырех. Таким образом, Blitz остается самым быстрым способом попасть в Яндекс.

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

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

О задачах

Алгоритмические задачи при разработке интерфейсов в Яндексе возникали всегда. Могу вспомнить примеры из 2005-2006 годов. Одной из таких задач была система работы с абстрактными событиями. Необходимо было сделать ядро, которое позволяло бы навешивать обработчики (заданные функцией) на произвольные события (заданные строкой), после чего — вызывать конкретное событие и снимать привязку обработчика.Дополнительной сложностью было то, что перечисленные три основные операции следовало выполнить как можно быстрее. Об этом даже есть раздел в одном из старых отчетов.

Еще одной интересной проблемой стало расположение миниатюр в поисковой выдаче Яндекс.Картинок. Необходимо было произвести выравнивание потока прямоугольных объектов одинаковой высоты и разной ширины по правому краю. В общем случае эта задача не имеет решения, поэтому было разрешено изменить исходный размер картинки (уменьшить и обрезать), но так, чтобы потеря информации не превышала некоторый заданный разумный порог в процентах.

Также были задачи, связанные с разработкой шаблонизатора Яндекса, известного по ключевым словам XJST и BEMTHML. Основная сложность заключалась в том, чтобы сделать это достаточно быстро, сохранив желаемую смысловую выразительность. Подробности об этом можно увидеть в многочисленных отчетах. Вот некоторые из первых отчетов с подробностями: events.yandex.ru/lib/talks/43 andevents.yandex.ru/lib/talks/329, есть много других.

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

Например, в одной из первых версий Яндекс. Mail, вы могли перетаскивать друг на друга почти все ключевые элементы: письма в папки, теги в письма, письма в теги и даже папки в письма. В процессе, пока пользователь «зажимал» объект в руке и водил им по экрану, необходимо было выделить те элементы, на которые он мог «сбросить».Наивная реализация «в лоб» тормозилась до крайности.

Отличия реальных задач от соревновательных

Задачи внутри Яндекса, как правило, решаются в командном режиме. Мужчина не предоставлен самому себе, как на соревнованиях. Он может получить помощь от коллег и должен согласовать свое решение с интересами других участников процесса.

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

Еще одно важное отличие состоит в том, что настоящий код, который мы пишем, существует и продолжает поддерживаться в течение долгого времени. Это не процесс «сделал и забыл», пока проходят тесты. Важно помнить, что ваш код может продолжать жить — не только выполняться, но и редактировать — в течение многих лет после написания.

О других интерфейсах конкурсов

Вы легко можете найти в Интернете сайты с задачами исключительно на JavaScript. По сути, это то же спортивное программирование, только на определенном языке. Кроме того, есть формат «код в темноте», когда макет составляется без просмотра результата, слепо видишь только код. Соревнования, подобные нашему, не особо распространены, потому что из-за специфики разработки интерфейса очень сложно выбрать хорошие задачи и произвести автоматические проверки их.В Яндексе исторически сложилась сильная школа автоматического интерфейсного тестирования, в том числе с использованием сравнения скриншотов из реальных браузеров. На основе этих разработок мы стремились проверить задания на конкурсе. Для нас это тоже эксперимент, но мы уверены, что он получится, и мы уже готовимся к дальнейшему развитию темы.

Машинное обучение для победы. Как алгоритмы Яндекс.Такси помогают отслеживать… | Яндекс.Такси: Под капотом

Как Яндекс.Алгоритмы такси помогают отслеживать чистоту автомобиля, планировать время работы водителя, назначать заявки на поездки и многое другое.

Яндекс.Такси работает на сотнях алгоритмов, созданных и поддерживаемых специализированным подразделением машинного обучения и анализа данных. У этой команды два основных направления:

№1 — точное определение аспектов продукта, которые можно улучшить с помощью больших данных и алгоритмов.

Другими словами, создайте приложение, которое уже знает, куда пользователь хочет пойти, как только он его откроет; сегодня день, когда дети не отправляются в дошкольное учреждение, или день, когда они отправляются в город с друзьями на поздний завтрак? Для этих поездок требуются разные автомобили, с детскими сиденьями или, возможно, даже минивэн для больших групп.Кроме того, подъедет ли водитель немедленно или через пару минут, чтобы у всех было время первым выйти на улицу? Идеальное приложение заранее сообщит вам, как долго вам придется ждать посадки, в зависимости от класса обслуживания и где встретить водителя, чтобы получить самый дешевый тариф.

№2 — оптимизировать стоимость, скорость и структуру внутренних бизнес-процессов Яндекс.Такси. Это включает поддержку пользователей, контроль качества транспортных средств, отношения с водителями и маркетинг.

Роман Халкечев, Директор департамента машинного обучения и анализа данных Яндекс.Taxi, делится некоторыми примерами того, как данные и алгоритмы облегчают жизнь гонщикам, водителям и всей команде за кулисами.

Источник: vc.ru

Когда пользователь нажимает кнопку «Заказать», наша система начинает решать задачу по поиску драйвера, или отправка , как это принято в отрасли. Он выбирает наиболее подходящий автомобиль среди всех доступных поблизости водителей, учитывая при этом все виды факторов, включая вероятность того, что водитель примет запрос на поездку.

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

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

Другими словами, алгоритм решает проблему назначения водителя для всех пользователей одновременно за счет оптимизации системы подбора водителя и водителя.

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

Чем больше запросов на поездку и водителей одновременно находится в «буфере», тем эффективнее распределяются поездки.Здесь машинное обучение используется для расширения «буфера», и не только путем добавления дополнительных бесплатных драйверов, но и путем добавления других водителей, которые в настоящее время находятся с гонщиком, но сейчас направляются в зону, чтобы их высадить.

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

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

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

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

В июле 2018 года Яндекс.Такси представил новый алгоритм решения проблемы аэропорта путем распределения заявок на поездку в очередь (опять же, при прочих равных).Теперь, когда водитель высаживает пассажира в зоне аэропорта, он автоматически присоединяется к очереди и может отслеживать, в каком месте он находится.

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

Чтобы показать водителю, сколько времени осталось до пассажира, Яндекс.Команда такси построила модель с учетом длины очереди, исторических данных об объемах запросов на поездку в зависимости от времени и расписания прибытия рейсов.

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

В крупных аэропортах, где у нас есть больше исторических данных, система прогнозирует время ожидания с погрешностью всего 10%.В небольших аэропортах погрешность приближается к 15–17%. По недавно открывшимся аэропортам у нас нет всей необходимой статистики, но это не мешает нашей команде изучать, как делать прогнозы без них.

Яндекс.Такси Служба поддержки обрабатывает запросы в зависимости от сложности и срочности. Если гонщик что-то оставил в машине, мы должны быть на высоте. Но если мы получим жалобу на то, что водитель не ответил на сообщение в чате приложения, мы можем решить ее чуть позже.

Наша старая система технической поддержки обрабатывала запросы в порядке поступления.У оператора был список «билетов», и он раздавал их своей команде в зависимости от важности и срочности.

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

Для начала команда машинного обучения обучила нейронную сеть самостоятельно определять, насколько критичным был запрос в службу поддержки. Они сделали это, скармливая ему огромное количество старых запросов на поддержку, написанных пассажирами и уже обработанных нашей командой с указанием «критических» или «срочных».”

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

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

Чтобы ускорить процесс, наши разработчики машинного обучения предоставили разные исторические данные нейронной сети в ответах на запросы в службу поддержки, чтобы обучить их предлагать один из пяти шаблонов, которые, скорее всего, относятся к рассматриваемой проблеме. В 70% случаев действительно актуален один из рекомендованных шаблонов.

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

Алгоритмы поддержки также обрабатывают обратную связь, когда гонщики оставляют 1, 2 или 3 звезды, и могут автоматически отвечать примерно на 40% запросов. Но полностью автоматизировать поддержку невозможно, так как слишком много ситуаций, когда только человек может решить, как лучше реагировать.

Посмотрите на картинку ниже, чтобы увидеть, насколько забавным иногда был этап тестирования автоматизированной системы ответов. В какой-то момент система получила 5-звездочный отзыв от пассажира, но система вообще не отреагировала так, как ее обучали.

Ага, мы тоже посмеялись!

Недавно Яндекс.Такси дебютировало с программой «Большие перемены». Его основная задача — обрабатывать отзывы водителей, чтобы лучше адаптировать наши услуги и приложение для водителя таксометра к их потребностям. Это означает, что нам нужно было быстро выяснить, с какими реальными проблемами сталкиваются водители и как их решать. Фактически, это была программа, которая привела к нашему алгоритму очереди в аэропорту.

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

Было много жалоб на то, что водители не могли точно видеть, где находятся их водители. Таксометр (приложение для водителя) показывал, где пассажир запросил трансфер, но это не гарантировало, что он там будет ждать.Особенно, если запрос на поездку был из района с большим количеством машин и людей, например из аэропорта, стадиона или центральной площади. Наша команда четко и четко услышала эти жалобы и добавила в приложение Яндекс.Такси возможность сообщать водителям о своем местонахождении. Теперь водители могут точно видеть, где находится их пассажир, на карте таксометра.

Одна из основных задач Яндекс.Такси — обеспечение соответствия автомобилей наших водителей нашим стандартам качества. Это означает чистый, без повреждений внешний вид, чистые пустые багажники, доступные детские сиденья (если водитель имеет право принимать запросы на поездку с детьми), точное соответствие между типом автомобиля и номером с тем, что указано в приложении, и т. Д.

Но Яндекс.Такси работает через партнеров — таксопарков или самозанятых водителей, которых исчисляются тысячами, поэтому прямой контроль качества является сложной задачей. Чтобы решить эту проблему, наша команда запустила систему удаленной проверки качества (RQC).

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

Если все в порядке, водитель продолжит получать запросы на поездку. В противном случае они должны сначала решить любые проблемы.

Этот драйвер не прошел проверку фотографий.

Этот процесс также может быть автоматизирован. Алгоритмы могут определить, проходит RQC или нет, без вмешательства человека. Поэтому наша команда по машинному обучению создала еще одну нейронную сеть, способную 1) проверять изображения, чтобы убедиться, что все в порядке, и 2) предлагать, в чем может быть проблема и что необходимо решить, например, правильно применять брендированный Яндекс.Наклейки такси.

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

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

Затем алгоритм проверяет номерной знак, распознавая его на изображении и сравнивая с тем, что записано на карточке транспортного средства в системе (созданной самозанятым водителем или партнером компании такси). В дальнейшем марка, модель и цвет автомобиля также проверяются на соответствие данным в системе.

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

ВКонтакте, Facebook и Instagram — это лишь некоторые из каналов, на которых мы проводим рекламные кампании. Здесь мы можем показывать рекламу случайным пользователям или использовать интегрированный таргетинг на социальные сети. Но есть и третий вариант — подключить алгоритмы, которые помогут сделать таргетинг еще более точным.

Благодаря Яндекс.Аудитории мы можем узнать, насколько вероятно, что у конкретного пользователя есть дети или машина. Кроме того, в Яндекс.Такси есть данные о пользователях, которые заказывают поездки в классе обслуживания «Дети». Эти два источника данных можно использовать для создания похожей модели для поиска анонимных профилей, которые не используют Яндекс.Такси, но по характеристикам аудитории очень похожи на пользователей, заказывающих поездки класса обслуживания для детей. Это люди, которые лучше всего видят нашу рекламу в социальных сетях.

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

IT-гигант, о котором вы, возможно, никогда не слышали

Ранее в этом году я впервые сел в беспилотный автомобиль.Я был одним из сотен людей, которые терпеливо ждали своей очереди, чтобы покрутиться. Некоторые даже загорели во время ожидания, но чувствовали, что боль того стоила. В итоге каждый из нас получил значок с надписью «Пассажир первого беспилотного автомобиля».