Wataru

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

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

Воспользуйтесь алгоритмом тарьяна: https://e-maxx.ru/algo/lca_linear_offline для получения ответов на все запросы LCA сразу.

Сначала при вводе создайте дерево целиком и запомните все запросы Get в массив. Потом пройдитесь по массиву запросов и раскидайте их в списки на вершинах, как надо в алгоритме таръяна.

Вам надо лишь чуть-чуть подкорректировать этот код, чтобы вместе с вершиной-запросом добавлять в списки к вершинам номер этого запроса. И тогда вместо вывода v+1, q[v][i]+1 вы сможете записать ответ в массив по нужному индексу.

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

Вы правильно поняли, что вам надо найти минимальный делитель числа K.

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

Если вы не нашли делителя до корня, то число простое и в качестве делитеял можно брать все K и тогда ответ будет K-1.

Как выяснили в комментариях, метрика будет sum_i w[i]^2 (actual[i]/ needed[i] - 1) ^ 2.

пусть x[i] - соклько i-ого продукта
Пусть a[i][j] - сколько в еденице i-ого продукта j-ого ингредиента. Тогда всего j-ого ингредиента будет sum_i a[i][j] x[i].

Тогда получаем следующую оптимизационную задачу:

Sum_j (sum_i A'[i][j] x[i] - C[i]) ^ 2 -> min
sum_i x_i = 1
x_i >= 0

Сумма всего приравнивается к 1, потому что иначе надо считать пропорции и получится вообще ужас-ужас.

A'[i][j], C[i] - какие-то числа, которые элементарно получаются из a[i][j], w[i] и needed[i].
A'[i][j] = a[i][j]*w[j]/needed[j]
C[j] = w[j] / needed[j];

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

Можно применить метод лагранжа, а точнее метод Каруша — Куна — Таккера

Сначала выразите x_1 = 1 -sum_j>1 x_j, подставьте во все уравнения и получите:
Sum_j (sum_i A''[i][j] x[i] - C'[i]) ^ 2 -> min
sum_i x_i -1 <= 0
x_i >= 0

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

Для условия жесткости придется рассмотреть 2 случая - лямбда - 0 или тогда sum_i x_i - 1 = 0

Прорешать оба случая (СЛАУ) и взять те, где все получается положительным.

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

Полный перебор. Вам надо найти множества, имеющие сумму в половину от суммы всех чисел.

Можно итеративно - перебирайте число от 0 до 2^|количество чисел|. Биты в этом числе будут обозначать, берется ли конкретный элемент множества в сумму. Дальше считайте сумму текущего подмножества пользуясь бытовыми операциями, чтобы проверить стоит ли заданный бит в 0 или 1. Если набрали половину общей суммы - выводите те индексы, где биты 1 как одно множество, а оставшиеся - как второе. Чтобы каждое разбиение не выводить 2 раза, требуйте, чтобы старший бит был 0 (перебирайте до 2^|количество чисел-1|)

Можно рекурсивно. Рекурсивная функция принимает текущий набор чисел и номер следующего числа кандидата. Функция или берет или не берет текущего кандидата и запускается рекурсивно передавая следющий номер как кандидата. Если все числа рассмотрены - проверяйте сумму и выводите разбиение. Можно соптимизировать - если уже набрали сумму больше половины, дальше перебирать смысла нет. Опять же, первое число можно потребовать всегда брать или всегда не брать, чтобы не выводить одно и то же разбиение 2 раза.

То, что вы делаете, называется очередью событий.

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

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

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

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

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

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

Есть такой алгоритм. Называется quickSelect. Фактически, это обрезанный quickSort, где после выбора ведущего элемента и разбивки массива работа продолжается только в той половине, где находится раздел между первыми K элементами и остальными N-K.

Пусть у вас N элементов в массиве и надо вернуть K минимальных. Тогда сортировка будет работать за O(N log N), а quickselect за O(N) в среднем*. В худшем случае может быть и квадратичное время работы, но этот случай практически невозможен, если реализация испольует случайные числа для выбора ведущего элемента.

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

Суть его в том, чтобы в куче (heap aka priority queue) поддерживать пока найденные K минимальных элементов. При этом куча будет на максимум. Сначала туда кладутся первые k элементов массива, а потом каждый следующий вытесняет максимальный элемент в куче, если он его меньше.

* Вообще говоря, можно заставить quickselect и quicksort работать идеально всегда, если использовать алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна, который ищет медиану за O(n). Но на практике этот алгоритм не применятеся, потому что у него такая константа, что там на логарифм хватит и еще на квадрат останется.