Wataru

Я придумал решение через динамическое программирование.

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

Ключевое наблюдение - если есть какой-то ответ (распределение заказов по поставщикам), то среди всех активных поставщиков всегда есть кто-то один, у которого текущая цена минимальна. Можно скидывать ему товары от остальных, пока не упремся в границу переключения цены у них. При этом цена у этого поставщика может еще и улучшиться. Общая сумма только улучшиться от этого. Если упремся в запасы этого поставщика, то можно его исключить из рассмотрения и повторить операцию. Таким образом, лишь улучшая ответ, мы придем к тому, что какие-то поставщики продают весь свой запас целиком, какой-то один продает сколько-то (и его цена меньше всех оставщихся). Все оставшиеся продают ровно минимальное количество для какой-то цены (ключ из входных данных). Можно в массив цен у каждого поставщика дописать вариант => <последняя цена>, если там такой записи еще нет. И еще запишите туда 0 => 0 в начало (купить 0 за 0). Тогда все еще упрощается - все поставщики, кроме одного, продают ровно какой-то свой priceBreak штук.

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

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

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

База тривиальна: DP(0,0) = 0, DP(i>0, 0) = infinity (на практике - большое число, или -1 и это значение надо отдельно проверять при переходе).

Переход:

DP(i,j) = min_{k : priceBreak[j][k]<=i} DP(i-priceBreak[j][k], j-1) + priceBreak[j][k]*cost[j][k]

Тут мы просто перебираем, сколько продает последний поставщик. Берем оставшиеся у предыдущих (DP(...,j-1) и прибавляем, сколько заплатим последнему.

Вот, подсчитали вы ДП. Теперь ответ - min_{i <= n, i <= stock} DP(n-i,m) + (i)*cost(i). Перебирайте, сколько вы купите у особого поставщика. Берите оставшееся из динамического программирования.

Если поставщиков M, надо купть N штук, у каждого поставщика по K цен, но это решение будет O(M*(M*N*K + N)) по времени и O(M*N) по памяти. (На самом деле, можно уточнить оценку по времени- O(M*(M*N+N*L+N)), где L - общее количество записей в массивах цен у всех поставщиков).

Для восстановления ответа вместе с DP() запоминайте, какое значение k выдало лучший результат. Потом можно будет с конца размотать оптимальный ответ, выдавая известное значение последнему поставщику.

Если цены у поставщиков могут возрастать при увеличении количества, то решение остается в силе, только надо дописать в каждый массив "количество=>цена" элементы с количеством на 1 меньше каждого priceBreak. Потому что теперь в любом ответе все-равно можно будет перекидывать от одного заказчика к другому, пока не упремя или в priceBreak сверху, или в последнее количество с неменяемой ценой. И опять получается, что только один поставщик будет продавать не фиксированное в массиве значение.

Можно вместо ДП гнать симплекс метод, как Philipp уже написал (будет быстрее, если поставщиков мало, а количесто штук очень большое).

Возможно, можно ускорить решение в M раз, если вместо M разных ДП гнать одно со всеми поставщиками. Потом перебрать i<=n, распределить i штук по поставщикам беря только priceBreak, а потом прибавить остаток к поставщику с минимальной ценой (не переваливая за следующий priceBreak!). Но я не уверен, что это будет работать (не смог пока доказать, что, если у оптимального ответа урезать торчащий от priceBreak хвост у кого-то поставщика, то ответ останется оптимальным для нового количества).

Простой вариант в реализации - перебирайте перестановку. Вот у вас в ответе буквам сопоставляются числа. Зафиксируйте порядок букв (вершин в одном графе). Тогда вершины второго графа (числа в ответе) будут представлять собой перестановку. Перебирайте все перестановки. Потом проверяйте, что одна матрица смежности после перестановки станет равна второй. Буквально для всех i, j проверяйте, что a[p[i]][p[j]] == b[i][j].

Перебор перестановок - известная задача. Применяйте этот алгоритм в цикле к текущей перестановке (которая изначально p[i] == i), пока получается. Реализация этого алгоритма уже есть в python.

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

Чуть более сложный в реализации, но более быстрый - перестановки перебираются рекурсивной функцией с одного конца. При этом, по мере выбора нового элемента, сразу же производятся все проверки (вот, зафиксировали вы p[i] на i-ом уровне рекурсии, сразу же посмотрите, что для всех ja[p[i]][p[j]]==b[i][j] выполняются).

Как соберете всю перестановку (дойдете до n-ого уровня рекурсии) - вы нашли ответ.

Если реализация выдает неправильный ответ, попробуйте вместо условия a[p[i]][p[j]]==b[i][j] поменять на a[i][j]==b[p[i]][p[j]] (Тут сложно понять, прямую или обратную перестановку вы хотите в ответе).

Алгоритм обхода в ширину или в глубину. Еще его называют алгоритм заливки. Гуглите. Если за одну заливку вы закрасили все черные пиксели, то фигура одна. Иначе, если компонент взязности несколько - разрыв есть.

Я так понял, надо распараллелить? Посмотрите на OpenMP - работает в С/C++. Параллеленье очень просто делается - вставляете какие-то директивы в код, ключи компиляции и все работает.

Как решать задачу паралелльно: Разбейте всю строку на N (количество потоков) частей и каждый поток отдельно для каждой части найдет ответ внутри нее. А также две велечины: Самый последний символ '<', самый первый симовл '<' и вообще, есть ли они в этом куске.

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

Вам равноудаленные или наиболее удаленные точки? Это немного разные вещи.

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

Теперь, что такое серединный перпендикуляр в манхеттанском расстоянии - это прямая, через середину отрезка между точками, строго под углом в 45 градусов. Соответственно, 2 таких перпендикуляра не могут пересечься.
Осталось только посмотреть пересечение таких прямых и границы области, и вершины области.

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

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

Т.е. вся логика на клиенте, но она продублированна и проверяется на сервере (например, проверка, что нет 10^20 кликов за секунду, что очков хватало на покупку апгрейда).

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

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

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

В общем случае решения может и не быть вообще. Если формула - нетривиальный полином 20-ой степени, то решения символьного вообще не существует.

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

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

И меня не устраивает "единственный" проблемный отрывок кода:
if ndata[i] % 2 != 0 and nf % 2 != 0: lucky += 1

Там вообще какой-то бред написан. При чем тут проверка на четность вообще?!

Вам надо подсчитать солько чисел из trda есть в ndata и вывести Lucky, если насчитали хотя бы 3 (перечитайте же условие задачи).

Соответственно должно быть что-то вроде

if nf == ndata[s]: cnt+=1
...
if cnt >=3:  print('Lucky')
    else: print('Unlucky')

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

Если я правильно понял задачу, то надо подсчитать для каждого i
sum_{j=1..n} (i%j?1:0) % 2.

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

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

Лампа будет переключена ровно столько раз, сколько делителей у ее номера. Иными словами - вам надо понять, четное ли количество делителей у каждого числа. Вспоминаем, что любое число представимо в виде разложения на простые множители: p1^k1*p2^k2* ... pm^km. Можно подсчитать количество делителей - это будет (k1+1)(k2+1)...(km+1), ведь каждое простое число может входить в делитель в степени от 0 до ki включительно.

Теперь, в каком случае это число будет нечетным? Только если все ki четные. А это значит, что число - полный квадрат (все степени четные же. Берем корень, делим степени пополам, получаем целое число).

Итого ответ - проставить true в массиве по всем индексам i*i.

Мне лень разбираться в вашем коде. Вот правильное решение:

Для всех интервалов добавить в массив точек пары {время начала, +1} и {время конца+1, -1}. Это массив точек - границ вакансий на оси времени (прибавляем 1 к времени конца, потому что последняя секунда включена в интервал). Потом сортируем этот массив. Теперь одиним проходом можно выделить из массива все отрезки времени и сколько на них было открыто вакансий.

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

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

Еще можете посмотреть предыдущий ответ вашему товарищу по курсу: В чем ошибка в алгоритме поиска количества интервалов?

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

Ваш код, например посчитает палиндромом строку "aab".
Потом, тут еще зачем-то бинпоиск присобачен. Зачем, вообще непонятно.
И еще ваше решение слишком медленное. Тут сложность порядка O(n^2 log n), что для 200000 ни в какие ограничения не влезет.

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

Как преобразовать слова?

Быстрое решение - построить для этого массива суффиксное дерево алгоритмом Укконена (или вот ссылка), потом обойти его, найти самую глубокую вершину, у которой есть более одного ребенка, и вывести путь до нее от корня. Работает за O(n).

Edit:

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

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

Ответ "можно" если
1) Каждому символу первой строки соответствует один и тот же символ второй строки
2) Если есть замены в виде цикла (вроде а->б, б->в, в->а), то нужна хотя бы одна свободная буква (та, которая не стоит справа в замене).

Решается так:
1) Проверить, что строки равны. Это особый случай
2) Проверить, что длина одинаковая?
3) Завести мап символ->символ, пройтись по строкам параллельно и записывать мап[строка1[i]] = строка2[i], если там пусто. Иначе - проверить, что там уже записано то же самое.
4) Проверить, что различных символов во второй строке меньше 33. Можно с помощью сета, который наполняется в том же цикле, что и в шаге 3.