Відео

@@Pepega230 напишите мне на почту (есть в описании видео) код решения этой задачи на Питоне, который Вы считаете простым - и который должен зайти за одну секунду на Питоне или PyPy. С этим кодом будем обсуждать с администратором acmp возможность увеличения памяти и возможно времени под этот код. Обычно администратор идёт навстречу в плане увеличения памяти.

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

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

Спасибо вам за объяснение этой задачи, я попробую переделать ее сам ❤

@@Gesperid обычно не пишут O(0), потому что есть расходы памяти на всякие мелочи: вызов метода (но для inline возможно нет расхода), переменная цикла for (но для while нет расхода).

@@Gesperid главный специалист по олимпиадному программированию в Вологодском государственном университете

По сути и при push_back вектора, и при reserve, и при resize происходит примерно одно и то же выделение памяти, остальные детали зависят от оптимизатора, так что что быстрее теоретически сказать невозможно. Плюс-минус без разницы.

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

@@35zvn Спасибо. На собеседованиях обычно минут 15 дают на задачу, насколько я знаю, если уж человек который пол жизни спортивным программированием занимается и учебники пишет ее полчаса решал, думаю 95% людей тут и отвалится. Под видео конкурентов очень многие писали что эту задачу 2-4 дня решали

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

Посмотрите на видео условие задачи, есть ли там ограничение. Они на leetcode не всегда были. Возможно именно их отсутствием объясняется использование map

А какие преимущества у них по сравнению с КМП? Разве что память можно в алгоритме Рабина-Карпа получить O(1). Но минус существенный - есть вероятность, что ответ будет неверный, что имеет смысл терпеть только если алгоритмическая сложность улучшается (обычно по времени), но конкретно тут мы этого не наблюдаем, КМП и так за линию работает. Забавный факт: поиск подстроки в строке на Go делается с помощью хэшей, так что если реализовать наивное решение на Go - оно будет соответствовать Вашему предложению.

@@35zvnПолиномиальные хеши не имеют преимуществ (с точки зрения асимптотической сложности), но их легко запомнить, и они подходят под большее число задач. В условиях стресса, первое, что приходит на ум в задачах со строками, это хеши, и скорее всего, с ними можно решить задачу. Получается своего рода запасной вариант, который почти всегда спасает.

Вопрос не в освобождении памяти. Она конечно освободится и без move. С move НЕ будет дополнительных расходов на новую копию данных в ответе. В C++ когда Вы один vector копируете в другой, идёт полное копирование данных. В отличие от например list в Python, где при присваивании создаётся ссылка на тот же объект.

Reverse за O(n), sort за O(nlogn). Разница не очень большая, но есть.

@@35zvn Спасибо. А вообще ты оч. крутой, быстро задачки решаешь. Я бы тебя нанял :D

Мне тоже 😉

@@35zvn мне не удалось на си просто перенести твой алгоритм, там нет ни векторов ни наборов, пришлось разбираться что такое DFS. Может надо кому: char *num_to_string(char num) { switch (num) { case '2' : return "abc"; case '3' : return "def"; case '4' : return "ghi"; case '5' : return "jkl"; case '6' : return "mno"; case '7' : return "pqrs"; case '8' : return "tuv"; case '9' : return "wxyz"; default: return ""; } } void backtrack(int K, char cur_str[5], char* s, const int strlen_s, char **result, int *return_size) { char str[5]; strcpy(str, cur_str); if (K == strlen_s) //Условие выхода из рекурсии - перебрали все цифры { strcpy(result[(*return_size)++], str); return; } for (int i=0; i< strlen(num_to_string(s[K])); i++) { str[K] = num_to_string(s[K])[i]; //Перебираю по порядку все буквы для текущей K цифры str[K+1] = '\0'; //Надо делать каждый раз, иначе strcpy: buffer overflow detected backtrack(K+1, str, s, strlen_s, result, return_size); //Перехожу к следующей цифре } } char** letterCombinations(char* s, int* return_size) { int strlen_s = strlen(s); int capacity; *return_size=0; switch (strlen_s) { case 1 : capacity=4; break; //capacity = 4^n. Всего возможно комбинаций (кол-во букв в цифре)^всего цифр case 2 : capacity=16; break; case 3 : capacity=64; break; case 4 : capacity=256; break; default: return NULL; } char **result = (char **)malloc(capacity*sizeof(char *)); //Выделение памяти под массив указателей на строки for(int i = 0; i < capacity; i++) result[i] = (char*) malloc(sizeof(char) * 5); //Выделение памяти под сами строки длиной 5 символов backtrack(0, "", s, strlen_s, result, return_size); return result; }

Без этого (int) сравнение int и size_t будет в size_t, конкретно тут проблемы в этом нет, но если бы было какое-то выражение вроде size() - 1 и при этом size() мог быть равен 0 - такое сравнение было бы ошибочно. Поэтому приведение к int тут просто относится к культуре написания кода с минимальной вероятностью ошибки. Что касается медленного кода - скорее всего замеры leetcode не точны, и такое заявление можно делать только после десятка раз сдачи того и другого кода.

А её нет, чтоб не сдавали, не разобравшись

Все эти задачи просто заставляют нас тратить своё время впустую, вместо того, чтобы реально работать и зарабатывать деньги для своей семьи. Какой смысл от того, что я решу все эти задачи сам? из всего, что я решал на leetcode или acmp мне в работе попалось только 3- 4 (поверхностно) Это при том, что на одну задачу со сложностью до 50 процентов я трачу около суток .Преподаватели, которые требуют такие задачи вообще в курсе, как работает бизнес, что требуют заказчики и какие задачи они ставят и за что платят деньги? Потратил на решение этих лабораторных почти две недели, а результат? лучше стал понимать алгоритмы и динамическое программирование? нет. Потому что в работе совсем другое используется...

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

Можно. Вопрос в типе данных, который потребуется для вычислений.