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

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

    Но если вам так надо, заведите функцию, которая вырезает квадрат с заданными координатами и размерами (и в двух вложенных циклах по i и j от 0 до 2 запускайте ее от координат (3*i, 3*j).

    Функция заводит массив нужного размера и для всех i,j копирует в ячейку [i,j] значение из большой матрицы из ячейки [i+offset_x, j+offset_y].
    Ответ написан
    Комментировать
  • Как реализовать определённые функции в кликере?

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

    Для этого отправляйте раз в секунду все действия пользователя на сервер (клики, нажатия кнопок покупок бонусов). Сервер должен повторить всю логику (прибавить клики, автоматические таймеры, включить всякие бонусы, если очков хватает) и отправить назад результирующие очки пользователя к той секунде. Клиент должен при отправке запомнить, сколько у него было очков и при получении ответа сравнить его с тем, что получил от сервера. Если есть расхождение то разница прибавляется к текущему количеству очков.

    Т.е. вся логика на клиенте, но она продублированна и проверяется на сервере (например, проверка, что нет 10^20 кликов за секунду, что очков хватало на покупку апгрейда).

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

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

    Если же вы хотите какую-то формулу или логику спрятать исключительно на сервере, то без задержек тут ничего не сделать.
    Ответ написан
    Комментировать
  • Существует ли алгоритм выведения неизвестного из формулы?

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

    Системы символьной алгебры грубо говоря умеют кучу частных случаев. Типа туда забита формула решения линейных и квадратных уравнений.

    Судя по всему, ваша задача - весьма частная. Если формула может быть только произведением величин в каких-то степенях, то алгоритм вы уже описали - перенести все лишнее в другую сторону и взять корень нужной степени.
    Ответ написан
    Комментировать
  • Как праильно определить лотерейные билеты в соответствии с условиями задачи?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    И меня не устраивает "единственный" проблемный отрывок кода:
    if ndata[i] % 2 != 0 and nf % 2 != 0: lucky += 1

    Там вообще какой-то бред написан. При чем тут проверка на четность вообще?!

    Вам надо подсчитать солько чисел из trda есть в ndata и вывести Lucky, если насчитали хотя бы 3 (перечитайте же условие задачи).

    Соответственно должно быть что-то вроде
    if nf == ndata[s]: cnt+=1
    ...
    if cnt >=3:  print('Lucky')
        else: print('Unlucky')


    Еще у вас вложенные циклы по одной и той же переменной i, может в питоне так и можно, но это обычно очень плохая идея.
    Ответ написан
    Комментировать
  • Как решить задачу?

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

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Если я правильно понял задачу, то надо подсчитать для каждого i
    sum_{j=1..n} (i%j?1:0) % 2.

    Или - есть n ламп в ряд изначально не горящих. Переключаются каждая первая, каждая вторая, третья и т.д. Вопрос - а какие лампы горят в конце.

    Разверните условие. Не переключайте каждую 1-ую, 2-ую и т.д. лампу, а подсчитайте для каждой лампы, сколько раз она будет переключена (потому что переключать их все по одной - это медленно. Надо как-то агрегировать вычисления)?

    Лампа будет переключена ровно столько раз, сколько делителей у ее номера. Иными словами - вам надо понять, четное ли количество делителей у каждого числа. Вспоминаем, что любое число представимо в виде разложения на простые множители: p1^k1*p2^k2* ... pm^km. Можно подсчитать количество делителей - это будет (k1+1)(k2+1)...(km+1), ведь каждое простое число может входить в делитель в степени от 0 до ki включительно.

    Теперь, в каком случае это число будет нечетным? Только если все ki четные. А это значит, что число - полный квадрат (все степени четные же. Берем корень, делим степени пополам, получаем целое число).

    Итого ответ - проставить true в массиве по всем индексам i*i.
    Ответ написан
    Комментировать
  • Найти алгоритм подсчета количеств множественного перекрытия интервалов, а также длительность таких интервалов?

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

    Для всех интервалов добавить в массив точек пары {время начала, +1} и {время конца+1, -1}. Это массив точек - границ вакансий на оси времени (прибавляем 1 к времени конца, потому что последняя секунда включена в интервал). Потом сортируем этот массив. Теперь одиним проходом можно выделить из массива все отрезки времени и сколько на них было открыто вакансий.

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

    Для простоты советую сначла одним циклом выделить все отрезки и сложить их в отдельный массив (опять пара - длина отрезка, количество вакансий). Потом пройтись по массиву (или во время складывания) найти максимальное количество вакансий. Потом пройтись еще раз и просуммировать времена для всех отрезков с данным количеством вакансий.

    Еще можете посмотреть предыдущий ответ вашему товарищу по курсу: В чем ошибка в алгоритме поиска количества интервалов?
    Ответ написан
  • Как правильно получить отрицательный результат подстроки?

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

    Ваш код, например посчитает палиндромом строку "aab".
    Потом, тут еще зачем-то бинпоиск присобачен. Зачем, вообще непонятно.
    И еще ваше решение слишком медленное. Тут сложность порядка O(n^2 log n), что для 200000 ни в какие ограничения не влезет.

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

    решение

    Надо проверить, есть ли 2 подряд идущих одинаковых символа. Если есть - лексикографически минимальная такая пара - ответ.
    Иначе, надо проверить, есть ли тройка символов, где первый равен третьему. Из всех таких надо выбрать лексикографически минимальную.
    Если и таких нет, то ответ "-1".

    Задача решается за 2 не вложенных цикла.
    Ответ написан
    Комментировать
  • Что я не правильно делаю в тестовом задании?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Ответ написан
    Комментировать
  • Алгоритм пропуска числа?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это обобщение известной задачи, где пропущено одно число. Там можно, например, вычесть все числа из 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.

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Быстрое решение - построить для этого массива суффиксное дерево алгоритмом Укконена (или вот ссылка), потом обойти его, найти самую глубокую вершину, у которой есть более одного ребенка, и вывести путь до нее от корня. Работает за O(n).

    Edit:

    Вообще есть много решений разной заумности и скорости. Самое быстрое - за линию - я привел выше. Следующий уровень - за квадрат, через z-функцию (но пишется и понимается проще суффиксного дерева). Для каждого суффикса вашего массива найдите максимальное значение z-функции.

    И еще проще, но уже за куб - переберите любые 2 позиции и потом одним циклом считайте, сколько символов с этих позиций совпадают.
    Ответ написан
    3 комментария
  • Как преобразовать слова?

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

    Решается так:
    1) Проверить, что строки равны. Это особый случай
    2) Проверить, что длина одинаковая?
    3) Завести мап символ->символ, пройтись по строкам параллельно и записывать мап[строка1[i]] = строка2[i], если там пусто. Иначе - проверить, что там уже записано то же самое.
    4) Проверить, что различных символов во второй строке меньше 33. Можно с помощью сета, который наполняется в том же цикле, что и в шаге 3.
    Ответ написан
    5 комментариев
  • Как разделить все точки на плоскости на пары с минимальным расстоянием?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    После сведения к теории графов есть решение за O(n^3) через венгерский алгоритм (реализация) или через алгоритм посика максимального потока минимальной стоимости (Там реализация, медленнее венгерского метода. Вот решение за n^3, но код готовый я не нашел).

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

    А это уже есть задача о назаначении на матрице расстояний между всеми парами точек: Надо в каждой строке выбрать ровно один элемент так, чтобы в каждом столбце был ровно один элемент и сумма была минимальной.


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

    Пример
    3 вершины (0, 0), (1, 0) и (0, 1).
    Матрица расстояний (с 1e90 на диаганали вместо 0):
    ((1e90, 1, 1),
    (1, 1e90, 1.414),
    (1, 1.414, 1e90)).

    Решение ценой 3.414 (3-ий элемент в 1-ой строке, 1-ый во 2-ой строке и 2-ой в 3-ей)
    ((*, *, 1),
    (1, *, * ),
    (*, 1.414, *)).

    Это значит, что вы берете пары 1-3 2-1 3-2.
    Ответ написан
    Комментировать
  • Как составить алгоритм слияния и разложения двух чисел?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Невозможно решить вашу задачу. У вас 65535*255 вариантов входных данных и по условию они должны выдавать разные значения. Итоговое количество чуть не дотягивает до 2^24 - а значит в 16 бит его никак не засунуть.
    Ответ написан
    Комментировать
  • Какова реальная сложность данного алгоритма?

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

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Один момент меня смущает: зачем вы внутри DFS не вызываете cycle когда у вас есть ребро в p? Это цикл длины 2 - вполне нормальный цикл. Или по условию задачи такие надо исключить?

    А главная ошибка - надо при выходе из dfs помечать вершину другим цветом - как обработанную (например, 2). Чтобы color == 1 только у вершин, которые в стеке. При этом в самом Dfs нужно рекурсивно вызываться только отвершин с color == 0.

    Допустим, у вас в графе есть ребро 2->1 и все. Вы вызоветесь от вершины 1 в цикле в main, ничего не найдете. Потом вызоветесь от вершины 2, найдете ребро в уже обработанную вершину и среагируете на это, как на цикл. Хотя это не цикл.
    Ответ написан
  • Тестер алгоритма?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Эм... Вам надо читать данные из входного файла (в задаче это 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() к элементам.
    Ответ написан
    1 комментарий
  • Задачи с минимальными и максимальным вариантами и неравномерными выборками?

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

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вы правильно решили отсортировать концы отрезков, но эвристика с +-1 в виде второго параметра сортировки у вас не работает. Похоже там и есть ошибка. Попробуйте тест, "6 100 102 100 102 100 102 102 104 102 104 102 104". Ответ должен быть - 1 отрезок длиной 1 (там 6 вакансий в 102-ой секунде). Другой интересный тест "6 100 102 100 102 100 102 103 104 103 104 103 104". Тут ответ 1 5 (3 вакансии).

    Проблема в том что такой подход с сортировкой работает, если границы отрезка - точки на прямой. У вас же в задаче границы отрезка - это секунды.
    Я бы прибавлял 1 к концам отрезков и считал границы точками на числовой прямой.

    Далее, я бы разделил код выделения отрезков и поиска максимума.
    У вас очень сложная логика и там может быть ошибка. Сложно за всем уследить.
    По памяти у вас вроде бы проблем нет - ну заведите еще один массив, куда будете складывать {количество вакансий, длина отрезка}. Складывайте туда только отрезки с разным количеством вакансий. Потом (или во время складывания) найдите там макимальное количество вакансий. И последним проходом подсчитайте сумму и количество элементов в с заданным количеством вакансий.

    Что-то вроде этого (код на недо-жаве, поправьте сами):

    // class Segment: имеет length и count.
    // result - arrayList of Segment
    // arrayList содержит MyClass отсортированные по X границы отрезков (Y= +1 для начала и -1 для конца. Концы отрезков имеют сдвинутую на +1 X).
    
    prev_x = arrayList[0].GetX();
    cnt = 0;
    for (MyClass mc : arrayList)  {
      cur_length = mc.GetX() - prev_x;
      // рассматриваем отрезок (prev_x, mc.GetX()), не включая границы-точки!
      // Поэтому GetY() прибавляем в конце!
      // пропускаем отрезки нулевой длины - они из-за совпадающих точек и смысла не несут
      if (cur_length > 0) {
       //  новый отрезок добавляем, только если разное количество вакансий.
       if (result.size() == 0 || result[result.size() - 1].cnt != cnt) {
        result.add(new Segment(cur_length, cnt);
       } else {
          result[result.size()-1].length += cur_length;
       }
       cnt += mc.GetY();
       prev_x = mc.GetX();
    }
    max = 0;
    for (Segment s : result) {
      if (s.cnt > max) max = s.cnt;
    }
    length = 0;
    total = 0;
    for (Segment s : result) {
      if (s.cnt == max) {
        length += s.length;
        total += 1;
      }
    }
    
    // print total length.
    Ответ написан
  • Нужны ли алгоритмы с графами в региональном этапе по программированию?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Да, могут быть нужны. Про то, что ограничения порядка 10^5 - это не факт. Может быть и задача, где ограничения меньше, а решение сложнее.

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

    Далее, что за дерево отрезков на графе?! А еще дейкстра может быть написан за (n+m)logn. И форд-беллман работает за nm, а не n^2.
    Ответ написан
    4 комментария