Wataru

Это известная задача иосифа. По ссылке есть всякие решения. Вам подойдет самое тупое и медленное. У вас в задаче k прибито гвоздями к 2.

Понять те формулы можно примерно так. Съели мы первый куст, перешли ко второму. Теперь перенумеруем их, что останется? Та же самая задача, только с n-1 кустом. Только все кусты сдвинуты на k позиций и один номера у них на один уменьшены. Т.е. можно взять тот самый куст который при n-1 останется и найти, какой у него был номер до сдвига.

Это обобщение известной задачи, где пропущено одно число. Там можно, например, вычесть все числа из n(n+1)/2. Или про-xor-ить все числа от 1 до n и все числа в массиве.

Для двух чисел нужно составить какие-то 2 уравнения, Например, найдите сумму двух чисел и сумму их квадратов: Сумма пропущенных чисел - это n*(n+1)/2 - (сумма всех чисел в массиве). Здесь надо аккуратно не забыть о возможном переполнении (если ваш язык, например, С++). Сумма квадратов: сумма квадратов всех чисел от 1 до n минус квадраты всех чисел в массиве.

Итак, вы за O(n) двумя не вложенными циклами (один для суммы квадратов 1..n, другой для обработки всех чисел массива) нашли X+Y=A и X^2 + Y^2=B.

Теперь решите уравнения относительно X и Y: Выразите X через Y из первого уравнения и подставьте во второе. Решите квадратное уравнение и получите:
X = (A-sqrt(2B-A^2))/2, Y = (A+sqrt(2B-A^2))/2.

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

После сведения к теории графов есть решение за O(n^3) через венгерский алгоритм (реализация) или через алгоритм посика максимального потока минимальной стоимости (Там реализация, медленнее венгерского метода. Вот решение за n^3, но код готовый я не нашел).



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

Невозможно решить вашу задачу. У вас 65535*255 вариантов входных данных и по условию они должны выдавать разные значения. Итоговое количество чуть не дотягивает до 2^24 - а значит в 16 бит его никак не засунуть.

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

Еще лучший вариант - вместо списка использовать какой-либо set в ids. Это будет работать совсем быстро, если ids длинный, а data короткий.

Эм... Вам надо читать данные из входного файла (в задаче это input.txt или stdin).

import sys

n = int(sys.stdin.readline().strip())
comp = [sys.stdin.readline().strip().split(" "), sys.stdin.readline().strip().split(" ")]

Это не самый быстрый способ читать в питоне, но это мешает, когда чисел порядка 100000. У вас же в задаче всего ~2000 чисел и можно и так делать.

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

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

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

На пальцах - можно и складывать и брать большее. Но последнее - более точная оценка. Но на самом деле надо формально расписать по определению. Что значит первая часть O(N)? Для некоторых чисел N1 и С1, при N>N1 первая часть алгоритма делает менее С1*N операций. Аналогично, при N>N2, вторая часть выполняет менее С2*log(N) операций.

Итого имеем, при N>max(N1,N2), всего выполняется менее C1*N+C2*logN операций. Если взять C = max(C1, C2), то можно сверху ограничить количество операций C*(N+log N). Т.е. мы доказали, что ваш алгоритм - O(N+log N). Далее, начиная с какого-то N>N3 N > log(N). Т.е. при N> max(N1,N2,N3) можно ограничить время работы как C*(N+N) = 2*C*N = C'*N. А это уже означает, что весь алгоритм - O(N).

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

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

Советую посмотреть в сторону Burrows-Wheeler transform и потом попробовать RLE или LZ присобачить сверху. Может, ваши данные будут им хорошо сжиматься.

Еще вам тут сильно помогло бы что-то вроде Base64 encode/decode. Допустим у вас k символов в алфавите. Значит каждый символ несет log_2(k) бит. И если у вас символов N, то ваша входная строка содержит N*log_2(k) бит информации. Округлите это число вверх и сгенерируйте столько битов. Это фактически преобразование из k-ичной системы счисления в двоичную. На больших строках будет тормозить, потому что пока мне не очевидно, как для произвольного k делать преобразование быстро, а не делить большое число на 2 с остатком. Если только у вас k не степень двойки, тогда как в base64 можно быстро преобразовывать по блокам.

Потом можно эту битовую строку сжать каким угодно алгоритмом (разбить на блоки, скажем, 8 бит и хоть хаффманом, хоть lz). Потом надо сжатую битовую строку преобразовать назад в k-ичную систему счисления.

Можно комбинировать сжатие на исходном тексте и запись произвольной битовой строки в вашем алфавите. Например после BW-transform вы гоните LZ на тексте из цифр. LZ для эффективности надо уметь писать произвольные битовые строки. Вот вы где-то в памяти отдельно собираете новые символы, которые замыкают новые строки-эталоны (цифры в вашем примере), и отдельно битовую строку. Потом эту строку переведите в k-ичную систему счисления и запишите перед просто символами (как-то закодировав ее длину в скольки-то первых символах заголовка).

Читайте строку std::string. Проверяйте,что в ней максимум 1 '-' в самом начале, далее первая цифра не '0' (если второй не ',', есть максимум один символ ',' и он не первый. Потом используйте stringstream чтобы прочитать double.