Этот пример создаёт ложное впечатление, что программа может работать с кириллицей так же понятно, как и с латиницей. Под Linux это ещё более-менее может работать, там почти все перешли на utf-8. Но под Windows нет. Запишем что-нибудь в файл, получаем проблемы с кодировками. Попытаемся открыть файл с кириллицей в названии через std::filesystem — проблемы с кодировками. Попытаемся зачем-нибудь вызывать WinAPI — снова надо не UTF-8, а что-то другое.
Тут уже проблема с самой постановкой задачи, если не ограничиться кириллицей-латиницей. Я не уверен, что "вывести строку задом наперёд" имеет хоть какой-то смысл для арабской вязи, например. Или что не могут возникать новые графемные кластеры из подряд идущих code points в зависимости от версии Unicode.
Вы про какой? Я вижу кроссплатформенные только в смысле "написали один код на C++". А дальше чтобы он корректно отработал надо плясать с бубном на каждой конкретной системе, среде разработке, компиляторе и подбирать ключи компиляции и настройки терминала.
Если у нас есть возможность зафорсировать одну ОС (и выкинуть либо людей с macOS, либо наоборот, либо выкинуть вообще всех, потребовав Linux) и среду разработки — то пожалуйста. Но если есть хоть какое-то разнообразие, то настройка даже одного компилятора — уже достаточное развлечение.
Это да, но как помогает? Пусть у меня N символов в строке, а разных символов Sigma (~26). Тогда имеем n(n+1)/2 - sigma*(n/sigma)*(n/sigma+1)/2 = (n^2+n - (n^2/sigma+n))/2 = n^2*(1-1/sigma)/2 срезов. Это всё ещё O(n^2) при sigma>=2.
Я подозреваю, что система показывает только результат запуска на тестах из условия и окончательное тестирование на полном наборе тестов будет уже после окончания отбора.
Решение из статьи даже на случайной строке длиной 2000 работает долго.
Мне кажется, проблемы скорее не из-за юникода, а из-за всяких неверных предположений о языках при разработке (статья). Даже арабский (один из шести официальных языков ООН) на сайтах отображают неверно: https://isthisarabic.com/
А с эмоджи в текстах тоже никаких проблем не возникало? С русским-то проблем лишь чуть-чуть больше, чем с английским — просто меняем концепцию "один символ — один байт" на "один символ — один code point" и теперь работаем и с русским, и с английским. А вот эмоджи это разламывают.
Но зачем доступ к code point? В общем случае это такая же абстракция. У него нет какого-либо значения, вот хорошая статья на тему.
Например, вот два code point: ??. Если наивно "развернуть" это по code point'ам, получим другой флаг. Потому что не надо почти никогда разворачивать строчки в вакууме, если это игра — то наверняка игра под конкретный язык.
А вот один code point: ﷽ . Или вот несколько, но выделяются обычно как один: ᄀᄀᄀ각ᆨᆨ.
Забудем сначала про модуль. Посмотрим просто на числа: пусть B=g^b и A=g^a. Тогда B^a=(g^b)^a=g^(b*a) — вот тут единственный нетривиальный трюк, надо заменить двойное возведение в степень на степень произведения. Аналогично с A^b=(g^a)^b=g^(a*b). А дальше пользуемся коммутативностью умножения: b*a=a*b.
А теперь если везде взять результат по модулю p (кроме b*a или a*b), то равенства не сломаются. Почему не сломаются — надо уже аккуратнее расписывать, что именно не ломается. Например, можно обозначить за B "настоящее" g^b, а за B' — взятое по модулю, дальше расписывать. Ещё из полезных трюков, через который вся модульная арифметика выводится: a = b (mod p) эквивалентно "(a - b) делится на p".
Это закрасит все точки такого цвета, а не только связные с той, куда вы ткнули. Например, если вы нарисовали двумерный домик на белом холсте и попытались закрасить пока что белые стены, закрасится весь лист, кроме очертаний домика.
Что касается пространственной сложности, то каждый рекурсивный вызов требует дополнительной памяти для хранения состояния функции, которое включает текущую позицию и цвет пикселя. В наихудшем случае, когда заполняемая область охватывает всё изображение, максимальная глубина рекурсии будет равна количеству строк в изображении. Поэтому пространственная сложность алгоритма заливки на основе рекурсии может быть выражена как O(m).
Это категорически неверно по двум пунктам сразу.
Во-первых, почему именно строк, а не столбцов? Столбцов может быть на порядок больше. Никаких принципиальных отличий между строками и столбцами в алгоритме обхода в глубину (depth-first search, так называется ваш первый алгоритм) нет. Так что как минимум O(max(n, m)), оно же O(n+m).
Во-вторых, а с какого перепуга это наихудший случай? Вы ещё скажите, что наихудший случай для алгоритма сортировки — это когда массив отсортирован в обратном порядке. Не бывает просто "наихудших" случаев. Это вредное заблуждение. Бывают только случаи, максимизирующие или минимизирующие какую-то метрику. Тогда мало предъявить случай, надо доказать.
Например, довольно легко придумать пример, где глубина стека (по сути максимальная длина пути, которую пройдёт алгоритм, пока не упрётся в тупик) будет уже порядка n*m/2.
Здесь надо "залить" точки и не ходить по решёткам.
Если вам кажется, что ну уж это-то очевидно наихудший случай, то вы снова попались в ловушку. Не было ни слова доказательства про наихудшесть случая. Этот случай плохой, но не наихудший. Можно ещё хуже сделать. Я вот знаю пример с n*m*2/3, но тоже без доказательства, что это наихудший случай.
Хотя асимптотически уже неважно, оба случая будут O(n*m). И вот это уже доказывается без "наихудших случаев": в стеке вызовов (за исключением текущего фрейма) каждая ячейка может встретиться не больше одного раза. Доказательство закончено.
А ещё посылаю лучи ненависти новому редактору Хабра. Он уже один раз съел комментарий и не давал набирать текст в некоторых местах, уффф.
Потому что в фигурных скобках команда завершилась с ошибкой — false. Из этого напрашивается вывод, что выполнение фигурных скобок прерывается из-за `set -e`, фигурные скобки целиком тоже завершились с ошибкой, дальше идёт обработчик ошибки справа от фигурных скобок.
Другими словами, ожидается прерывание выполнения не только на самом верхнем уровне, но и внутри скобок.
Бинарники можно продавать только в комплекте с исходниками, да.
"Копию" — в смысле что нельзя взять программу под GPL и продать кому-то исключительные права на её использование, чтобы это кто-то мог решать, что можно и нельзя делать? Как только опубликовали под GPL, джин выпущен из бутылки. Да, нельзя, конечно. Как нельзя продать любую программу, если ты не правообладатель.
Но если есть согласие всех исходных авторов, то можно взять ту же версию кода, перелицензировать как душе угодно без переписывания код, и вот эту перелицензированную версию кому-то продать. Тогда старая версия остаётся под GPL (и с ней нельзя ничего запретить), зато новая может быть проприетарной сколько угодно.
Yes, the GPL allows everyone to do this. The right to sell copies is part of the definition of free software. Except in one special situation, there is no limit on what price you can charge. (The one exception is the required written offer to provide source code that must accompany binary-only release.)
Microsoft .NET Core распространяется под лицензией MIT, можно делать почти что угодно, в том числе продавать:
Permission is hereby granted, free of charge, to any person obtaining a copy of this software ... to ... sell copies of the Software ..., subject to the following conditions:
Только после продажи покупатель снова может делать с полученным что угодно:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
Аналогичная история с GPL: если вы получили бинарники или код — можете делать почти что угодно, в том числе продавать. Правда, обязаны передать покупателю исходный код, даже если продаёте только бинарники.
Но есть ещё интересная штука под названием "торговая марка". Не удивлюсь, если последовательности букв "Microsoft", "Microsoft .NET", ".NET", ".NET Core" являются торговыми марками. Тогда с ними совершенно другая история идёт про использование, независимо от лицензии на исходники. Например, наверняка нельзя использовать в рекламе просто так без разрешения Microsoft. Я даже слышал байку, что в США владелец торговой марки обязан докапываться до её использования без разрешения, иначе отберут с комментарием "а зачем она вам тогда нужна, если не отстаиваете". Не знаю, насколько правда.
Они зарезервированы POSIX, как и куча чего другого. Как я это выяснил: мне как-то сдали решение, которое у меня на компьютере не компилировалось с ошибкой "переопределение типа". Оказалось, что на моей ОС такой тип в стандартных заголовках есть, а у студента — нет. И у студента честно компилировалось.
С тех пор рассказываю, что зарезервированное под POSIX тоже лучше не использовать глобально. В идеале, конечно, всё в отдельный namespace заворачивать, но до namespace'ов не сразу доходим, и это тоже надо проверять глазами или писать свой отдельный инструмент.
Есть обязательное code review и полуавтоматические скрытые тесты, на них и ловим. Например, чтобы поймать static initialization order fiasco надо компилировать с единицами трансляции в разном порядке в зависимости от решения. То есть надо заранее подумать, что в решениях такая проблема будет и составить задание так, чтобы была сборка не как обычно через CMake, а руками.
А вот некорректные названия (двойные нижние подчёркивания, подчёркивания в начале глобальных переменных, типы заканчивающиеся на _t) и нарушения strict aliasing или левые const_cast ловятся только глазами. Ну, __ и _foo умеет ловить clang-tidy, а вот foo_t не умеет.
Что ловится разными компиляторами и санитайзерами: отличия int и long, разные переводы строк под Windows/Linux, почти все переполнения массивов и переполнения знаковых типов.
Более того — ровно такое поведение стандартом C++ и описано: https://en.cppreference.com/w/cpp/language/lambda и https://eel.is/c++draft/expr.prim.lambda.closure#1 . Конечно, компилятор мог бы оптимизировать это во что-нибудь ещё более эффективное по as-if rule, но если запретили весь инлайнинг, то этого не происходит.
Этот пример создаёт ложное впечатление, что программа может работать с кириллицей так же понятно, как и с латиницей. Под Linux это ещё более-менее может работать, там почти все перешли на utf-8. Но под Windows нет. Запишем что-нибудь в файл, получаем проблемы с кодировками. Попытаемся открыть файл с кириллицей в названии через
std::filesystem— проблемы с кодировками. Попытаемся зачем-нибудь вызывать WinAPI — снова надо не UTF-8, а что-то другое.Тут уже проблема с самой постановкой задачи, если не ограничиться кириллицей-латиницей. Я не уверен, что "вывести строку задом наперёд" имеет хоть какой-то смысл для арабской вязи, например. Или что не могут возникать новые графемные кластеры из подряд идущих code points в зависимости от версии Unicode.
Вы про какой? Я вижу кроссплатформенные только в смысле "написали один код на C++". А дальше чтобы он корректно отработал надо плясать с бубном на каждой конкретной системе, среде разработке, компиляторе и подбирать ключи компиляции и настройки терминала.
Если у нас есть возможность зафорсировать одну ОС (и выкинуть либо людей с macOS, либо наоборот, либо выкинуть вообще всех, потребовав Linux) и среду разработки — то пожалуйста. Но если есть хоть какое-то разнообразие, то настройка даже одного компилятора — уже достаточное развлечение.
Это да, но как помогает? Пусть у меня N символов в строке, а разных символов Sigma (~26). Тогда имеем n(n+1)/2 - sigma*(n/sigma)*(n/sigma+1)/2 = (n^2+n - (n^2/sigma+n))/2 = n^2*(1-1/sigma)/2 срезов. Это всё ещё O(n^2) при sigma>=2.
Там не две буквы меняются местами, а подстрока целиком разворачивается. abcde может превратиться в edcba, а не ebcda.
Я подозреваю, что система показывает только результат запуска на тестах из условия и окончательное тестирование на полном наборе тестов будет уже после окончания отбора.
Решение из статьи даже на случайной строке длиной 2000 работает долго.
Мне кажется, проблемы скорее не из-за юникода, а из-за всяких неверных предположений о языках при разработке (статья). Даже арабский (один из шести официальных языков ООН) на сайтах отображают неверно: https://isthisarabic.com/
А с эмоджи в текстах тоже никаких проблем не возникало? С русским-то проблем лишь чуть-чуть больше, чем с английским — просто меняем концепцию "один символ — один байт" на "один символ — один code point" и теперь работаем и с русским, и с английским. А вот эмоджи это разламывают.
Но зачем доступ к code point? В общем случае это такая же абстракция. У него нет какого-либо значения, вот хорошая статья на тему.
Например, вот два code point: ??. Если наивно "развернуть" это по code point'ам, получим другой флаг. Потому что не надо почти никогда разворачивать строчки в вакууме, если это игра — то наверняка игра под конкретный язык.
А вот один code point: ﷽ . Или вот несколько, но выделяются обычно как один: ᄀᄀᄀ각ᆨᆨ.
Забудем сначала про модуль. Посмотрим просто на числа: пусть B=g^b и A=g^a. Тогда B^a=(g^b)^a=g^(b*a) — вот тут единственный нетривиальный трюк, надо заменить двойное возведение в степень на степень произведения. Аналогично с A^b=(g^a)^b=g^(a*b). А дальше пользуемся коммутативностью умножения: b*a=a*b.
А теперь если везде взять результат по модулю p (кроме b*a или a*b), то равенства не сломаются. Почему не сломаются — надо уже аккуратнее расписывать, что именно не ломается. Например, можно обозначить за B "настоящее" g^b, а за B' — взятое по модулю, дальше расписывать. Ещё из полезных трюков, через который вся модульная арифметика выводится: a = b (mod p) эквивалентно "(a - b) делится на p".
Это закрасит все точки такого цвета, а не только связные с той, куда вы ткнули. Например, если вы нарисовали двумерный домик на белом холсте и попытались закрасить пока что белые стены, закрасится весь лист, кроме очертаний домика.
Это категорически неверно по двум пунктам сразу.
Во-первых, почему именно строк, а не столбцов? Столбцов может быть на порядок больше. Никаких принципиальных отличий между строками и столбцами в алгоритме обхода в глубину (depth-first search, так называется ваш первый алгоритм) нет. Так что как минимум O(max(n, m)), оно же O(n+m).
Во-вторых, а с какого перепуга это наихудший случай? Вы ещё скажите, что наихудший случай для алгоритма сортировки — это когда массив отсортирован в обратном порядке. Не бывает просто "наихудших" случаев. Это вредное заблуждение. Бывают только случаи, максимизирующие или минимизирующие какую-то метрику. Тогда мало предъявить случай, надо доказать.
Например, довольно легко придумать пример, где глубина стека (по сути максимальная длина пути, которую пройдёт алгоритм, пока не упрётся в тупик) будет уже порядка n*m/2.
Лучше придумайте сами
Здесь надо "залить" точки и не ходить по решёткам.
Если вам кажется, что ну уж это-то очевидно наихудший случай, то вы снова попались в ловушку. Не было ни слова доказательства про наихудшесть случая. Этот случай плохой, но не наихудший. Можно ещё хуже сделать. Я вот знаю пример с n*m*2/3, но тоже без доказательства, что это наихудший случай.
Хотя асимптотически уже неважно, оба случая будут O(n*m). И вот это уже доказывается без "наихудших случаев": в стеке вызовов (за исключением текущего фрейма) каждая ячейка может встретиться не больше одного раза. Доказательство закончено.
А ещё посылаю лучи ненависти новому редактору Хабра. Он уже один раз съел комментарий и не давал набирать текст в некоторых местах, уффф.
Потому что в фигурных скобках команда завершилась с ошибкой —
false. Из этого напрашивается вывод, что выполнение фигурных скобок прерывается из-за `set -e`, фигурные скобки целиком тоже завершились с ошибкой, дальше идёт обработчик ошибки справа от фигурных скобок.Другими словами, ожидается прерывание выполнения не только на самом верхнем уровне, но и внутри скобок.
Увы, это всё не до конца помогает, если писать сложные скрипты. Например, вот такой код выведет
should not printвместоfailed:Бинарники можно продавать только в комплекте с исходниками, да.
"Копию" — в смысле что нельзя взять программу под GPL и продать кому-то исключительные права на её использование, чтобы это кто-то мог решать, что можно и нельзя делать? Как только опубликовали под GPL, джин выпущен из бутылки. Да, нельзя, конечно. Как нельзя продать любую программу, если ты не правообладатель.
Но если есть согласие всех исходных авторов, то можно взять ту же версию кода, перелицензировать как душе угодно без переписывания код, и вот эту перелицензированную версию кому-то продать. Тогда старая версия остаётся под GPL (и с ней нельзя ничего запретить), зато новая может быть проприетарной сколько угодно.
GNU GPL v2 продажу разрешает, и никаких упоминаний 60% в тексте лицензии нет и близко.
Microsoft .NET Core распространяется под лицензией MIT, можно делать почти что угодно, в том числе продавать:
Только после продажи покупатель снова может делать с полученным что угодно:
Аналогичная история с GPL: если вы получили бинарники или код — можете делать почти что угодно, в том числе продавать. Правда, обязаны передать покупателю исходный код, даже если продаёте только бинарники.
Но есть ещё интересная штука под названием "торговая марка". Не удивлюсь, если последовательности букв "Microsoft", "Microsoft .NET", ".NET", ".NET Core" являются торговыми марками. Тогда с ними совершенно другая история идёт про использование, независимо от лицензии на исходники. Например, наверняка нельзя использовать в рекламе просто так без разрешения Microsoft. Я даже слышал байку, что в США владелец торговой марки обязан докапываться до её использования без разрешения, иначе отберут с комментарием "а зачем она вам тогда нужна, если не отстаиваете". Не знаю, насколько правда.
Ответил выше
Они зарезервированы POSIX, как и куча чего другого. Как я это выяснил: мне как-то сдали решение, которое у меня на компьютере не компилировалось с ошибкой "переопределение типа". Оказалось, что на моей ОС такой тип в стандартных заголовках есть, а у студента — нет. И у студента честно компилировалось.
С тех пор рассказываю, что зарезервированное под POSIX тоже лучше не использовать глобально. В идеале, конечно, всё в отдельный namespace заворачивать, но до namespace'ов не сразу доходим, и это тоже надо проверять глазами или писать свой отдельный инструмент.
Есть обязательное code review и полуавтоматические скрытые тесты, на них и ловим. Например, чтобы поймать static initialization order fiasco надо компилировать с единицами трансляции в разном порядке в зависимости от решения. То есть надо заранее подумать, что в решениях такая проблема будет и составить задание так, чтобы была сборка не как обычно через CMake, а руками.
А вот некорректные названия (двойные нижние подчёркивания, подчёркивания в начале глобальных переменных, типы заканчивающиеся на
_t) и нарушения strict aliasing или левыеconst_castловятся только глазами. Ну,__и_fooумеет ловить clang-tidy, а вотfoo_tне умеет.Что ловится разными компиляторами и санитайзерами: отличия
intиlong, разные переводы строк под Windows/Linux, почти все переполнения массивов и переполнения знаковых типов.