Следствие из свойств скалярного произведения. Из чего это следует?

MuffinLover3,
(a+b, c+d) = (a, c+d)+(b,c+d) = (a,c) + (a,d) + (b,c) + (b,d)

Как написать функцию расшифровки этого алгоритма?

Dmitry81923, Вряд ли есть сайты. Но не надо самому писать. Там по ссылке даже код есть с объяснением.

Но вообще, если оно вам не понятно, то можно проще. Вам же всего один раз обратные найти, можно сделать более медленным методом. Для каждого множителя A просто переберите все числа X от 0 до 65535 в цикле. Найдите то единственное, при котором A*X == 1:

uint16_t a = 26399;
    uint16_t x = 0;
    while(true) {
        uint16_t t = a;
        t *= x;
        if (t == 1) {
            cout << x << "\n";
            break;
        } 
        ++x;
    };

Как написать функцию расшифровки этого алгоритма?

Dmitry81923, Вот, допустим, мы работаем с вещественными числами. Чтобы отменить умножение на 2 надо поделить на 2. Но как вообще определить деление? Математики определили его как домножение на обратное - на 0.5. 2*0.5=1. Точно так же 5*0.2 = 1 и поэтому для отмены умножения на 5 надо домножить на 0.2. А для отмены умножения на 3 надо домножить на 0.3333... Пока понятно?

Это было среди вещественных чисел. Но у вас-то в программе операции среди целых чисел помодулю 65536. Потому что state 16-битный и переполнение просто обрезает старшие биты. Те же самые числа можно получать, если перемножать в 32-битные и брать остаток от деления на 65536 (на самом деле процессор скорее всего так и работает).

Обратите внимание, в группе по модулю сложение и умножение работают похоже на обычные числа. Но вот деление - совсем нет. Потому что тупо не все числа можно делить по обычным школьным правилам. Вот как поделить 3 на 27569 и получить целое число в 16 бит? По школьным правилам оно тупо не делится. А из математики груп получается, что операция должна быть применима ко всем членам группы. Надо придумать такое "деление", что бы любое число от 0 до 65535 можно было "поделить".

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

И вот так получается, что у некоторых чисел есть обратные по модулю. 26399*27569 = 1 (mod 65536). Напишите программу, которая эти два числа перемножит в 16-битных. Получите 1. Точно так же, как 2*0.5 = 1 среди вещественных чисел, по модулю 65536 эти два числа обратны к друг другу.
Поэтому можно домножить на обратное, чтобы отменить домножение:
(x*26399)*27569 = x*(26399*27569) = x*1 = x (mod 65536).
Найти эти обратные можно, например, с помощью расширенного алгоритма эвклида.

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

Как еще чуть ускорить алгоритм?

Еще опишите, что там за ужас со вводом происходит. Какой формат данных в файле?

Как найти максимально похожий цвет?

Maxim Siomin, Совремменные процессоры могут выполнять несколько сот миллионов операций в секунду. Допустим, мобильный процессор - слабенький. Пусть будет 100 000 000 операций в секунду. у вас будет 3 разности, 3 произведения, два сравнения на каждый цвет. ну еще по мелочи округлим до 20 операций на цвет. Итого - 30000 операций на каждый запрос. Итого - в секунду поместяца 3300 запроса. А вам надо упихнуть 120. Т.е. все помещается и еще 97% свободного процессорного времени остается.

Как найти максимально похожий цвет?

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

Как написать функцию расшифровки этого алгоритма?

Dmitry81923, Позвольте прокоментировать. Ваш код очень плох. Никогда не надо работать с адресами через int64_t. Это непереносимо, разные версии компиляторов и уровни оптимизации могут вам все сломать.

Погуглите про "арифметику указателей" в C. К char* можно прямо прибавлять 1, не надо его для этого приводить к int64_t.

Далее, ваш метод прочитать 2 байта из arg1 - вот так вот просто читая unsigned int по какому-то адресу - это тоже неправильно. Или делайте memcpy, или вручную через сдвиги и битовые операции:

unsigned int b1 = *text++;
  unsigned int b2 = *text++;
  state = (b1 << 8) | b2;

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

Ну и далее, названия arg1, arg3 - это очень и очень плохо. Вы там сами не путаетесь? Я понимаю в условиях соревнования, когда код надо писать быстрее называть переменные text, t, n, i, a. Это тоже не очень хорошо, но хоть устаявшиеся нормы есть (a - массив входных чисел, t - текст, n - количество входных чисел, i, j - индексы).

Как написать функцию расшифровки этого алгоритма?

MaxKozlov, если он signed, то там undefined behavior при перепрлнении. А так, важно, что множители взаимнопросты с модулем (65536). Обратимо было бы даже если бы они не были простыми, а просто нечетными.

Как написать функцию расшифровки этого алгоритма?

Dmitry81923, Прочитали мой ответ? Прочитали ссылку на обратне по модулю?

Понимаете, что значит "по модулю"?
Вы, вроде, понимаете, что вам надо обратить операции. Если в шифраторе стоит +65530, то в дешифраторе будет -65530, что то же самое, что +6 (потому что по модулю же все). Т.е. чтобы обратить прибавление 65530 вам надо прибавить обратное относилельно сложения.

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

Как написать функцию расшифровки этого алгоритма?

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

Как написать функцию расшифровки этого алгоритма?

Dmitry81923, Василий Дёмин, переполнение - это взятие по модулю 2^16. У нечетных чисел есть обратные по этому модулю. Все обратимо.

Как написать функцию расшифровки этого алгоритма?

Dmitry81923, Вот вам сильно упрощенный пример. Пусть это у вас 4 бита. Умножение по модулю 16.

Так вот, обратное к умножению на 3 - умножение на 11.

5 * 3 % 16 = 15
15 * 11 % 16 = 165 % 16 = 5

8 * 3 % 16 = 24 % 16 = 8
8 * 11 % 16 = 88 % 16 = (5*16 + 8) % 16 = 8

11 * 3 % 16 = 33 % 16 = 1
1 * 11 % 16 = 1.

Вот - если бы шифрование состояло только из state = state * 3, (а state был 4-битный), то в расшифровке было бы просто домножение на 11.

Как написать функцию расшифровки этого алгоритма?

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

Как правильно построить многоугольник по точкам?

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

Есть ли приложения генерирующие анимацию облака точек по видео?

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

Как настроить сборку для линковки двух разных версий одной библиотеки?

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

Еще вариант, это иметь две версии библиотеки, названные по-разному, собранные в dll. И тогда вы руками будете подгружать нужные вам функции из измененной библиотеки.

Как настроить сборку для линковки двух разных версий одной библиотеки?

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

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

Как настроить сборку для линковки двух разных версий одной библиотеки?

Вадим Ушаков, Нарушить One Definition Rule не получится. Никак. Как не получится, например, писать конструкции языка на русском языке. Ну вот так компилятор устроен, что ему надо писать "for" а не "цикл". Точно также надо чтобы все функции в исполняемом файле имели разные сигнатуры.

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

Откуда у вас взялось желание использовать одинаково названные функции? Зачем? Почему? Если они идентичные по коду, то зачем вам копии? Если они разные, то как вы решаете, какая из них вызывается в каждом конкретном месте?

Как настроить сборку для линковки двух разных версий одной библиотеки?

Вадим Ушаков, Еще можно прокладку между монитором и клавиатурой поменять.

Почему LCS алгоритм находит совпадение в конце последовательности?

Антон Жучков, Вот как раз хотел спросить, а что делать в случае "abcd" и "cdba" - тут есть 2 варианта взять наибольшее LCS размером в 2, но оно или в первой строке раньше, или во второй. Значит у вас надо именно минимизировать вхождение в первой строке.

Дальше в ответе смотрите ниже.