Как показать зависимость скорости от O(nlogn)?

jidomasson, Да, но вы должны помнить, что О-большое - это ассимптотическая оценка. Она действует только на больших числах. Допустим, там, на самом деле 5n log n + 100sqrt(n) операций. Это все еще O(n log n). Однако, если вы n с 10 до 20 увеличите, то у вас время вырастет чуть более, чем в 1.414 раз, потому что 100sqrt(n) сильно больше 5n log n. Однако на больших n скорость роста будет задаваться именно n log n.

Поэтому чтобы действительно намерить ассимптотическую сложность - надо брать большие n.

Ошибка double free or corruption (out) Aborted, как исправить?

При компилировании? Точно? Или при запуске программы и вводе каких-то данных?

Как оптимизировать код с++ с рекурсией в времени?

Maksym122, не стоит

Как оптимизировать код с++ с рекурсией в времени?

Maksym122,

> В одном тесте теперь неправильные данные, а в других двух ограничение памяти превысило

Поменяйте переменные на int64_t. Особенно tens, left, right. Наверно, там переполнение. В задаче ограничения на q не приведены, но если там действительно 2000000000, то могут быть проблемы.

Как оптимизировать код с++ с рекурсией в времени?

Maksym122, Ну значит, надо как я говорил, применять математику:

int S(int p, int q) {
  int sum = 0;
  for (int d = 1; d < 10; ++d) {
    for (int tens = 1; tens <= q; tens *= 10) {
      int left = p - d*tens;
      if (left < 0) left = 0;
      else left = (left + 10*tens-1)/(10*tens);
      int right = q - d*tens;
      if (right < 0) right = -1;
      else right /= 10*tens;
      sum += d*(right - left + 1);      
     }
  }
  return sum;
}

Как оптимизировать код с++ с рекурсией в времени?

Maksym122, Если не хватает стека, программа упадет с runtime error.
Переполнению тут особо негде и случатся, а если оно и есть, то ну получите вы отрицательные числа вместо правильных.

Как оптимизировать код с++ с рекурсией в времени?

Maksym122, нет.

Как найти кратчайший путь в лабиринте, двигаться в котором можно только вперед и направо?

Похоже, ук вас проблема с начальным состоянием. В очередь надо сложить 4 направления.

И вообще, использование 3d массива считается нормой для такой задачи, или лучше стараться этого избегать и писать иначе?

Ну, одно измерение тут всего 4. Так что не очень-то оно и трехмерное. Если у вас пространство вершин такое, то по-другому никак. Если так глаза мозилит, то можно завести массив фиксированного размера с максимальными размерами в задаче. Или вообще сделать массив одномерным и вычислять индексы руками.

А в каких-нибудь задачах на DP иногда и 5-мерные массивы бывают.

Как оптимизировать код с++ с рекурсией в времени?

Вы что-то напутали. S рекурсивно вычисляет сумму всех F() от p до q. Там же на каждом рекурсивном вызове прибавляется самое левое слагаемое.

Какой алгоритм использовать, чтобы: разбить массив чисел так, чтобы суммарная разница между максимальным и минимальным числом была максимальна?

BAF1, Попробуйте тест aaaaa 3 4
Должно быть NO SOLUTION.

А можно ли вывести всю строку, как одно слово? Вы, вроде как требуете всегда хотя бы 2 слова, но, может это и не надо? В тесте aaaaa 5 5 должно вывести одно слово aaaaa.

Как оптимизировать код с++ с рекурсией в времени?

Алексей 〒., да, в этой задаче это особо не поможет.

Какой алгоритм использовать, чтобы: разбить массив чисел так, чтобы суммарная разница между максимальным и минимальным числом была максимальна?

Alexandroppolus,

там может (r - l) сильно меньше n.

Может. Но пока об этом ничего не сказано, оценка сверху остается O(n) на каждое f().

что для вычисления max и min в очередной группе можно применить тот прием со стеком, который используется для вычисления оных на sliding window. Последняя группа смещается похожим образом. Если так, то будет вообще линейно.

Ну не, это же только для фиксированного размера группы сработает. Если там хоть какой-то разброс есть r-l, то sliding window уже нe работает.

Как оптимизировать код с++ с рекурсией в времени?

Alexandroppolus, да, ваша оценка более точна.

Как оптимизировать код с++ с рекурсией в времени?

Adamos, Она вам задана рекурсивно. Если там не написано, что надо ее именно так написать в коде, то - нет.

Если в задаче, например, сказано, что F(x) = sum i=1..x i, то функция заданна циклом. Но ее можно реализовать как x(x+1)/2.

Если вам надо обязательно иметь в коде рекурсивную F, то никак особо вы код не с оптимизируете. S разверните в цикл - и все. Но этого, скорее всего, не хватит.

Как в C++ создать массив с неизвестным числом элементов?

Вообще, некоторые компиляторы c++ поддерживают массивы переменной длины, и можно даже в коде написать:

cin >> n;
int a[n];

Это называется VLA, и вообще идет из C, но оно не стандартно и не всегда и везде скомпилируется.

Как переобразовать string в const unsigned char* в C++?

ASASDASDASDA, Только не забывайте, что это лишь указатель на память, которой владеет string. Поэтому если у вас str в примере выше выйдет из области жизни и удалится, то str_ptr останется висячим указателем.

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

Как устроен вывод в задаче?

Смотрите: вы добавляете в граф какие-то ребра. Надо чтобы после этого кратчайшие пути между заданными парами вершин укладывались в заданные ограничения. Ведь добавляя ребра вы можете какие-то пути улучшить (какие-то может и не улучшатся от каких-то ребер, но хуже нигде не станет. Ведь никто не заставляет пакеты ходить по новым ребрам).

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

Ну, тест, например,
7 6
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
3
1 4 2 1
5 7 1 2
1 7 1 3
1
1 7 4
Вывод:
2
1 2

Как устроен вывод в задаче?

Sunter, Ну, время - путь в графе кратчайшей длины. В примере 2 добавив "1 3 1 3" вы создали путь из 1 в 3 длинной 3 (из одного нового ребра). Он укладывается в нужное ограничение.

Добавление ребра "2 3 2 1" не помагает, потому что оно участвует в пути 1-2-3, и его стоимость 2+2 = 4, не укладывается в лимит по времени. Но добавить его в ответ все-равно можно, потому что цена добавления 1 меньше цены первого добавления. И кратчайший путь в графе (где длины ребер - время) все еще остается 3, через одно новое ребро 1-3.

Как устроен вывод в задаче?

Sunter, ах да. Вы еще стоимость и время в предложениях перепутали.

Как устроен вывод в задаче?

Sunter, простите, ответил на коммент до редактирования. Там на самом деле неважно и только второе предложение и оба вместе дают одинаково хороший ответ, ведь второе предложение самое дорогое. Так что 1 2 тоже валидный ответ.