Результаты решения

#today #c_plus_plus #leetcode #algo

Daily question, again

На Leetcode похоже ежемесячник смешных задач на XOR. Всё остальное сразу убираю под спойлер.

Итак, сразу понятно, что о каком-либо переборе всех возможных массивов original с пересчётом их deriverd речь идти не может – это было бы экспоненциальное время работы. Вместо этого внимательно посмотрите на Example 1: в расписанных формулах для элементов derived каждое значение original фигурирует ровно дважды – это значит, что XOR-сумма элементов валидного derived, полученного из произвольного original обязана быть равна нулю.

class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        int res = 0;

        for (const auto& x: derived)
        {
            res ^= x;
        }

        return res == 0;
    }
};

#today #c_plus_plus #leetcode #algo

Хорош ли номер

Эта серия с Leetcode подзатянулась, но это не значит, что я её не продолжу:) Сегодня предлагаю просто почитать задачу уровня Hard, с удивительно низким для меня уровнем Acceptance порядка 20 процентов – решение я опубликую потом.

Сразу скажу: решение довольно простое, укладывающееся в сотню строк; причём достаточно использовать только сравнение символов, итерирование по строке и прочие низкоуровневые штуки, использовать тут regexp – неспортивно.

#today #c_plus_plus #leetcode #algo #ToBeContinued

Хорош ли номер ч. 2

Вернёмся к задаче из поста: решение я всё ещё придержу. Кстати, в данном случае использование конечных автоматов, предложенных тут в комментариях, в принципе оправдано, хотя – в своём решении я не использую их. Если кто-то из подписчиков реши(л|т), используя этот формализм, – предлагаю привести решение в комментариях.

Я же тут, пока что написал регулярное выражение подходящее под условие (\-\+)?((\d)+)|((\d*\.\d+)|(\d+\.\d*))((e|E)\d+)? – считайте это подсказкой.

#today #c_plus_plus #leetcode #algo #ToBeContinued

Хорош ли номер ч. 3

Закончим задачу из поста.

Итак, в прошлый раз я уже писал regexp, теперь проговорю словами: по сути валидное число это decimal или integer, которые могут быть продолжены символом 'e' или 'E' за которым идёт integer. Очень читабельное решение получается при разбиении строки на две части – до и после 'e/E'. Полученные части будут достаточно просты, что б проверить их циклом в один проход.

Код будет в комментарии. Обратите внимание на функцию isDecimal: на самом деле она не отличает decimal от integer, но это работает:) – Да, углы немного срезаны. Итоговая сложность, очевидно, линейна.

#today #c_plus_plus #leetcode #algo

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

Однако, часто так бывает, что найти хорошее решение, не изобретая велосипед, – практически невозможно. Неожиданный пример такой проблемы: умножение двух uint64_t по модулю в C++. Тут важны все слова: умножить без модуля – не очень сложно, использовать uint32_t – легко, не в C++ – окей, кто знает – тот знает.

А в чём собственно проблема? – в том, что, вообще говоря, произведение двух uint64_t не влезет в uint64_t, а стандартного типа uint128_t – нет.

Но есть же какая-то библиотека, где это уже сделано? – конечно, тот же gmp, но это не то решение, которое я ищу.
А что, если разбить uint64_t на две половинки по 32 бита, как-то их перемножить и т.д.? – к сожалению, это тоже не работает, в какой-то момент в формуле всё равно вылезет необходимость перемножить два uint64_t. Есть пара похожих вариантов, которые мне лень расписывать, и которые тоже не работают.
А есть же расширение __int128? – Да, есть, но только для GCC.
И что ничего нельзя сделать, если хочется получить самописную платформонезависимую реализацию данной операции? – Можно, вот только потребует это удивительно много строк кода.

Рассмотрим пару вариантов:
1) реализовать сначала обычное умножение с сохранением в пару uint64_t, потом по-честному поделить на модуль, вернув остаток
2) использовать алгоритм Монтгомери

Относительно первого варианта: реализовать умножение – сравнительно легко, вот с делением будет проблема: стандартный алгоритм (примерно то, что изучается в школе) потребует явный цикл...есть другие алгоритмы, но они ещё более неприятны в имплементации (например, рассмотренный мной метод Ньютона-Рафсона)

Относительно второго варианта – он выходит за рамки среднестатистических знаний об алгоритмах (включая, и мои знания на данный момент), но вот вам ссылка.

Вишенка на этом торте безумной "удобности" C++ является то, что процессор это умеет: можно посмотреть тут. Можно в godbolt дизассемблерить простой листинг для GCC.

typedef unsigned __int128 uint128_t;
uint128_t mult(uint64_t a, uint64_t b)
{
    return uint128_t(a) * uint128_t(b);
}

Так что вы говорите там будет интересного в новом стандарте?

#today #c_plus_plus #algo #hatred

Вернемся к задачам на Leetcode: часто такое бывает, что читаешь условие – и не можешь понять, что нужно сделать, перечитываешь снова, смотришь testcases, и только тогда – понимаешь. С этой сложной задачей всё абсолютно наоборот – сложно представить себе условие сформулированное ещё проще, тут даже разработчиком быть не обязательно.

Convert a non-negative integer num to its English words representation. То есть записать данное положительное целое число прописью.

Решение будет опубликовано спустя несколько дней. Кстати, на всякий случай уточню: задачи Leetcode не привязаны к определенному ЯП – просто на данный момент мне проще решить их на C++, но если вам более знаком Python, C#, you name it – просто используйте их, скорее всего платформа его поддерживает.

#leetcode #algo #ToBeContinued #English

Продолжим то, что начали в прошлый раз.

Несмотря на простую, формулировку testcases пригодятся: язык хоть мне и знакомый, но не родной – редко приходится озвучивать числительные да и ещё такие большие.

Итак, для 1 234 567 нужно выдать "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven". Думаю довольно очевидно, что все уникальные числительные будут константами так или иначе организованными в листинге, а именно это числа 0-19, 20, 30...90, 100, 1000, 1000 000, 1000 000 000. Далее, по большей части я вынужден перефразировать подсказки данные в условии (честно скажу, что я прочёл их уже после успешного submit).

Рассмотрите отдельные тройки разрядов, обратите внимания, что их звучание однотипно – отличие только в том, что одна группа это Million, другая Thousand, ну а последняя (Ones) – суффикса не требует. Так же нам везёт, что все эти Million/Thousand сами не склоняются по числу ( не требует 's'). Внутри же этой тройки разрядов всё достаточно просто: озвучиваем первую значащую цифру, прибавляя Hundred, далее если в оставшихся двух разрядах число старше 19, то озвучиваем сначала десяток, потом вторую цифру, если число не старше 19 – озвучиваем сразу две цифры. И да – нули не озвучиваем.

Как выделяются тройки разрядов и обработку corner-cases – посмотрите в листинге или в подсказках на платформе. Листинг в комментарии к посту.

#leetcode #algo #c_plus_plus #English

Разница в подходах

Поучаствовал в небольшом Яндекс.Контесте. Темой было решение задач по теории чисел, но о самих задачах в этот раз я ничего говорить не собираюсь – они были несложные и не особо-то интересные.

Удивило меня другое: на Leetcode нет нужды писать ввод-вывод, ну и самое главное – если после Submit решение упадёт на каком-либо из testcases – платформа покажет это. Также можно добавлять свой пользовательский вывод и его тоже будет видно. На Я.Ке нужно писать весь ввод и вывод данных самому, не видно содержания testcases, и невозможно ничего распечатать и увидеть это где-либо. То есть, при любой малейшей ошибке нет ни одного шанса обнаружить её с помощью этой платформы – остается только самому придумывать тестовые данные и локально отлаживать.

В двух задачах из трёх я столкнулся с ситуацией, что решение не проходит N-ый testcase: не забить окончательно на такую неразговорчивую платформу и довести до конца, помогла только мысль, что задачи-то простые.

Вывод: для изучения алгоритмов либо поддержания себя в тонусе для собесов, Leetcode гораздо удобнее – подход Я.К требует гораздо большей мотивации (которой нет).

#today #algo #leetcode

Написал статью на Хабр под названием "Недистрибутивность деления, или как я считал среднюю величину". Сама статья выйдет, вероятно, в июне — тут от меня мало что зависит.

Тема выросла из вопроса с собеседования (Вова - спасибо). Изначально казалось, что материала на статью маловато, но я довёл проблему до абсурда абсолюта — и материал нашёлся.

Будет всё, что я люблю: неочевидный слом очевидного, скрупулёзный подсчёт битов, духота математических рассуждений. Ладно, я несколько преувеличиваю: статья будет проста, гораздо проще, чем эта.

#today #habr #algo