• В чем моя ошибка в задаче?

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

    Но вот случай, когда достаточно одного числа вы неправильно разобрали. Почему вы ищите самое большое простое число? Какой вообще смысл смотреть, что в позиции ans-1 стоит c?

    А еще ваш код выводит 0 неверно иногда.

    Вы, может, задачу неправильно поняли? Надо сделать так, что бы все позиции, в которых символы отличные от c, не делились бы на хотя бы одно число в вашем ответе.
    Ответ написан
    1 комментарий
  • Как настроить сборку для линковки двух разных версий одной библиотеки?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Автоматический метод могу предложить только один: перезагрузите компьютер. Если не помогло, то придется искать ошибку в коде.
    Ответ написан
    8 комментариев
  • Почему LCS алгоритм находит совпадение в конце последовательности?

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

    Построение матрицы менять не надо, оно просто считает оптимальную длину LCS. Вам надо отдавать приоритет переходам вверх (или влево) пока это возможно при восстановлении ответа.

    Но можно сделать простой хак - усеките ваш текст как можно короче, пока LCS все еще оптимального размера.

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

    От этой позиции и запускайте ваш DoDiff вместо левой нижней ячейки матрицы.

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

    Вам еще придется в конце зарепортить необходимое количество l3diffDeleted или l3diffAdded, чтобы восстановить усеченную часть.
    Ответ написан
    1 комментарий
  • Как тут применить китайскую теорему об остатках?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Найдите остаток от деления искомой штуки на 4 и на 25. Далее примените китайскую теорему об остатках.

    Так проще, потому что остаток от деления a^(b^c) на степень простого числа можно найти по малой теореме Эйлера:

    a^(b^c) = a ^ (b^c % (p-1)p^(n-1)) mod p^k.

    Т.е. 7^9^9 = 7^((9^9) % 20) mod 25

    9^9 % 20 уже можно вычеслить через логарифмическое возведение в степень.

    Аналогично для 4.

    Правда, тут можно и без теоремы об остатках. Надо просто сразу применить теорему ейлера. фи(100) надо только аккуратно вычислить. И числа будут чуть больше, но все-равно подъемные.
    Ответ написан
    Комментировать
  • Как "нормально" перевести float в int?

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

    Edit: Видимо, проблема в том, что 0.9 нельзя идеально точно представить в float. На самом деле там хранится что-то вроде 0.8999999.... При домножении на 10 и округлении вниз вы получите 8, а не 9.

    Надо использовать округление к ближайшему - round.
    Ответ написан
    1 комментарий
  • Как в двоичном дереве поиска найти минимальный элемент, больший данного?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Надо, как в бинарном поиске - идти или в левое или в правое поддерево. Если пошли в левое поддерево, то надо проверить, что вернула рекурсивная функция - если там не было больших элементов, то надо вернуть значение в текущей вершине.
    Ответ написан
    3 комментария
  • Как к html странице подключить css на своем Http-Серевере?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если стили не встроены прямо в html файл, то css - это просто ресурс на сервере, как и html страница, как картинки или js скрипты. Браузер сам делает запрос по адресу, прописанному в Html теге на странице. Сервер должен лишь отдавать правильый mime type у файла.
    Ответ написан
  • Как расширить массив с++ (добавить элемент)?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Используйте std::vector. Он автоматически расширяется и при этом работает быстро.
    Ответ написан
  • Член класса/структуры типа uint8_t * или int8_t *, оптимизация?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Тут проблема не в том, что член класса char*, а в том, что запись идет в char*, и из-за strict aliasing правил - это может быть запись куда угодно, в том числе в &this. Кешировать пришлось бы любой член структуры, любого типа.

    Эту же проблему можно воспроизвести в меньшем масштабе, если у вас в цикле есть запись в int* и чтение какой-то другой не меняющейся int переменной. Особенно, когда переменная в куче и указатель пришел в параметре функции. Вот компилятор офигеет и будет на каждой итерации ее загружать в регистр заново. Опять же, потому что ну не может он понять, что вот этот вот указатель не указывает на вот эту вот переменную.

    Частично это можно решить кешированием, можно попробовать поменять типы кое где. Но делать это не стоит - это та самая преждевременная оптимизация, о которой писал Кнут. Лучше алгоритм хороший и структуры данных правильные в вашей программе выберите. А уже дальше, если профилирование покажет, что вот тут вот узкое место, то можно смотреть на ассемблерный код и думать, как убедить компилятор геренировать что-то более быстрое.
    Ответ написан
  • Почему не получается найти подпоследовательность?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    У вас решение за O(MN), когда как можно за O(M log N).

    Вы говорите, что оно линейно, но вы выполняете линейное количество операций на каждый элемент массива b. Это медленно. Ваша проблема в том, что вы храните все индексы для каждого значения просто в списке и потом там наивно ищите первое вхождение больше данной границы. Можно список хранить в Set. Вот я не в курсе, умеет ли он, как C++-шный set искать первый элемент больше заданной границы. Если нет, то можно тупо хранить отсортированые списки индексов, тогда там можно будет делать бинпоиск.
    Ответ написан
    7 комментариев
  • Как вывести на экран все значения элементов лежащих по одному ключу в std::map?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Нужно использовать multimap, а котором ключами будут фамилии. Тогда можно вывести все телефоны по фамилии пройдясь мо этому мапу с lower_bound до upper_bound. Похоже там, откуда вы списывали примерно такая идея и была. Иначе зачем вам два абсолютно одинаковых map в коде (surname_book есть точная копия phone_book)?
    Ответ написан
  • Как соеденить массив строк в одну строку и разделить пробелами?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Если это С++ и вы используете std::string, то можно строки тупо суммировать через +=.

    Если по условию задания вам надо делать все руками, то нужно выделить память, чтобы все поместилось, а дальше можно воспользоваться strcat_s, memcpy или вообще посимвольно копировать.
    Ответ написан
    Комментировать
  • Не правильно сортируется параллель под побочной диагональю. Что не так и что надо исправить?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вы этот код хотя бы раз целиком прочитали? Кажду строчку? Вот поствьте перед мониторо кружку. Представьте, что это ваш друг-студент, который пытается списать у вас задание, но ничего не понимает. Вот объясните ему, строчка-за-строчкой, что происходит в вашем коде, что он должен делать, как должен работать.

    Вам должно сразу стать понятно, что в одной строчке написан полный, абсолютный, дисстилированный бред.
    Ответ написан
    5 комментариев
  • Как узнать сколько байт прочитал std::ifstream.read()?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Ну посмотрите в документацию же.

    Там английским по белому написано:
    The number of characters successfully read and stored by this function can be accessed by calling member gcount.


    И даже пример внизу есть.
    Ответ написан
    Комментировать
  • Как сделать перебор всех значений строки определенной длины состоящей из цифр и букв?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Ну вот как вы прибавляете 1 к числу из 0..9 прибавляйте 1 к числу, где цифры могут быть 0..9 и a..z. Все z в конце замените на 0, следующий символ увеличте на 1 (если стало '9'+1, то Замените на 'a').
    Ответ написан
    Комментировать
  • Почему решение задачи неправильное?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    is_subsequence написана с ошибкой. Что у вас там за алгоритм? Почему вы считатете, что оно должно работать?

    Оно, например, не работает на тесте s="abc" t="zzzzzcba". Ваша реализация скажет, что abc является подпоследовательностью, хотя на самом деле - нет.

    Еще хочется отдельно привлечь внимание к гениальности кода:
    if (is_sub)
            return true;
        else
            return false;


    Он кажется мне немного перемудренным.
    Ответ написан
    1 комментарий
  • Почему быстрая сортировка Хоара медленнее пузырьковой?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Во-первых, quicksort медленне всяких пузырьков на маленьких числах. Это нормально. У него ассимптотика лучше - он сильно быстрее на больших числах. Но константа из-за сложности алгоритма хуже - поэтому на маленьких числах он и проигрывает пузырьку. Во всех библиотечных реализациях квиксорта (да и любой другой логарифмической сортировки) там есть проверка, что если чисел мало, то запускать пузырек или сортировку вставками.

    Увеличте размер сортруемых массивов до 100 000 или до миллиона и квиксорт должен стать быстрее.

    Во-вторых, ваша быстрая сортировка написана весьма неоптимально. Пузырек у вас сортирует сам массив на месте, когда как квиксорт постоянно создает новые массивы через конкатенацию. Возьмите нормальную реализацию и на 1000 элементах квиксорт уже станет быстрее пузырька.
    Ответ написан
    Комментировать
  • Найдите перестановку по её номеру в лексикографическом порядке. Total - кол-во элементов, К - номер перестановки. Как сократить время программы?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вы генерируете перестановки по одной, пока не отсчитаете k. Это медленно, потому что k может быть очень большим. Перестановок-то n! - это дофига много.

    Надо генерировать ее сразу по номеру.

    Посмотрите на первый элемент. У первых (n-1)! перестановок там 1, у следующих (n-1)! - там 2, потом идет группа, начинающихся с 3 и т.д.

    Уже вы можете понять в какой группе искомая k-ая перестановка. Тупо floor(k/(n-1)!) (если нумерация с 0 и перестановок и групп). Фактически, формула для первого элемента - a[0] = (k-1)/(n-1)! + 1.

    Дальше вы можете выкинуть из рассмотрения первый элемент. Сфокусируйтесь на группе с заданным известным первым элементом. Какой номер искомая перестановка имеет среди этих (n-1)!? Надо из k вычесть количество перестановок c меньшими первыми элементами (их (a[0]-1)*(n-1)!. Потом задача сводится к преведущей - сгенерировать k-ую перестановку среди оставшихся n-1 элементов.

    Если использовать какое-нибудь дерево отрезков, чтобы быстро искать j-ый пока не занятый элемент, то все решение будет за O(n log n). Если делать совсем просто - двумя циклами - то будет O(n^2). Гораздо быстрее вашего O(n!).

    Надо только аккуратно обработать случаи, когда (n-1)! слишком большое. Фактически, вам надо найти максимальный факториал, который меньше k. Пока не спуститесь до этого момента нужно сразу брать первый незанятый элемент и не считать факториал вообще.
    Ответ написан
    Комментировать
  • Самомодифицирующийся код на c++ изменяющий значения переменой для нового запуска?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    На винде это можно сделать только в виде двух исполняемых файлов. Первый, внешний файл - просто запускает основной второй и ждет, когда он завершится. Когда вызываемый файл завершится, запустивший его может редактироват экзешник. Тут надо разбираться с форматом исполняемых файлов и дальше надо просто переписать байтики в определенной позиции в секции .rdata или что там будет.

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

    В линуксе можно исполняемый файл редактировать, пока он запущен - поэтому там попроще. Чтобы бороться с sigkill стоит редактировать файл в самом начале после запуска.
    Ответ написан
  • Как доказать что последовательные производные также имеют вещественные корни?

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

    Если нет кратных корней - то все просто. У вас n-1 последовательный промежуток между двумя корнями. На каждом должен быть ноль производной.

    Теперь, допустим есть какой-то корень степени k > 1.

    Тогда P(x) = (x-a)^k Q(x).

    Если взять производную, то видно, что она делится на (x-a) в степени k-1, т.е имеет k-1 корней:

    P'(x) = k*(x-a)^(k-1)*Q(x)+(x-a)^k*Q'(x)

    Т.е, если у вас m различных корней (суммарной кратностью n), то производная, как и в первом случае имеет m-1 корней между корнями P(x) и еще n-m раз повторяет корни полинома как во втором случае. Суммарно - n-1 вещественных корней, значит все корни - вещественные.
    Ответ написан
    Комментировать