Ответы пользователя по тегу Программирование
  • Как решить данную олимпиадную задачу?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Это задача на придумывание паттерна и доказывание его. Тут надо рисовать всякие случаи на бумажке и обобщать.

    Во-первых, когда встает вопрос о можно-нельзя ли какими-то операциями получить что-то, первая мысль должна быть - придумать инвариант. Какое-то свойство, которое не меняется при применении операции. С опытом наберетесь идей для инвариантов. Тут сразу приходит в голову такой: Обозначим цвета цифрами от 0 до 2. Тогда при любом перекрашивании сумма всех чисел по модулю 3 не меняется. Если столбы одинаковые - сами числа не меняются, если 01 перекрасить в 22, 02 в 11 и 12 в 00, то сумма остается с таким же остатком от деления на 3.

    Отсюда можно сразу сделать вывод, что при N делящемся на 3 ответа нет. Потому что в конце мы должны получить все цвета одинаковые, а значит сумма будет 0, N или 2N - делится на N. Раз N делится на 3, то и итоговая сумма дает остаток 0 (по модулю 3). Но изначальная раскраска может иметь любой остаток (например, 00..0001). Значит решения для таких N нет.

    Далее, можно легко придумать, как "удваивать" решение. Пусть мы умеем получать какой-то N, то можно получить алгоритм для 2N. Сначала перекрашиваем первую половину по известному плану. Потом вторую половину. Потом попарно столбы из двух половин. Надеюсь, очевидно, почему это работает?

    Так можно получить ответ для 2,4,8,16, но этого мало.

    Следующая мысль, как можно построить универсальный план покраски - это воспользоваться тем, что если мы сделаем все столбы одинаковыми, то все последующие действия ничего не испортят. Т.е. можно взять конкретную раскраску столбов, составить план для нее. Потом взять следующий вариант входных данных, прогнать его через уже составленный план. Если результат не одноцветный - дополнить план так чтобы раскрасить все в один цвет и для этого варианта изначальной раскраски. Повторить со всеми возможными входными данными. Использовать эту идею для всех вариантов N раскрасок слишком медленно (их же 3^N). Вернемся к ней попозже.

    Следующая идея должна быть - раз для существования решения важно неделимость на 3, то возможно мы сможем к группе одинаковых столбов добавить 3 столба?

    После разбора нескольких случаев на бумаге я понял, что надо отдельно рассматривать случаи N%3=1 и N%3=2.

    Рассмотрим первый случай. У нас есть 3k столбов цвета А, и в конце еще 4 столба - AXYC (один из N и 3 новых). Задача - получить в конце 4 одинаковых цвета. У нас уже есть решение для N=4 в примере. Просто примените его к 4-м последним столбцам. Теперь у нас есть ...AAAZZZZ. Если A=Z, то все наши операции ничего не сделают. Рассмотрим только случай A!=Z. Красим A+Z, получаем AAYYZ..Z на конце Красим 2 раза A+Y. Т.е. за 3 операции мы перекрасили 3 последние A в Z. Повторяем операцию, пока все A не перекрасим (их же 3k, напоминаю).

    Теперь случай N=3k+2. У нас есть 3k A, и в конце AAXYC. Если у вас есть решение для 5, то получаете на конце 5 Z и аналогично предыдущему случаю перекрашиваете 3 последних A в цвет последних столбов.

    Т.е. отдельно рассматриваете случай разных остатков N%3. Потом решаете задачу для N=4 или 5 первых столбцов, потом добавляете по 3 столба: решаете задачу для 4/5 последних столбов и итеративно перекрашиваете по 3 столба из предыдущих.

    Это решение потребует максимум N/3*(F(5)+N) шагов, где F(5) - сколько нужно операций для решения N=5.

    Теперь решение для N=5. Тут и надо будет воспользоваться наблюдением о дополнении плана для разных входных данных. Вот есть 5 столбов. Покрасим 1+2 и 3+4. Теперь у нас есть AABBC. Возможно какие-то цвета одинаковые. Но сначала допустим, что они все три разные. Красим попарно A+B(1+3 и 2+4). Все. Но что, если B=C, B!=A? У нас было AABBB. Мы покрасили 1+3 и 2+4 - получили ССССA. Красим 4+5 - CCCBB. Теперь, как раньше, перекрасим 3С в B: 3+4 (CCAAB), 1+3(BCBAB), 2+4 (BBBBB).
    Теперь надо рассмотреть случай B=A, C!=A: AAAAC. Надо аккуратно повторить все операции выше - получим BBBBB. План для этого случая работает, ничего дописывать не надо. Остался случай A=C, C!=B. Т.е. дано AABBA. Применяем шаги выше и получим (перепроверьте!) AAAAA.

    Т.е весь план для N=5 1+2, 3+4, 1+3, 2+4, 4+5, 3+4, 1+3, 2+4.

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

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

    Возьмите максимальную степень двойки, помещающуюся в N. Пусть это k (2k > N, k <= N). Примените план для первых k. потом для последних k. Итого вы получите N-k столбов одного цвета и k столбов (возможно) другого цвета в конце. Если N-k делиться на 3 то, по известному плану "перекрашивания по тройкам" перекрасьте первые N-k в цвет последних k. Если же N-k не делиться на 3, то покрасьте попарно столбы цвета первых N-k и цвета вторых N-k. Потом останутся какие-то столбы в конце другого цвета, но их количество точно будет делиться на 3 (доказательство этого факта придумайте сами. Рассмотрите какие могут быть остатки от деления на 3 у k и N-k). Раз у нас группа другого цвета состоящая из троек, то мы умеем ее перекрашивать.

    Этот вариант будет требовать не квадратичное, а O(n log n) количество операций.
    Ответ написан
  • Как правильно понять, клетка в шахматах 1 бит или 13 бит?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Если клетка может иметь 13 различных состояния, то надо log_2(13)=3.7004... бит. Т.е. если хранить каждую клетку отдельно, то она будет 4 бита.

    Дополнительный цвет клетки удвоит количество возможных вариантов. Будет нужно на 1 бит больше (log2(13*2)=log2(13) + log2(2) = log2(13)+1).

    Запомните, количество бит = логарифм от количества вохможных вариантов. Потому что каждый бит, имея 2 значения, умножает количество возможных вариантов значений на 2.
    Ответ написан
  • Как реализовать графические (мб логические) объекты, вложенные друг в друга, (окна в окнах (как матрешки))? Python? C++? ??

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    ООП. Объект - рамка. Должен содержать в себе список всех дочерних рамок (но не внуков - только тех, которые прямо в верхней содержатся, но не в чем другом).

    При рисовании новой рамки рекурсивно спускайтесь по этому дереву объектов, пока не получите тот элемент, в котором новая рамка целиком содержится.

    При спуске, если видите, что текущий объект не пересекается с рамкой - просто возвращайтесь. Если видите, что пересекается, то возвращайте ошибку - по условию новая рамка пересекаться не может. Если лежит строго внутри, то продолжайте поиск.

    Если видите, что все дети текущего объекта не пересекаются с рамкой, то вы нашли рамку - родителя вашего нового объекта. Добавьте новую рамку к детям этого объекта. Теперь пройдитесь по всем детям и, если они целиком внутри новой рамки - перенесите их в детей этого нового объекта.

    Как делать прорисовку? Опять же рекурсивный проход по дереву отсекает все элементы, которые не пересекаются с видимой областью. Те, которые пересекаются - сохраняются в какой-то список на прорисовку.

    Это если рамок не слишком много, скажем до 1000. В противном случае придется повозиться и городить всякие BSP-tree, kd-tree для быстрого поиска объектов, но вам это, похоже не надо. Это будет слишком сложно.
    Ответ написан
  • Как правильно хранить ключ шифрования для десктопных приложений?

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

    А с поролем - надо какой-то криптографически стойкой kdf-функцией преобразовать его в ключ шифрования и дальше применять хоть AES, хоть какой-то другой алгоритм шифрования.

    Главное самостоятельно ничего криптографического не велосипедить. Берите популярные крипто-библиотеки и используйте стандратные и современные криптографические приметивы.

    Тут, правда, есть проблема - если пользователь мастер пароль забудет - то сохраненные локально данные уже никак не достать. Можно полученный из пароля через KDF ключ как-то простенько зашифровать (или вообще в плейн тексте) и дополнительно выдать пользователю для сохранения на флешке и использовать для восставления пароля: если нет пароля, то ключ из файла применяется, потом данные шифруются с новым ключем, полученным из нового пользовательского пароля. Важно только убедить пользователя не хранить этот файл на том же компьютере. Если видите этот файл в папке с программой, на рабочем столе или в "моих документах" стоит отругать пользователя за пренебрижение к безопасности.

    Для проверки, что пароль правильный, данные надо снабдить какой то контрольной суммой (до шифрования).

    Все остальное - это security through obscurity. Не работает в долгой перспективе.
    Ответ написан
  • Как решить задачу на сложность алгоритмов ниже?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    г) не правильно подсчитано.

    Составьте уравнение. Вот есть у вас функция времени для n входных данных f(n) на компе B. На компе A время выполнения будет - f(n)/100, ведь он в 100 раз быстрее.

    Теперь обозначьте за x объем данных на компе A, который надо найти. Тогда у вас f(x)/100 = f(n). Подставьте нужную функцию вместо f() и найдите x. Спойлер, будет похоже, но не то, что у вас в вопросе указано.
    Ответ написан
  • Очень быстрый алгоритм умножения длинных чисел, куда копать?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    При умножении на маленькое число всякие хитрые алгоритмы типа преобразования Фурье или Карацубы лаже медленнее тупого умножения в лоб: Просто проходитесь по большому числу от младших разрядов к старшим, умножете на маленький множитель, прибавляете перенос. Потом берете остаток от деления на базу (если множитель маленький, то быстрее будет просто вычесть несколько раз в цикле вместо модуля), а результат целочисленного деления записываете в перенос.
    Ответ написан
  • Наиболее эффективная реализация алгоритмов преобразования BWT и MTF?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вот тут посмотрите: https://stackoverflow.com/questions/7857674/whats-...

    Идея - построить суффиксный массив (что почти тоже самое, что BWT). Там рекомендуют libdivsufsort. Вроде как, его можно использовать и в node.js: https://www.npmjs.com/package/divsufsort
    Ответ написан
  • Как реализовать поиск общих элементов двух массивов с помощью суффиксного дерева?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Для отсортированных массивов достаточно просто выполнить операцию слияния.

    Если массивы не упорядочены, или очень хочется деревом, то
    1) Строим суффиксное дерево для массива a[].
    2) Проходим по всем элементам массива b[] и смотрим, сколько раз подстрока из этого 1 элемента встречается в строке a[]. Это стандартная операция для суф. дерева: надо просто взять количество листьев в поддереве вершины, которая читается искомой строкой (в нашем случае - это непосредственный ребенок корня, к которому ведет строка, начинающаяся с символа b[i]).

    Еще конкретнее - постройте дерево, найдите для каждой вершины количество листьев в поддереве (просто суммируя эти же значения для всех детей или рекурсивно или поднимаясь снизу-вверх). Потом просуммируйте эти значения для всех вершин, в которые из корня есть ребро начинающееся с символа b[i] для всех i.
    Ответ написан
  • Как проверяется принадлежность точки многоугольнику методом углов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Я так понимаю, что это метод "подсчитать, сколько оборотов делает многоугольник вокруг точки".
    Для этого берем каждое ребро многоугольника (в каком-то порядке обхода, т.е. каждая точка для одного ребра первая, для другого - вторая), и считаем под каким углом этот отрезок виден из точки. Важный трюк тут - угол со знаком. Т.е. +30 градусов, если отрезок идет от первой точки ко второй против часовой стрелки, и -30, если точно такой же отрезок развернут.

    Для этого нужно взять векторное и скалярные произведения векторов на точки - это будут синус и косинус угла, умноженные на длины векторов. Их, даже не деля на длины, можно передать в функцию atan2(), и она даст вам значение угла. уже с правильным знаком. Хотя можно подстраховаться - угол должен быть от -пи до +пи. Если он больше пи, то нужно вычесть из него 2пи, если меньше -пи, то прибавить.

    Все эти углы просто суммируем. Если точка лежит снаружи, то ответ будет 0. Если точка внутри, то ответ будет +-2пи. Если точка лежит на границе - то черт его знает, но этот случай легко обнаружить. Если какой-то из суммируемых углов равен +-пи, то точка на отрезке. Еще отдельно надо бы проверить случай, что точка совпала с одной из вершин многоугольника. Там будет нулевой вектор, и atan не сработает.
    Ответ написан
  • Какой алгоритм использовать для определения минимального числа перестановок карт в колоде?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Правильный ответ - 52-<длина наибольшей общей подпоследовательности>.
    Выводится он так:
    1) Ни одну карту нет смысла двигать 2 раза. Т.е. ответ 52-<количество неподвижных карт>
    2) Неподвижные карты находятся в том же порядке в обеих колодах, следовательно они образуют наибольшую общую подпоследовательность.

    Наибольшая общая подпоследовательность - вообще-то это их обработки строчек тема, будем считать что у нас даны 2 52-символьные строки, один символ-одна карта, все символы разные. НОП - это такая наибольшая строка, которая останется, если выкинуть из первой и второй строки какие-то символы. Ищется она за квадратичную сложность (в данном случае - моментально, строчки-то фиксированной длины) динамическим программированием.

    F(i, j) - длина наибольшей общей подстроки у префиксов длины i у первой строки и длины j у второй.

    База F(0,*)=F(*,0)=0

    Переход: F(i,j) = max(F(i-1,j), F(i,j-1), F(i-1,j-1)+1). Третий вариант рассматривается только, если i-ый символ в первой строке и j-ый во второй равны.

    Ответ - 52-F(52,52) для вашей задачи

    Если надо выдать куда что перемещать, то задача чуть сложнее. Динамика модифицируется сохранением, какой из трех вариантов был выбран, чтобы потом восстановить НОП. Эти карты помечаются как неподвижные. Потом, для всех карт во второй колоде найдите их места в первой колоде. А потом, тупо, перемещайте подвижные карты по одной на нужные места в возрастающем порядке результирующих мест. Тогда не надо будет вообще учитывать пока не перемещенные карты.
    Ответ написан
  • Как изменить обычную сортировку вставками так, чтобы алгоритм использовал бинарный поиск?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Бесполезно прикручивать к сортировке вставками бинарный поиск. Кроме поиска места, куда вставляется новый элемент - надо еще и этот элемент вставить. При этом массиве придется сдвигать O(n) элементов при каждой вставке. В связном списке не пришлось бы сдвигать элементы, но там невозможно сделать бинарный поиск, потому что нет быстрого произвольного посика.

    Приведенная вами реализация - довольно быстрая. Тут поиск места вставки и сдвиги всех элементов объединены. Теоретически, можно сначала сделать бинарный поиск и вместо цикла while использовать, допустим, цикл for с фиксированным количеством итераций. Это сократит количество сравнений в цикле 2 раза, но добавит сколько-то сравнений и нелокальных обращений к памяти в бин.поиске. Возможно будет работать быстрее только если входные данные почти в обратном порядке заданы. В среднем же, будет работать хуже.

    Гораздо лучшая реализация была бы изначально зарезервировать первый элемент в массиве и записать туда очень маленькое число. А сами данные записывать после него. Тогда в цикле while не надо будет сравнивать index>0. Эта реализация будет гораздо быстрее дополнительного бинарного поиска.
    Ответ написан
  • Игры на алгоритмы

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Еще интересная игра — SpaceChem. Тут не совсем привычное программирование. Надо на плоском поле расставлять в клетках команды. Некоторый манипулятор двигается по полю, повинуясь командам и берет/отпускает атомы. Надо собирать из атомов определенные молекулы. Развивает не только алгоритмический образ мышления, но и воображение и память.
    Ответ написан