Ответы пользователя по тегу Алгоритмы
  • А как предков вывести?

    Alexandroppolus
    @Alexandroppolus
    кодир
    здесь никакой bfs не нужен.

    Стартовое число в итоге будет повернуто на 0, 1, 2 или 3 вправо (это разница поворотов вправо и влево). То есть возможны 4 стратегии. Тебе надо сравнить 4 различных сдвигов исходного числа, посчитав для каждого сдвига суммарную стоимость преобразований.

    например,
    A = 2573
    B = 4164

    нулевой сдвиг дает стоимость действий 1 и 2: (4-2) + (5-1) + (7-6) + (4-3) = 2 + 4 + 1 + 1 = 8, плюс ещё надо здесь прикинуть оптимальную стратегию разворотов и посчитать, сколько их будет.

    сдвиг на 1 вправо (стартовое число 3257) по действиям 1 и 2 выходит (4-3) + (2-1) + (6-5) + (7-4) = 6, и снова надо прикинуть развороты.

    определив таким образом оптимальную - самую дешевую - стратегию (т.е. определив, насколько в итоге будет повернуто исходное число), выстраиваешь цепочку переходов.
    Ответ написан
  • Как решить задачу на алгоритмы?

    Alexandroppolus
    @Alexandroppolus
    кодир
    если букв и особенно цифр очень много, то можно оптимизировать:
    1) Для каждой стороны получить массив точек с цифрами и отсортировать по расстоянию от левого края или от верха.
    2) Далее для каждой буквы проверять каждую из 4 сторон. При проверке стороны находить на этой стороне цифру, ближайшую к букве, например двоичным поиском, и уже смотреть расстояние до этой цифры. Далее сравнивать результаты для каждой из сторон, выбирать минимум.
    Ответ написан
    2 комментария
  • Как можно реализовать алгоритм замены подстроки в строке?

    Alexandroppolus
    @Alexandroppolus
    кодир
    Две идеи. Как применить, пока не очень понятно.
    1) вместо строки использовать двусвязный список символов. Это поможет делать замены более экономно, не растрачивая память и не сдвигая толпу символов. Хотя, если строки В и С одинаковой длины, можно и массивом обойтись, но это частный случай, не думаю что надо с ним возиться.
    2) сделали первый обход с заменами. Теперь новые вхождения заменяемой строки надо искать не по всей получившейся строке, а только там, где были замены (в районе левого и правого краев вставленной строки; так же условие гарантирует, что В не является подстрокой С). Точнее, даже так: сначала просмотреть строку А, найти (средствами стандартной библиотеки) все вхождения В и поместить их в очередь, потом перегнать строку А в двусвязный список, и далее по принципу обхода в ширину - берем из очереди позицию для замены, делаем замену, находим новые позиции замены (одну или две), добавляем в очередь, тут ещё проверить, что эти вновь добавленные позиции ни с кем не пересекаются..

    Да, этот способ не позволяет сократить число замен, но это уже лучше, чем на каждом этапе заново искать позиции.

    Дальнейшее ускорение - как то сократить число замен, поскипав промежуточные и вычислив результат, но тут много кейсов, и навскидку сказать трудно.
    Ответ написан
  • Можно ли быстрее чем за O(N) подсчитать сумму S(N,K,M) = sum i=0..N K*i%M?

    Alexandroppolus
    @Alexandroppolus
    кодир
    Мысли вслух.

    К наблюдениям ещё можно добавить довольно кэпский поинт K < M, думаю понятно почему.

    Если К "маленькое", например меньше корня из N, то у нас тут мало прогрессий и они довольно длинные. Границы прогрессий и "точки приземления" можно искать с шагом не менее sqrt(N) - делаем такой шаг, потом в его окрестности за О(1) отыскиваем границу, - итого сложность не более O(sqrt(N)).

    Вот что делать для "больших" К, пока не совсем понятно...
    Ответ написан
    Комментировать
  • Как написать код, где надо узнать в каком диапазоне число(без if else)?

    Alexandroppolus
    @Alexandroppolus
    кодир
    запихнуть нижние границы (начиная с 50) в массив и обойти его циклом, пока очередная нижняя граница не станет меньше или равна числу.
    кстати, если бы диапазонов было не 6, а дохренища, то лучше бинпоиском.
    Ответ написан
    3 комментария
  • Как решить задачу линейным алгоритмом?

    Alexandroppolus
    @Alexandroppolus
    кодир
    Это задача про однократную покупку/продажу акции. Решается за один проход, просто надо помнить текущий максимум aj/ai, и минимальное ai (чтобы на него делить очередное значение), и соответственно индексы, при которых эти рекорды были достигнуты.

    почему в первом тесте ответ 2 5, а не 1 4
    индексы здесь начинаются с 1, а не с 0.
    Паскальщик составлял.
    Ответ написан
    3 комментария
  • Как решить задачу 6 kyu Duplicate Encoder?

    Alexandroppolus
    @Alexandroppolus
    кодир
    там перед @ вообще-то стоит пробел. Замени его на скобку, тогда попустит.
    Таки да, пробелы - это тоже символы.
    Ответ написан
    Комментировать
  • Объясните, пожалуйста, принцип работы алгоритма из задачи про самый дешевый путь?

    Alexandroppolus
    @Alexandroppolus
    кодир
    Суть в формуле для стоимости достижения ячейки [i][j]:

    cost(i, j) = a[i][j] + min(cost(i, j - 1), cost(i - 1, j));

    А всё потому, что в [i][j] можно прийти только из [i][j-1] или из [i-1][j]

    Алгоритм последовательно меняет значения a[i][j] на их стоимости, используя тот факт, что на момент заполнения стоимости для a[i][j], уже заполнены стоимости для обоих предшествующих ячеек.

    Это "динамическое программирование".

    Только во второй строке второго цикла (который заполняет стоимости для левого столбца и верхней строки) есть баг . Её надо бы отдельным циклом.
    Ответ написан
    1 комментарий
  • Какова сложность алгоритма?

    Alexandroppolus
    @Alexandroppolus
    кодир
    В лучшем случае O(N), в худшем O(N^2)

    Если сделать по нормальному, всегда будет O(N)
    Ответ написан
    2 комментария
  • Как правильно пропарсить лабиринт в граф?

    Alexandroppolus
    @Alexandroppolus
    кодир
    Похоже, тут обычный поиск в ширину. Сначала находишь первую вершину (просмотреть первую строку, потом вторую и т.д., первая попавшаяся звездочка будет поворотом или тупиком). Ну а далее все соседние звездочки - это соседние вершины, либо пути в соседние вершины (то есть в каждую сторону идешь прямо, пока встречаются "транзитные" звездочки, а именно ограниченные решетками или краями карты с двух противоположных сторон, и подсчитываешь длину пути).
    Если в лабиринте только одно пространство, то обойдешь всё. Иначе надо после завершения обхода в ширину снова искать неотмеченные вершины.
    Ответ написан
    Комментировать
  • Почему вставка элементов занимает такое время?

    Alexandroppolus
    @Alexandroppolus
    кодир
    в массивах надо сдвинуть все элементы, которые будут после вставляемого. А в списках подразумевается, что у тебя уже есть ссылка на элемент списка, после которого надо вставить новый элемент
    Ответ написан
    1 комментарий
  • Как нормализовать растянутые данные не линейной нормализацией?

    Alexandroppolus
    @Alexandroppolus
    кодир
    Если тебе надо "увеличивать маленькие значения", то можно использовать какую-нибудь выпуклую функцию для каждого значения, например кубический корень. Ну и потом, в конце, всё равно понадобится четвертая формула, дабы впихнуть всё в отрезок [0, 1]

    Или даже так: сначала линейно нормализовать по четвертой формуле, а потом применить некоторую функцию F, возрастающую и выпуклую на отрезке [0, 1], такую что F(0)=0, F(1)=1. Например кубический корень.
    Ответ написан
    Комментировать
  • Как сгенерировать наиболее разнообразные комбинаций из элементов заданного набора множеств?

    Alexandroppolus
    @Alexandroppolus
    кодир
    Рандомно перемешать каждый из массивов - https://qna.habr.com/q/1118198
    после чего брать комбинации: (a[0], b[0], ..., f[0]), (a[1], b[1], ..., f[1]), ...
    где a, b.. - слои

    если, допустим, надо N тайлов, а в слое всего M вариантов, где M < N, то из этого слоя (перемешанного) можно брать' элемент с индексом (i % M)
    Ответ написан
    Комментировать
  • Почему моё решение данной задачи неправильное?

    Alexandroppolus
    @Alexandroppolus
    кодир
    В твоем решении x2 и x3 должны быть простыми числами, причем x2 >= 1+d, x3 >= x2+d.

    Ну и весь прикол задачи - найти два таких простых числа. Скорее всего, надо предварительно построить таблицу с набором простых чисел. Это либо отсортированный массив оных, где можно искать двоичным поиском, либо массив, где a[i] = (минимальное простое, большее или равное i), с поиском за O(1). В любом случае, максимальное простое число, которое тебе вообще может понадобится, не больше чем 20200, так что много байтов это дело не займет. Ну и само собой, для создания подобного словаря можно воспользоваться решетом Эратосфена или чем-то подобным.
    Ответ написан
    1 комментарий
  • Как решить задачу про кузнечика путем динамического программирования?

    Alexandroppolus
    @Alexandroppolus
    кодир
    Кузнечику обязательно побывать на последней кувшинке?
    Если нет (если можно её проскочить), то сделай в конце cout << max(a[N-2], a[N - 1]);
    Ответ написан
  • Алгоритм Евклида?

    Alexandroppolus
    @Alexandroppolus
    кодир
    если a < b, то a%b всегда равно a
    Ответ написан
  • Из какой коллекции можно быстро удалять элемент, но к ней применим бин. поиск?

    Alexandroppolus
    @Alexandroppolus
    кодир
    Написать своё сбалансированное дерево. Удаление и upperBound будут за логарифм
    Ответ написан
    Комментировать
  • Как еще чуть ускорить алгоритм?

    Alexandroppolus
    @Alexandroppolus
    кодир
    Путь действительно странный. А главное, есть какие-то непонятные действия с массивом, которые, возможно, приводят к копированию, например result_arr = result_arr + know_range(number)

    Проще всего было бы из строки получить массив с возрастающими ненулевыми интервалами, а потом пройтись по нему справа налево и "посрезать уголки":

    строка "5 3 0 4 6 1 5 0 9 2 3 0"
    массив после первого обхода: [inf, inf, 0, 1, 2, 3, 4, 0, 1, 2, 3, 0]
    после обратного обхода, тот же массив: [2, 1, 0, 1, 2, 2, 1, 0, 1, 2, 1, 0]
    Ответ написан