Задать вопрос
  • Как выбрать начальное число (задача по бинарному поиску)?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Тут мало выбирать только первое число и гнать обычный бинарный поиск. Важное ограничение - вы не можете использовать один и тот же цвет дважды. Есть еще спецэффект, что случаи c=n-1 и с=n можно разделить только перекрасившисть с 1 на n или наоборот. Т.е. вы не имеете права краситься в 1 или n-1, только если не знаете точно, что C меньше n или что С одно из двух крайних значений.

    Нужно придумать какой-то паттерн, как компактно расположить все запросы в промежутке от 1 до n без повторений.
    Ответ написан
    Комментировать
  • Как работает ограничение скорости в роутере при раздаче по wifi?

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

    В целом, роутер считает, сколько байт он пропустил, и если видит, что байт слишком много в еденицу времени, лишние пакеты просто дропаются (отбрасываются без пересылки их дальше). А дальше уже источник трафика как-то подстраивается. Если трафик TCP - то отправитель замечая потери будет снижать скорость отправления пока потери не прекратятся. Если же используется UDP, и приложение не надстроило над ним каких-то rate-control механизмов, то так и будет посылать лишние пакеты, которые будут уничтожатся роутером. До него трафик будет без ограничения скорости, а дальше пойдет уже ограниченный.
    Ответ написан
    Комментировать
  • Как быстрее получить множество точек, входящих в прямоугольник?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Обычное k-d дерево, как по ссылке у freeExec тут будет работать неплохо и будет потреблять сравнительно мало памяти. Но оно не дает гарантию времени выполнения. Может так получится, что вы обойдете почти все вершины в дереве (то же O(n), n - количество точек), даже если в прямоугольник не попала ни одна точка. Правда для этого нужно иметь весьма специфическую конфигурацию точек и очень прямоугольник с большим периметром. Я думаю, этот вариант вам лучше всего подходит, если точки более менее случайно разбросаны и экран занимает лишь маленькую, более менее квадратную область.

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

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

    Дерево отрезков, оно же segment tree - это структура данных, которая делит все пространство координат на половинки, пока не получит в листах по одной координате.

    Дерево поиска - это сбалансированное двоичное дерево поиска. Типа avl, красно-черных или декартовых деревьев. Возможно стандартный Set из JS или его аналог тут подойдет.

    Суть решения такая - вы разбиватете все пространство по одной координате (скажем, y) деревом отрезков. Каждая вершина этого дерева отвечает за некоторую горизонтальную полосу c фиксированными y координатами и ханит в себе Set всех точек, которые в эту полосу попадают. В Set храните какие-то ссылки на точки (допустим, их id в массиве всех точек), упорядоченные по x координате, а потом по y координате, а потом по id.

    Это фактически 2D дерево отрезков, но наивная реализация требовала бы MaxW*MaxH памяти, что слишком много. Замена внутренних деревьев отрезков на Set позволяет сильно сэкономить в памяти.

    При добавлении/удалении точки надо в дереве отрезков найти все вершины, которые покрывают ее y координату (их будет Log MaxH) и в их сетах удалить/добавить вершину с заданными (x,y) координатами.

    Важно, что set упорядочен по x координате, не той же по которой упорядочено дерево отрезков.

    Для получения всех точек в прямоугольнике стандартным обходом дерева отрезков найдите log(MaxH) вершин покрывающих прямоугольник по y координате. Теперь для каждого из найденных Set() найдите upper_bound левой границы. Теперь обойдите точки в Set, начиная с этой, пока не выйдете за правую границу прямоугольника и рисуйте их.

    Эта структрура данных найдет все точки в прямоугольнике за O(k + log(MaxW) * log N), где k - количество точек в прямоугольнике, MaxW - высота пространства, N - общее количество точек. При этом каждая точка будет хранится ровно log(MaxW) раз, т.е. по памяти эта структура данных не такая и прожорливая - O(n log(MaxW)).

    Единственная проблема: похоже стандартный Set в JS не умеет делать upper_bound. Если точки не меняются часто, то можно вместо Set хранить массив точек отсортированный по x и бинарным поиском искать левую границу при обходе прямоугольника. Иначе же используйте вместо Set более продвинутую реализацию дерева поиска, которая поддерживает upper_bound. Возможно даже есть что-то стандартное в JS или есть готовые библиотеки - я не специалист.
    Ответ написан
    Комментировать
  • Как обойти граф не зацикливаясь на связи одного узла с другим?

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

    В этом случае надо, как вы и предположили, хранить массив "посещенности" домов. Можно совместить его с массивом-ответом или статусами домов. Ваш метод уже не принимает конкретный дом как параметр, а просто считатет для всех домов. Он изначально заполняет массив для всех домов и электростанций нулями, что значит, что электричества в доме нет. Потом выполняется DFS (обзод в глубину) или BFS (обход в ширину) от электростанций, которые активны. При этом все посещенные вершины помечаются 1 в массиве. В уже помеченные вершины вы не ходите, поэтому алгоритм незациклиться.

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

    Можно сделать гораздо быстрее. Если связи между домами только добавляются (но ни в коем случае не удаляются), то можно использовать систему непересекающихся множеств (DSU). Изначально каждый дом и электростанция - сами себе множество. В каждом множестве поддерживайте счетчик активных электростанций (изначально у домов - 0, у электростанций - 1). Это просто в реализации: у вас есть какой-то массив ссылок root, элеметы которого указывают сами на себя только в корне множества. Заведите второй массив, который будет по тем же индексам хранить счетчики для элементов. Точно также в вики по ссылке выше поддерживатеся rank.

    При добавлении провода вы должны слить 2 множества. При этом пересчитайте счетчик (прибавьте счетчик нижнего множества к счетчику верхнего множества).

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

    Это решение будет фактически работать за O(1) при каждом запросе и добавлении ребра (если использовать эвристику сжатия путей).
    Наивное же решение с полным обходом графа каждый раз было бы O(1) при добавлении ребра и O(n) при запросе.
    Ответ написан
  • Как максимизировать сумму элементов выбираемых из списка?

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

    Пересчет: f(i) = max(f(i-1), a[i-1] + f(i-k)) - тут мы или не берем последний элемент, и тогда ответ f(i-1) или берем - и тогда мы обязаны пропустить k-1 следующих элементов. База: f(i<=0) = 0.

    Можно сократить потребление памяти если считать в массиве снизу вверх и хранить только последние k элементов f[].
    Ответ написан
    Комментировать
  • В чем ошибка в коде, который расчитывает период Пизано?

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

    И, очевидная оптимизация - так как у вас fib() вызывается от увеличивающихся по порядку индексов, вы вместо функции делайте сразу же seq.push_back((seq[i-2]+seq[i-1]) % m);
    Ответ написан
    Комментировать
  • Как найти все возможные комбинации чисел от 1 до n-1 чтобы их сумма была равна n?

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

    Можно хранить список взятых чисел в глобальном массвие/списке. Но надо аккуратно его откатывать. Перед рекурсивным вызовом, если добавили новое число, то после вызова его из массива/списка удалите. Так будет потребление памяти O(n) вместо O(n^2).

    Что-то типа такого:
    void Generate(int n, int next, int sum, vector<int> taken) {
      if (next > n || sum > n) return;
      if (sum == n) {
       Output(taken);
      }
      Generate(n, next+1, sum, taken);
      taken.push_back(next);
      Generate(n, next+1, sum+next, taken);
    }
    
    ...
    
    Generate(n, 1, 0, {});


    Но это решение будет не самым быстрым - ибо оно будет заходить в длинные "тупики".

    Вариант 2 - оптимизированный перебор, который не перебирает ничего лишнего. Сначала, как в задаче о рюкзаке, при решении динамическим программированием, найдем все варианты набрать каждую сумму.

    Заведите двумерный массив n x (n+1). d[i][j] будет хранить, можно ли собрать сумму j используя числа от 1 до i.

    База - d[0][0] = true (нет чисел - ноль набрать можно), d[i][0] = false (нет чисел. Не ноль набрать нельзя).

    пересчет: d[i][j] = d[i-1][j-i] or d[i-1][j] (или берем текущее число или нет)
    Естественно, первый вариант рассматривается только если i<=j. Можно подсчитать этот массив или рекурсивной функцией с запоминанием или просто тупо двумя вложенными циклами.

    Потом модифицируем нашу рекурсивную функцию из первого варианта. Теперь она будет как бы идти с конца и параметры будут - сколько первых чисел мы можем использовать, какую сумму должны набрать и какие бОльшие числа уже взяли. В функции опять 2 варианта - или берем текущее число или нет. Но при этом смотрим в массиве d[][], а можем ли мы вообще набрать нужную сумму данными нам числами. Если нет - сразу возвращаемся. Когда пришли к оставшейся сумме в 0, выводим набранные числа.

    Оба решения имеют временную сложность O(2^n), но второе будет в несколько раз быстрее, потому что не перебирает никаких тупиков. Возможно, если еще подумать можно избваиться от динамического программирования и вообще вывести формулу, когда из чисел от 1 до i можно собрать заданное число k (может там формула типа i*(i+1)/2 <= k).

    Если у вас задача стоит не вывести все наборы (их много! Порядка 2^n), а подсчитать их количество, то тут не надо рекурсивного перебора, а можно подифицировать динамическое программирование, которое будет вместо true/false считать сколько способов собрать из i чисел сумму j. будет формула вида d[i][j] = d[i-1][j] + d[i-1][j-i]. Тогда все решение будет за O(n^2) по времени и можно сделать его O(n) по памяти, если немного подумать (и хранить только две или одну строку матрицы d).
    Ответ написан
    3 комментария
  • Какой у этого решения time и space complexity?

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

    В функции:
    - Выделяется новый массив: n операций
    - Вызывается функция для укороченного массива: F(n-1) операций
    - Цикл по всем перестановкам n-1 элемента: (n-1)! повторений
    - Вложенный цикл по позициям: n*(n-1)! = n! повторений
    - вложенное в циклы построение новой перестановки: n*n! операций

    Итого F(n) = n + F(n-1) +n*n!

    Можно раскрыть рекурсивно и получим:
    F(n) = 1 + 2 + 3 + ... + n + n*n! + (n-1)*(n-1)! + (n-2)*(n-2)! + ... +1
    Аккуратно посмотрев на это можно понять, что все члены, начиная от (n-1)*(n-1)!, cумарно меньше n*n!, а первые n членов вообще мизерные и их можно отбросить.
    В итоге, F(n) = O(n*n!).

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

    Сложность по памяти такая же - ведь вы там в итоге храните все перестановки, их n! и каждая занимает n. Но это оценка ассимптотики - O(n*n!). На самом деле будет чуть больше n*n! элементов, потому что хранится список ответ и список для меньших перестановок, плюс стек и промежуточные массивы при конкатенации.

    Это хорошая ассимптотика - для построения всех перестановок меньше нельзя.
    Однако, если вам не надо все перестановки хранить в памяти (да и для кэша, кстати) будет заметно быстрее генерировать следующую перестановку из текущей на месте, как описано тут. Хоть и с такой же ассимптотикой, этот алгоритм будет работать в несколько раз быстрее.
    Ответ написан
    Комментировать
  • Смысл и предназначение обычного бинарного дерева? Какова погрешность измерение времени программы при помощи Stopwatch'ера?

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

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

    Про stopwatch ничего не знаю, что это такое даже.

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    То, что вы внутри функции присваиваете int параметру, снаружи функции не видно (переменная передается по значению, а не по ссылке). Поэтому результат рекурсивных вызовов надо брать из возвращаемого значения, а не надеятся, что функция сама обновит tmpMaxValue.
    Ответ написан
    Комментировать
  • Как решить задачу с CodeWars Simple Fun #159: Middle Permutation?

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

    Вместо ceil(a/b) используйте (a+b-1)//b
    Вместо floor(a/b) или, когда делится без остатка используйте a//b

    В логике решения ошибки я не вижу.
    Ответ написан
    4 комментария
  • Как организовать такое поведение?

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

    Могу лишь дать пару советов по реализации.
    Пишите рекурсивную функцию которой передается оставшиеся не распределенные блюда и список уже готовых наборов (наборы из одного блюда - тоже наборы). Пытайтесь куда-то приспособить первое нераспределенное блюдо.

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

    Если же наборы могут быть больше или всего блюд многовато и надо бы побыстрее решать, то делайте следующее:
    Для каждого типа блюд заведите список наборов, в которые такой тип входит.
    В функцию передавайте блюда, сгруппированные по типам, и уже собранные наборы. Потом циклом перебирайте какой тип набора будете собирать с первым блюдом (у вас же есть список всех подходящих наборов) и вызывайте вторую рукурсивную функцию, которой передаются несобранные блюда, уже готовые наборы, какой тип набора собирается, и собранная часть текущего набора. Функция2 будет брать следующий неиспользованный тип в текущем наборе и, если блюда такого типа у вас есть, добавлять в цикле одно такое блюдо к набору и вызываться рекурсивно. Если весь набор собран, то рекурсивно вызывайте первую функцию.
    В первой функции, помимо перебора всех наборов, после цикла, просто берите первое блюдо как само себя.

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Это классическая задача о рюкзаке.

    Можно составить такое ДП: F(c, k) - максимальное количество страниц, которые можно набрать из первых k книг общей стоимостью ровно c.

    База: F(0,0) = 0, F(0,*) = F(*,0) = -infinity.
    Пересчет:
    F(c, k) = max(F(c-cost[k], k-1) + pages[k], F(c,k-1))


    Это ДП приведено в википедии, например. Ответ - максимум по всем c F(c,k).

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

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

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

    Во первых, можно забыть про заглушки, если требовать собрать ровно от N до 1.25N секций.
    Т.е. в вашем примере вам можно собрать от 300 до 400 секций.

    Теперь ваша задача в точности становится задачей о рюкзаке, количество секций в контейнере - это "длина" вещи из задачи о рюкзаке, а длина - это "цена".

    И вам надо, как в задаче о рюкзаке, набрать каких-то "вещей", т.ч. рюкзак заполнен от 300 до 400 и суммарная "цена" минимальна.

    Если контейнеров не много (до 20-25), то можно решать полным перебором: рекурсивной функцией перебираете сколько контейнеров каждого типа вы берете в ответ. Если суммарное количество секций выше 1.25N, то останавливаетесь. В конце, когда перебрали все контейнеры, если набрали от N до 1.25N секций, то сравниваете текущую длину с оптимальным ответом и запоминаете, если длина меньше.

    Довольно быстрое решение - через динамическое программирование. Заведите массив от 0 до 1.25N. В нем будет хранится минимально возможная длина для набора контейнеров с заданным количеством секций. Изначально заполните его -1, а в индекс [0] положите 0.0.

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

    // Container - структура содержащая длину length и количество секций sections.
    int maxn = n*5/4; // Округленное вниз целое число.
    vector<float> length(maxn+1, -1.0);
    length[0] = 0.0;
    vector<container> best(maxn+1);
    for (Container c: containers) {
      for(int i = 0; i < maxn; ++i) {
        if (length[i] < 0) continue;
        int j = i + с.sections;
        if (j <= maxn && (length[j] < 0 || length[j] > length[i] + c.length)) {
          length[j] = length[i] + c.length;
          best[j] = c;
        }
      }
    }
    int besti = -1;
    float bestlen = 100000000;
    for (int i = n; i <= maxn; ++i) {
      if (length[i] > 0 &&  length[i] < bestlen) {
        besti = i;
        bestlen = length[i];
      }
    }
    if (besti == -1) {
      cout << "Нет решения" << endl;
    } else {
      cout << "Минимально возможная длина: " << length[besti] << endl;
      cout << "Контейнеры:" << endl;
      while (besti > 0) {
        cout << best[besti].length << endl;
        besti -= best[besti].sections;
      }
    }


    Лучше, все-таки, если вы сможете задать длины целыми числами, например, в миллиметрах. Тогда не будет проблем с точностью. Это слегка адаптированный под вашу задачу стандартный алгоритм динамического программирования для задачи о рюкзаке. Погуглите, почитайте википедию. Там еще указаны различные аппроксимационные алгоритмы. Если у вас ОЧЕНЬ много секций (N>10^8) и данный алгоритм требует слишком много памяти, но вам пойдет и достаточно хорошее решение, пусть и не оптимальное, то используйте аппроксимационные алгоритмы.

    Если хотите изменить допустимые проценты заглушек - меняйте коэффициент 5/4 в коде.
    Важно: это решение предполагает, что все контейнеры допускают одинаковый процент заглушек.
    Решение уже ищет минимальное количество заглушек при минимально возможной общей длине.

    Edit: исправил код восстановления ответа - сначала забыл разобрать случай недостижимых состояний (-1 в массиве length)
    Ответ написан
    2 комментария
  • Какие есть достойные альтернативы жадному алгоритму (greedy)?

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

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

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

    Встретили открывающую скобку - положили ее позицию в стек. Встретили закрывающую - вынимаем последнюю позицию из стека. Кусок от этой позиции до текущей - ваш блок кода.

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

    Можно алгоритм усложнить, если надо какую-то проверку на синтаксис делать. Тогда вам придется, во первых, разбить текст на токены. Во вторых класть в стек всякие разные открывающие токены. Например, туда еще пойдут '[', '(' в С или "begin" в паскале. Потом при встрече любого закрывающего токена нужно проверить, что на вершине стека лежит правильный открывающий токен.

    Еще важно не забыть, что при некорректном входном коде у вас стек может кончится раньше времени. Например: "{a};}{". Тут, когда вы дойдете до второй скобки, у вас будет пустой стек. Это означает, что текст некорректен.
    Ответ написан
    Комментировать
  • Как решить задачу на or?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Есть решение, но оно на плохих тестах, если не повезет, не влезет в лимит.
    Чтобы вам повезло, можно "перемешать" входные данные случайным образом. Заведите случайную перестановку. Далее внизу я про нее как бы забуду, но когда я говорю спросить про элементы i и j вы должны справшивать про p[i] и p[j]. Как только вы найдете, что 0 в p[k] - про эту случайную перестановку можно забыть и далее использовать элемент p[k] для востановления перестановки.

    Спросите про элементы 0 и 1. Запомните a[0] | a[1].

    Вот у вас есть 2 элемента каких-то, вы знаете их позиции и a[i]|a[j]. Мы будет добавлять к ним элементы 2..n-1 по одному, все время выбрасывая один или несколько, в которых нуля точно нет.

    Вот есть у вас элеметы x, y и вы знаете a=x|y. возьмем новый элемент z и спросим b=y|z.

    Мог ли 0 быть в x? тогда бы a = x|y=0|y = y. Т.е. предыдущее значение a должно вкладываться в новое b как множество единиц. Аналогичный критерий для возможности z быть нулем - b вкладывается в a.

    Eсть 4 взаимоисключающих варианта, как множества бит a и b соотносятся:
    1) a целиком вкладывается в b, или a|b == b, a != b, например 5 вкладывается в 7.
    2) b целиком вкладывается в a, или a|b == a, a != b
    3) a == b
    4) ничего из выше перечисленного, например, 3 и 6.

    Мы уже становили, что x может быть 0 только в случаях 1) и 3). z может быть нулем только в случаях 2) и 3).

    В каких случаях может быть нулем y? только в 1), 2) и 4)

    Теперь алгоритм, если выпал случай 1), то мы выбрасываем z. При этом значение текущего OR уменьшилось как множество.

    Если выпал случай 2), то мы выбрасываем x. При этом значение текущего OR уменьшилось как множество.

    Если выпал вариант 3), то мы выбрасываем y и нам придется спросить x|z, ведь нам надо знать OR оставшихся элеметов. Это плохо тем, что мы спросили 2 раза, рассморев один новый элемент. В неудачном случае мы бы задали 2n вопросов только ища 0 и у нас не осталось бы квоты на восстановление самой перестановки.

    Но тут есть 2 подварианта. 3а) Если значение x|z стало меньше, как множество, то ок. 3б) Но оно еще могло бы остаться таким же, т.е. x|y=y|z=x|z. Но в этом случае, по аналогичным рассуждениям нуля не может быть нигде среди этих трех элементов! А значит мы можем выкинуть и их все, избавившись от двух элементов за два вопроса.

    Если выпал вариант 4), то мы выбрасываем x или z.

    Таким образом задав от n до 2n (в самом неудачном случае) мы получаем в конце 2 элемента в одном из которых точно 0, а второй - a.

    Чтобы восстановить кто из двух оставшихся элементов кто: по ходу отсеивания, задавая любой вопрос запоминайте для какой пары чисел вы видели нулевой бит в каждом разряде. (Т.е. спросили про i|j получили ответ 5. Тут второй бит 0, значит запомнили, что i|j дает 0 в бите 2. И поддерживайте массив для всех разрядов).
    Если вам хоть сколько-нибудь повезет. вы наберете достаточно таких примеров.

    Теперь пройдитесь по всем примерам, что вы ранее видели и выберите тот, который имел 0 в разряде, где у a стоит 1. пусть это были элементы i и j. Теперь спросите x|i. Если и там этот разряд 0, то x=0, иначе у=0.

    Тут почти нарисовался строго убывающий инвариант - размер множетсва бит в OR для текущих кандидатов, но пункт 3б) его ломает, ведь мы получаем 2 новых элемента и множество может стать любым. Но случайный порядок вопросов должен сделать этот вариант маловаероятным. У вас запас примерно 150 впоросов на максимальном тесте. Возможно тут можно придумать какую-то строгую схему, где какой-то инвариант строго убывает на лишних вопросах и может убывать не более 100 раз.
    Ответ написан
    Комментировать
  • Как превратить процент в такое число?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Нужно строить регрессию.
    Например, сделаейте так:
    Заведите таблицу, где у вас первый столбец - ваши значения. Второй столбец - проценты (p). Третий - константа 1. четвертый - квадрат процентов (p^2). Потом логарифмы (log p), корни разных степеней, обратные (1/p).
    Потом прогоните на этой таблице линейную регрессию методом наименьших квадратов (фактически - решить систему линейных уровнений, например, методом Гаусса), она даст вам коэффициенты перед всеми функциями в аналитической формуле. Если не угадали с функциями, то ошибка будет большая. Фукции с мелкими коэффициентами можно будет отбросить и заменять чем-то другим.
    Возможно стоит добавить логарифмов со здвигом вида c1*log(p+c2), как у Rsa97, но тогда при методе наименьщих квадратов будут не только линейные урванения, придется помучиться аналитически.
    Ответ написан
  • Обход Binary-Tree, как сделать быстрее?

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

    Тут оба обхода вернут 1,2,3.

    Можно в вашем решении добавлять всякие разделители при переходе влево-вправо-вверх. Вставить всякие yeild -1 и другие значения перед походом влево, выводом собственно элемента и походом вправо.

    Но есть лучшее решение, через DFS или BFS: вы делайте обход одновременно на двух деревьях. Т.е. у вас параметр функции dfs или в очереди в bfs лежат сразу 2 вершины - по одной из каждого дерева. Вы проверяете, что у них значения одинаковые и что у них у обеих одновременно есть или нет левого и правого ребенка. Потом вызываетесь/кладете в очередь одновременно левых детей и одновременно правых детей. Если в процессе обхода вершины оказались разными, или где-то есть ребенок, а где-то нет - то деревья не равны.

    Очень логично реализовывается в виде DFS (ниже псевдокод):
    Equals(t1, t2):
       // обработать случай null одного или обоих деревьев.
       return t1.v == t2.v && Equals(t1.left, t2.left) && Equals(t1.right, t2.right)


    Все предельно логично - 2 дерева равны, если у них равны корни, левые поддеревья и правые поддеревья.

    Кстати, ваше решение, если его исправить, тоже будет за O(n).
    Ответ написан
  • Как объединить массивы с дубликатами в уникальные списки?

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

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

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

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

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

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