Задать вопрос
Ответы пользователя по тегу Алгоритмы
  • Как можно предиктить дату регистрации при массиве данных?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Единственная мысль: попробуйте что-то вроде кубических сплайнов. Для первого интервала делайте квадратичную интерполяцию по 3 первым точкам. Для каждого следующего интервала - кубическую по 4 точкам (начало предыдущего интервала, этот интервал, конец следующего).
    Типа если мы видим что между точками 1 и 2 много регистраций, между 3 и 4 мало, то скорее всего на текущем интервале от 2 до 3 точки идут более плотно в начале.

    Но тут может быть косяк: кубическая интерполяция может дать и отрицательное приращение дат. Тогда текущий отрезок надо сделать линейно или квадратично.
    Ответ написан
    Комментировать
  • Как построить топологию сетей (данные в FDB таблице) когда связи замкнуты в кольцо?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вообще говоря, однозначно вы восстановить все не сможете. Допустим у кольцо из 6 узлов:
    100-101-102-103-104-105-100

    При этом можно добавить связи 100-103 и 101-104. А можно добавить 100-104 и 101-103. В обоих случаях вы по всем портам видите одно и то же - все узлы. FDB таблица будет идентична.

    Вы можете только определять компоненты двусвязности в графе - этакие кольца с всеми хордами внутри, но конкретные их формы - вы знать не можете.

    Если допустить, что в графе нет парных ребер (2 узла не соеденины несколькими связями), то можно компоненты находить так: Если у узла по двум портам видны одни и те же узлы, эти 3 вершины надо объединить в одну компоненту. Потом эти компоненты надо "сжать". В любой записи все узлы из этой компоненты будут идти вместе - замените их все на один номер компоненты. Получится граф без колец, в нем решите задачу, как умеете. Все входящие ребра в компоненту надо назначить тому узлу, у которого по какому-то порту виден другой конец этого ребра. Потом как угодно объежинить все узлы в компоненте оставшимеся портами. Их там у каждого узла будет хотя бы 2, так что объедините их в произвольное кольцо и потом оставшиеся порты надо объединять парочками, начиная с двух самых больших узлов (по количеству не занятых портов).
    Ответ написан
    Комментировать
  • Какие переходы для ДП у "Гелифиш и незабудка" codeforce?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Не вижу, где тут ДП.

    Вы правильно заметили, что можно вместо ai и bi рассматривать только ai^bi. Мы как будто берем все A по дефолту и каждый игрок может своим решением это стандартное действие отменить, что равносильно брать или не брать ai^bi.

    Но надо заметить еще одно важное свойство (пусть di = ai ^ bi). Любое di можно заменть на di^dj (j > i) и задача остается эквивалентной. Тут каждый игрок вместо решения брать или не брать dj в зависимсоти от текущей суммы, он будет решать. делать ли статус у dj таким же как у di или нет. Ну или, рассуждение как выше, стандартное действие - брать dj если di было взято. Каждый игрок может своим решением это действие отменить.

    А это уже очень похоже на вычитание линейных уравнений друг из друга в методе гауса. Можно этим заняться и привести Di к виду, где для каждого разряда мы найдем "базисный вектор" и единица будет стоять только в нем, а во всех остальных числах на этом разряде будет стоять 0. Для каких-то разядов мы может такого не найдем, там может быть много единиц, но все они будут в базисных векторах для каких-то других разрядов. При чем начинайте фиксировать базис с максимальных разрядов. Тогда у вас будут какие-то базисные разряды, и не базисные, которые однозначно определяются базисными и меньше их.

    Т.е. идете с конца по массиву D, из текущего числа xor-ите все базисные вектора. если стоит единица в нужном разряде. Если там остался не ноль, добавляете это число в базис для старшего бита.

    И тут уже сразу ясно, надо ли какое-то Di брать или нет. Каждый игрок знает, хочет ли он этот разряд в конце сделать 1 или 0 (в зависимости от его цели и того, стоит ли 1 в xor всех A в этом разряде).

    Вот и все. Никакого ДП.
    Ответ написан
    Комментировать
  • Почему неправильно работает Keeloq?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вот код на C:
    #define KeeLoq_NLF		0x3A5C742E
    #define bit(x,n)		(((x)>>(n))&1)
    #define g5(x,a,b,c,d,e)	(bit(x,a)+bit(x,b)*2+bit(x,c)*4+bit(x,d)*8+bit(x,e)*16)
    
    u32	KeeLoq_Encrypt (const u32 data, const u64 key)
    {
    	u32					x = data, r;
    	
    	for (r = 0; r < 528; r++)
    	{
    		x = (x>>1)^((bit(x,0)^bit(x,16)^(u32)bit(key,r&63)^bit(KeeLoq_NLF,g5(x,1,9,20,26,31)))<<31);
    	}
    	return x;
    }
    
    u32	KeeLoq_Decrypt (const u32 data, const u64 key)
    {
    	u32					x = data, r;
    	
    	for (r = 0; r < 528; r++)
    	{
    		x = (x<<1)^bit(x,31)^bit(x,15)^(u32)bit(key,(15-r)&63)^bit(KeeLoq_NLF,g5(x,0,8,19,25,30));
    	}
    	return x;
    }


    Ищите несоответствия. Во-первых, надо делать не &64, а &63.

    Во-вторых, в encrypt надо использовать x, а не data. Чтобы каждый следующий раунд использовал результат вычисления предыдущего, а не считал заново одно и то же.
    Ответ написан
  • Какие переходы для ДП Codeforces Петя и пауки?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Сначала переформулируем задачу - надо найти минимальное количество клеток с пауками в конце. Каждая клетка доски должна быть "покрыта": или быть с пауками, или быть соседней с клеткой с пауками.

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

    Что-то вроде такого расположения работает на больших досках:
    *...*...*
    ..*...*..


    Во-вторых, можно решать через графы. Пусть каждая клетка - вершина графа. Ребра между соседними клетками. Заметим, что граф - двудольный (шахматная раскраска доски - это и есть 2 доли). Исходная задача поиска минимального количества клеток с пауками, это фактически задача поиска контролирующего множества вершин: каждая клетка должна или быть во множестве, или быть соседней с клеткой из множества. В двудольном графе эта задача равнасильна поиску максимального паросочетания. Это решение за O(n^2m^2).

    Если хотите ДП, то перед переходами надо определиться с состояниями. Ясно, что будет какое-то ДП по профилю. Будем целиком покрывать сколько-то первых строк, а состояние последней строки хранить в маске. Поскольку каждая клетка может быть покрыта как снизу, так и сверху, то в состоянии надо держать состояние 2 последних строк.
    Например, состоянием может быть f(k,m1,m2) - расставили пауков в клетках их первых k строк. Считаем минимальное количество пауков. Первые k-1 целиком покрыты, строка k покрыта маской m1, а строка k+1 - маской m2. База f(0,0,0) = 0, f(0, m1, m2) = infinity. Ответ будет в min_m2 (f(n, 2**m-1, m2)).

    Переход снизу вверх: перебираем, куда мы ставим пауков в строке k+1. При этом важно, что бы строка k оказалось целиком покрыта. Пресчитываем маску в строке k+1, а маска в строке k+2 - это будет куда мы поставили пауков:
    F(k,m1,m2) --> F(k+1, m2 | m3 | (m3 << 1) | (m3 >> 1), m3), для всех m3, таких что m3 | m = 2**m-1

    Это будет решение за O(n6^m).
    Ответ написан
    Комментировать
  • Какую букву в игре поле чудес в этом случае лучше всего открыть? правильное ли это решение?

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

    Так в вашем примере буква О откроется либо нигде, либо в 3-ей позиции, либо в 3-ей и 5-ой. В любому случае отбросятся 2 из 3 слов.

    В примере
    СЛЕВА
    СЛОВА
    СЛОВЕ

    Надо назвать E. Либо откроется 3-я буква, либо никакая, либо 5-ая. Опять, с одной попытки вы уменьшили множество вариантов до 1.

    Надо все слова сгруппировать по тому, на каких позициях в них стоит данная буква (пустое множество позиций - отдельный вариант). Из всех групп вас интересует худший вариант - самая большая. Вам надо выбрать букву, чтобы самая большая группа была минимальна.
    Ответ написан
    2 комментария
  • Почему моя реализация Shaker Sort-а такая медленная?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Возможно, копирование данных во временные переменные a и b - медленно. Сравнивайте просто item[i] и item[i+1].

    Потом, попробуйте закоментировать второй цикл, который идет с конца в начало. Сортировка первратится в bubbleSort. Я думаю, что это здорово ускорит ее. Тут дело в железе: самое медленное в современных процессорах - это обращение к памяти. И оно всякими костылями и подпорками ускореяется. Один из таких костелей - перефетчинг: когда вы читаете данные из какого-то места, процессор заранее читает сразу блок побольше, вдруг пригодится. Начиная с этого адреса и вперед.
    И когда цикл идет i++, то эта оптимизация срабатывает. Данные для следующей итерации уже оказываются в кеше и работа с ними быстрая. С i-- этот фокус никак не помогает, поэтому циклы задом-на-перед гораздо медленнее циклов идущих по возрастанию индексов, даже если там ровно такие же операции. Потому что там команда чтения данных занимает гораздо больше тактов процессора.
    Ответ написан
    5 комментариев
  • Как лучше восстановить индексы в n-мерном рюкзаке с точным весом?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Для восстановления вам нужен второй массив, где вы храните одно из 3 значений - в какой из трех наборов идет i-ая гиря. Когда считаете dp и пишите, что можно составить i, w1, w2 вы же эти значения получили куда-то поместив последний элемент. У вас или к w1 что-то было прибавлено, или к w2, или никуда. Это 3 варианта.

    При восстановлении начните с N, sum/3, sum/3 и в цикле вычитайте 1 из первого индекса и вес i-й гири или не вычитайте или вычитайте из одного из весов, в зависимости от сохраненного знаяения во втором массиве.

    Можно вместо второго массива в dp хранить 0, если это состояние невозможно и или номер кучки для последней гири.
    Ответ написан
    Комментировать
  • Как научиться решать алгоритмические задачи?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Тут поможет только практика. Чтобы научиться решать задачи - надо много задач решить. Если не можете какую-то задачу решить сами, читайте разбор или чужие решения, пока не поймете, что там происходит. И потом обязательно реализуйте решение сами, не перепечатывая готовое.

    Хорошие книги: Кнут "искусство програмирования", Кормен "алгоритмы. Построение и анализ", Бхаргава "Грокаем алгоритмы". Старайтесь прорешивать все упражнения в этих книгах. Но прочитав их вы задачи решать не научитесь, а лишь подтянете базу.
    Ответ написан
    Комментировать
  • Какое оптимальное решение для трёхмерной задачи о рюкзаке?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    В правильном решении dp[i][k][t] должно обозначать максимальную возможную стоимость объектов, среди превых i, такое что суммарная энергия и время у них t и k. Или -inf, если такое набрать невозможно.

    Пересчет: dp[i][k][t] = max(dp[i-1][k][t], dp[i-1][k-K[i-1]][t - T[i-1]]) (второй вариант считаем, только если k>= K[i-1], t>= T[i-1].

    База: dp[0][0][0] = 0, dp[0][k][t] = -inf.

    Ну и ответ - max_{k, t} Dp[n][k][t].

    Раз надо выводить и сами объекты, то надо еще запоминать, откуда был переход, т.е. еще один трехмерный массив bool, Где вы будете хранить True, если пересчитали через + x['v'].
    Ответ написан
    Комментировать
  • Как правильно написать partition?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    https://en.m.wikipedia.org/wiki/Quicksort
    Смотрите секцию algorithm. Там аж 2 варианта с объяснением и кодом.
    Ответ написан
    Комментировать
  • Не могу решить задачу на C?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Если проблема только с тем, что у вас циклов слишком много, то можно 3 последних объединить в 1.

    Вы при каком условии должны числа дописывать в ответ? Пока есть число хоть в одном из двух массивов.
    Вот и получается:
    while (i < M || j < N)
    Но внутри уже чуть побольше случаев. Можно просто ваши же условия объединить. Если выполняется условие первого цикла - делаете тело первого цикла. Иначе, проверяете условие второго цикла, делаете его, иначе - тело третьего цикла.

    Но можно знатно сократить код, если просто расписать все варианты, когда вы берете число из A. В противном случае, очевидно, берется число из B. Число из A берется, если оно есть и оно "лучше" числа из B - или B вообще нет, или A < B:
    if (i < M && (j == N || A[i] < B[j])) {
      C[k++] = A[i++];
    } else {
      C[k++] = B[j++];
    }
    Ответ написан
    4 комментария
  • Как это посчитать?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Проще всего двигать элементы по одному, справа-налево. Элемент можно сдвинуть, если справа стоит 0 или такой же элемент. Поддерживаем инвариант, что все элементы правее current уже сдвинуты и уплотнены до предела. Двигаем текущий пока можем. Чтобы не было циклов не двигаем нули.
    int n = a.size();
    int current = n-1;
    while (current >= 0) {
        while (a[current] > 0 && current < n-1 && 
              ((a[current+1] == a[current]) || (a[current+1] == 0))) {
          a[current+1] += a[current];
          a[current] = 0;
          ++current;
        }
        --current;
    }
    Ответ написан
    5 комментариев
  • Что означает n0 k0 в алгоритме Kingdom Division hackerrank?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Тут считаются 2 динамических программирования: 1) Сколько вариантов раскрасить поддерево так, что ни одна вершина не изолирована. 2) Сколько вариантов раскрасить поддерево так, что ни одна вершина кроме корня не изолирована, а корень изолирован.

    Считается снизу вверх, в "стеке" получаются вершины для которых значения уже подсчитаны - изначально листья. n, k - это как раз значения ДП в текущей вершине и в отце. текущей вершины.

    В структуре tree для каждой вершины хранится 2 объекта. Под индексом 0 - пара значений дп, под индексом 1 - список соседей в дереве.

    next получается значение этой структуры для отца, cur - для текущей вершины.
    Ответ написан
    3 комментария
  • Почему в алгоритме нахождения числа перестановок ищется сумма по модулю 2?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Тут считается динамическое программирование f(i,j) - количество перестановок из i элементов с j инверсиями.

    База: F(0, 0) = 1, F(i, j) = 0
    Переход: F(i,j) = sum_t=0..min(j, i-1) F(i-1, j-t)

    Тут мы берем все перестановки из i элементов и группируем их в зависимости от того, где стоит максимальный элемент. Этот максимальный элемент добавляет t - от 0 до min(j, i-1) инверсий. Если мы его выкинем, останеся перестановка из i-1 элемента и, чтобы полная перестановка имела j инверсий, эта урезанная должна иметь j-t.

    Оба кода хранят только одну последнюю строку и пересчитывают ее через сумму на предыдущей итерации.
    Ведь
    F(i,j) = F(i-1, j-i+1) + F(i-1, j-i+2) +... + F(i-1, j)
    F(i,j-1) = F(i-1, j-i) + F(i-1, j-i+1) +... + F(i-1, j-1)
    Вычтя второе уравнение из первого получаем: F(i,j) -F(i,j-1) = F(i-1, j) - F(i-1, j-i). Или F(i,j) = F(i-1, j) - F(i-1, j-i) + F(i,j-1). Это ровно формула в первом решении.

    В первом коде A - это вычесляемая текущая строка, B - копия предыдущей строки.
    Во втором коде s - это текущая строка и следующая вычесляется прямо в этом же массиве. В переменной ss поддерживается сумма F(i-1,j-i+1)+..+F(i-1, j-1).

    Ответ к задаче - это F(n, k)+F(n,k-2)+F(n,k-4)+...+F(n, k %2), потому что за каждую операцию мы или делаем +1 или -1 к количеству инверсий. Можно сколько-то раз сделать +1 -1, а потом сделать сколько осталось +1 и мы получим перестановки с инверсиями от 0 до k но той же четности, что и k (потому что каждая -1 вместо +1 уменьшает количество инверсий на 2).
    Ответ написан
  • Почему 8 в формуле hackerrank city?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это формула просто уже причесана и разложенна на множители. Это 12Y+8 (не X, кстати) идет в слагаемом (12Y+8)*(X+Y*Ai)

    8 там - это 4*2. 4 дерева и 2 новые вершины. Подробнее ниже.

    Как подсчитать все расстояния? Давайте отдельно посмотрим на те, которые внутри копии из 4 деревьев. Это даст нам слагаемое 4*Answer. Теперь подсчитаем те, которые идут между двумя разными деревьями. Их можно рзабить на 2 части - куски среди 5 новых ребер длины Ai и куски внутри деревьев. Вот эти куски внутри деревьев они все будут из угла, которым дерево крепится к остальным. Поэтому нам надо считать вот эту вот сумму расстояний от угла дерева (X).

    Новые ребра посчитаем отдельно. В скольки путях каждое ребро будет присутствовать? Это надо перемножить количество вершин с одного конца ребра на количество вершин с другого конца. Ведь из каждой из первых есть путь во вторые, проходящий через данное ребро. Для 4-ех новых ребер размеры кусков будут Y и 3Y+2. Вот мы получили 4*Y*(3Y+2)*Ai. Вот тут если 4 внести внутрь мы получим вот это самое 12Y+8 из вопроса. Для одного ребра размеры будут 2Y+1 и 2Y+1. Вот мы получили слагаемое (2Y+1)^2*Ai.

    Дальше надо посчитать, сколько раз каждый кусок в дереве из угла пойдет в ответ из путей между деревьями. Опять же, ровно столько раз, сколько вершин можно взять в качестве другого конца. Таких веришин 3*Y+2 - в любом из трех остальных деревьях или 2 новые вершины. Но эти куски в каждом из 4 деревьев, поэтому надо домножить на 4. Это дает нам слагаемое 4*X*(3Y+2). Тут тоже вылезает 12Y+8.

    Вот и получается формула там.
    Чтобы пересчитать Y, понятно что надо умножить на 4 и прибавить 2. 4 дерева 2 новые вершины.

    Вот с X по сложнее. Во-первых. там могут быть пути внутри одного дерева. Получаем слагаемое X. Во-вторых, надо посчитать, сколько раз каждое из новых ребер войдет в ответ. Ребро у дерева с углом с одной стороны имеет ровно одну вершину конец - угол. С другой может быть в любом дереве или в одной из 2 новых вершин. Поэтому получаем слагаемое (3Y+2)*Ai Ребро между новыми вершинами с одной стороны может кончатся в любом из 2 деревьев или в новой вершине. Получаем (2Y+1)*Ai. Оставшиеся 3 ребра ведут только в одно дерево и дают 3*Y*Ai.

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

    Куски путей внутри корневого дерева - это всегда диаметр дерева Z который идет рвоно столько раз, сколько там других вершин в дереве (3Y+2). Получаем Z*(3Y+2).

    Если все сложить и причесать, получим ответ в статье. Возможно там чуть другая логика вывода была, но суть решения такая же. Аккуратно считаем все пути. Чтобы это было проще все пути можно разбить на группы: внутри дерева, между двумя разными, и еще и на части: часть в дереве и часть в новой серединке. И главный инструмент: ребро встречается в сумме путей ровно столько раз, сколько путей через него проходит, а это произведение размеров подграфов с двух концов ребра.
    Ответ написан
  • Какая функция (или набор разных ф-ий) изменения "мощности" цвета света при распространении луча?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Это называется яркость света. Цвет лазера особо не меняется. Наверно, можно считать, что яркость уменьшается очень медленно линейно из-за рассеивания воздухом. Для не лазерных источников света яркость убывает квадратично от расстояния.
    Ответ написан
  • Как "выпрямить" кольцевой буфер c ограниченной доп.памятью?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Ваша задача - сделать циклический сдвиг массива на k позиций влево на месте, с O(1) дополнительной памяти.
    Вот код:
    void ShiftLeft(std::vector<int> &a, int k) {
      int n = a.size();
      int cycles = std::gcd(n, k);
      for (int start = 0; start < cycles; ++start) {
        int tmp = a[start];
        int i = start;
        while (true) {
          int next = i + k;
          if (next >= n) next -= n;
          if (next == start) break;
          a[i] = a[next];
          i = next;
        }
        a[i] = tmp;
      }
    }


    Работает это так: на место элемента вставет элемент на k позиций правее. Возьмем первый элемент, запомним его в tmp, поставим на его место тот, кто там должен быть. Освободилось место, поставим на него опять того, кто там должен быть и так далее. Рано или поздно мы вернемся к первому элементу. Но там уже стоит второй. Тут можно выйти из цикла и поставить на нужное место тот, кого мы сохранили в tmp. Но мы могли обойти не весь массив, как, например в случае n=6, k=2. Начав с 0 мы тут подвинем элементы 0,2,4, но не 1,3,5. Всего будет циклов gcd(n, k), и они все идут со сдвигом 1. Поэтому можно начинать с каждого из нескольких первых элементов.

    Додуматься до этого можно так: сдвиг на 1 позицию понятно как циклом while сделать-то и одной переменной tmp. А на несколько? Надо только заметить что элементы разбиваются на циклы.
    Ответ написан
    7 комментариев
  • Как обяснить в алгоритме инверсии?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Инверсия тут - это из комбинаторики. Инверсия - это когда 2 элемента не в том порядке. Количество инверсий - это сколько пар элементов стоят не так. В массиве (1,2,3,4) инверсий 0. В массиве (1,4,3,2) инверсий 3: 4 и 3, 4 и 2, 3 и 2 - вот эти 3 пары идут по убыванию, вместо нормального порядка. Оставшиеся 3 пары стоят как надо.
    Ответ написан
  • Поиск куда можно добраться по графу за время?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Если граф не взвешанный, то запустите обычный bfs, только не кладте в очередь вершины с расчтоянием больше ограничения. Если граф взвешанный, то запустите обычного Дейкстру, только остановитесь, когда зафиксируете вершину с раччтоянием больше допустимого.
    Ответ написан
    Комментировать