Задать вопрос
  • Правильно понимаю из статьи про умные указатели?

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

    Тут автор считает, что сначала выполнится new A(), потом new B(), потом конструктор unique_ptr. Если исключение бросит B(), то действительно будет утечка памяти. Объект A, полученный через new умрет еще до оборачивания в unique_ptr. Такой сырой указатель автоматически не удалится.

    Такая последовательность невозможна c С++17:
    In a function call, value computations and side effects of the initialization of every parameter are indeterminately sequenced with respect to value computations and side effects of any other parameter.


    Evaluations of A and B are indeterminately sequenced : they may be performed in any order but may not overlap: either A will be complete before B, or B will be complete before A. The order may be the opposite the next time the same expression is evaluated.


    Но до C++17, действительно, компилятор может перемешать вычисления аргументов как угодно.
    Ответ написан
    Комментировать
  • Как отсортировать список из массивов?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Зависит от возможных значений чисел. Если числа не очень большие, то RadixSort будет самым быстрым вариантом. В противном случае самая обычная стандартная сортировка будет достаточно быстрая. Просто надо как-то ей передать функцию сравнения двух массивов, которая смотрит на первый элемент, а потом на второй. Что-то вроде a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]). Не специалист по C#, но возможно массивы уже так и сравниваются там.
    Ответ написан
    Комментировать
  • Код при самостоятельном тестировании работает корректно, а при проверке тестировщиком программа выдает ошибку. В чем может быть проблема?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    У вас неинициализированные переменные mini и maxi. И они используюся такими в сравнениях. Это Undefined Behavior и на разных компьютерах может вести себя по разному. И если вам не повезет и, например, mini окажется каким-то очень маленьким числом, то у вас выдаст не правильный ответ.
    Ответ написан
  • Как из длины массива и максимального количества потоков узнать индексы, которые будет обрабатывать поток?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вам надо разбить массив на K как можно более равных частей?

    Если длина массива N, то все куски будут длиной хотя бы floor(N/K), и ровно N%K будут иметь на 1 элемент больше. Вроде, если у вас 10 элементов надо на 3 потока разделить, то будут длины {4, 3, 3}. А если 15 на 4, то {4, 4, 4, 3}

    Так что i-ый кусок будет начинаться с позиции (N/K)*i + min(i, N%K) и иметь длину N/K + ((i < N%K) ? 1 : 0).

    Чуть проще формулы, если вы эти позиции явно в массиве получите, а не будете каждую отдельно считать:
    int start[K], end[K];
    int prev = -1;
    for (int i = 0; i < K; ++i) {
      int len = N/K + ((i < N%K) ? 1 : 0);
      start[i] = prev + 1;
      end[i] = start[i] + len;
      prev = end[i];
    }
    Ответ написан
    Комментировать
  • Как называется такая структура данных?

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

    И вообще, у вас тут намудрено, почему нельзя сделать просто:
    let objects: HashMap<Uuid, Object>;

    Тут все такой же O(1) доступ к элементу по id. Зачем вам массив? Вы там добились простой и cache-friendly итерации по всем объектам? Не факт, что это уже не реализовано внутри HashMap. По крайней мере во многих языках можно проитерироваться по всем объектам в стандартной хеш-таблице.

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Используйте std::vector. Их можно присваивать как переменные. При этом там под капотом не будет никакого копирования, а просто изменение указателей в данном случае (так как правая часть - временное значение).
    std::vector<int> a, b;
    a = a0;
    b = F(a);
    for (int i = 1; i <= n; ++i) {
      a = G(b);
      b = F(a);
    }


    Если вас напрягает, что функции G и F выделяют память внутри, то можно сделать, чтобы они получали vector, в который надо вернуть значения:
    void F(const vector<int> &a, vector<int>& res);
    void G(const vector<int> &b, vector<int>& res);
    
    std::vector<int> a, b;
    a = a0;
    b = F(a);
    for (int i = 1; i <= n; ++i) {
      G(b, a);
      F(a, b);
    }
    Ответ написан
    Комментировать
  • Почему без std::remove_reference_t не работает?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вообще, не вижу противоречия. У вас же там tfunc&&, его вы пытаетесь к void* привести и к нему применяете remove reference.

    Попробуйте в ваш static assert добавить std::move и он обвалится.
    Ответ написан
    Комментировать
  • Могут ли возникнуть проблемы при одновременном чтении и записи в разных потоках переменной?

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

    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 варианта с объяснением и кодом.
    Ответ написан
    Комментировать
  • Что лучше: static методы или функции?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Посмотрите в этот allStatic: https://github.com/openjdk/jdk/blob/496641955041c5...

    Там написано, почему используются статические методы: Почему-то авторы какого-то проекта HotSpot решили, что плодить namespac'ы плохо. Так что это вызвано соглашениями по стилю в конкретном проекте. Их право.

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

    Еще логично сделать функцию членом класса, если она именно с классом работает. Например, функции фабрики.

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вам надо подсчитать вероятности успеха. Просто с бонусом все элементарно. Если бонус b, то у вас выпадают очки b+1,b+2,b+3...,b+20 с равной вероятностью. Считаете сколько их больше нужного количества очков m и делите на 20: (20-(m-b)+1)/20. Вот вероятность выиграть с этим бонусом.

    Проблема с двумя кубиками. Тут не сумма, а максимум. Если составить таблицу результатов, например для костей с 3 гарнями, то мы получим вот это:

    * 1 2 3
      -----
    1|1 2 3
    2|2 2 3
    3|3 3 3


    Т.е. 1 выпадет в 1 исходе, 2 в - в трех, 3 в 5... Для 20-гранных кубиков будет аналогично. i от 1 до 20 выпадет с вероятностью (2i-1)/400.

    Какие исходы вам подходят? i+b >= m, т.е i >= m-b.
    Итак, для вероятности успеха вам надо проссумировать вероятности всех хороших исходов. Т.е. просуммировать (2i-1)/400 для i от m-b до 20.

    Потом взять ту конфигурацию, у которой вероятность выигрыша больше всего.

    Формулы выше считают, что m > b. Иначе они не совсем работают и там получается вероятность больше 1. На самом деле она там 1. Так что если есть вариант с бонусом хотя бы нужное количество очков - берите его не раздумывая.
    Ответ написан
    Комментировать
  • Почему шаблон выдает ошибку при включении заголовка в .cpp файл?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Не совсем уверен, потому что кода не хватает в вопросе. Но симптом звучит как "если шаблон определяется не в том же файле, где он объявляется, то ничего не работает". Это частая ошибка на С++ с шаблонами.

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

    Поэтому надо или шаблон объявлять и опеределять в хедере, чтобы оперделения были везде, или в cpp с определениями указать спецификацию для всех используемых варинтов шаблона. Вроде
    using my_template<int>;
    Ответ написан
    6 комментариев
  • Не могу решить задачу на 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).
    Ответ написан
  • В каких практических задачах требуется алгоритм размещения прямоугольников в круге?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Размещение разных чипов на круглой загатовке. Вообще сейчас печатают один и тот же чип, но, теоретически, мешая чипы разных размеров можно сэкономить отходы.
    Ответ написан
    1 комментарий
  • Почему 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++
    Разработчик на С++, экс-олимпиадник.
    Это называется яркость света. Цвет лазера особо не меняется. Наверно, можно считать, что яркость уменьшается очень медленно линейно из-за рассеивания воздухом. Для не лазерных источников света яркость убывает квадратично от расстояния.
    Ответ написан