Wataru

В каком виде? В виде программы. Или в виде блок схемы.

Ваша идея не верна.

Надо порисовать на бумажке и убедится, что из строки S вы можете получить только строки вида S(k1)S(k2)S(k3)...S(kn), Где S(x) - x-ый префикс строки S, т.е. первые x символов.
При этом k1 >= k2, ... k1>= kn.

При чем все строки такого вида можно получить.

Доказывается по индукции по количеству операций. Изначально строка именно такого вида (k1=длина строки). После каждой операции, эта строка сколько-то раз копируется и как-то обрезается по длине. Поэтому любая полученная строка будет такого вида. И каждую такую строку можно построить: применяйте операции с k равными k1, k1+k2, k1+k2+k3... Так вы за n операций соберете все префиксы по одному.

Теперь, раз вам во входном файле задана подстрока результата, вам надо проверить, что эта строка состоит из подстроки S, за которой идут префиксы строки S.

Так, пример из условия bcabc состоит из подстроки bc и одного префикса abc.

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

Потом нужно построить граф: из позиции 0 сделайте ребра во все позиции, где заканчивается какая-то подстрока первой строки в начале второй. Из позиции i>0 сделайте ребра во все позиции j такие, что подстрока i...j префикс первой строки.

Потом, если в этом графе есть путь из вершины 0 в вершину с номером длины второй строки - YES. Иначе - NO.

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

Когда вы выделяете массив на n элементов типа T вам надо n*sizeof(T) памяти.

Когда вы выделяете строку на n символов вам надо n+1 байт памяти. Потому что каждый символ занимает 1 байт, и вам нужно место под n символов и под завершающий символ '\0'. В C/C++ строки всегда завершаются нулевым символом. Надо про него всегда помнить и выделять под него место.

Число y переполняется. Вы записываете двоичную запись десятичными цифрами. в uint16_t помещаются число до 65535. Соответственно, если вы постараетесь 100000 туда записать, оно переполнится. Т.е. ваша программа не работает при x>=32.

Вместо запихивания довичной записи в десятичное число вы должны биты записывать в строку std::string. Потом ее перед выводом развернуть.

Скорее всего, обращение к массиву тормозит. Там, видимо, еще и проверки на попадание в границы массива происходят.

Если вы место обращения к массиву будете делать currentByte & (1 << (7-j)), то должно работать почти также быстро.

P.s. и вообще у вас какой-то странный выбор порядка битов. Обычно сдвигают вправо, к младшему биту. Тогда вместо маски будет тупо 0x1.

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

Ответ на вопрос в заголовке - vector::insert

Если хотите добавить x после k элементов в вектор a, то сделайте
a.insert(a.begin()+k, x);

А зачем вы делаете ptr = result->ai_next;?

В документации есть пример, как обрабатывать результат:
for(ptr=result; ptr != NULL ;ptr=ptr->ai_next) {

Наверняка, оно у вас возвращает одну запись, а вы сразу берете следующую, которой не существует. И дальше разыменовываете нулевой указатель ptr.

Логика вашего решения вообще непонятна. Какие-то жадные сдвиги одной из двух переменных на 1, да еще и ответ ровно один раз вернется, когда как в задаче надо найти все решения уравнения.

Там по вашей ссылке в задаче есть подсказка: уравнение можно переписать в виде (x-2y)(x+2y)=n

Отсюда получается решение: Перебирайте все делители n, не превосходащие корень. Пусть делитель d, тогда второй множитель будет n/d.

Осталось решить систему линейных уравнений:

x-2y=d
x+2y=n/d

Решается в уме - x=(d+n/d)/2, y=(n/d-d)/4

Отслось только учесть диофантовость уравнения - ответ должен быть неотрицательные целые числа. Значит, надо чтобы оба делителя d, n/d давали одинаковый остаток от деления на 4 и 2. Ну и d<=n/d, но это учтется перебором делителя до корня.

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

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

Во первых, тут есть неоднозначность. Может быть так что теги A,B,C попарно несовместимы, но заодно попарно несовместимы теги A,D,E - куда относить тег A, в какую группу?

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

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

Еще есть Алгоритм Брона — Кербоша. Он перебирает все максимальные клики.

Подсчитайте, сколько различных текстов подходят под ваш паттерн (каждый ? дает 10 вариантов - всего 10^k, где k - количество ? в шаблоне).

Посмотрите, сколько ваша видео карточка выдает хэшей. Беглый гуглеж дает что-то порядка 3Ghash/s Поделите 10^k на 3*10^9 - получите максимальное время в секундах. Можно ожидать, что в среднем понадобится половина этого времени.

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

Если я не сбился в расчетах, то вам понадобится 5-6 лет на одной карточке, чтобы подобрать текст. Если вы готовы ждать месяц, то вам понадобится 600 компов в кластере.

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

Тут есть 2 куска 1110. Но за первым идет "010", а за вторым "011". Начинать со второго - выгоднее.

В этой задаче очень маленькие ограничения - можно полностью перебирать все возможные числа и брать максимальное. Можно даже не переводить в двоичную систему, а воспользоваться битовыми операциями.
Когда вы узнали, сколько битов в числе, то самый младший бит x можно получить как x&1. Сдвинуть все биты числа на одну позицию вправо - это x >> 1. При этом младший бит пропадает. Чтобы вставить новый бит b слева нужно сделать x | (b << k) - тут k - номер позиции этого бита, считая с 0.

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

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

Edit:

Раз задача построить концентрические вложенные квадраты, то есть 2 подхода.

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

Заведите двумерный массив, заполните его пробелами, и потом циклом от n%2 до n с шагом 2 рисуйте квадраты.

Второй, более эффективный, подход - это немного подумать. Возьмите клетчатый лист, или в редакторе каком-либо нарисуйте ответ для n=9,10. Подумайте над паттернами. Первая строка будет всегда из n #. Вторая будет #, n-2 " ", #. Следующая "# #...# #" и так далее.

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

Подсказка для формулы - имеет значение, как близко строка к середине массива и четность n. Расстояние до середины можно получить как abs(n/2 - i)

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

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