Блог пользователя iensen

Автор iensen, 14 лет назад, По-русски

На последней тренировке была такая "простая задача":найти определитель матрицы NxN (<=100)где

|числа| <=10^6

Я ,написал давно известный мне рекурсивный вариант за N^4-TL,Гаусса-TL/WA из за точности  в BigDecimal,если ставить >250-то TL9,иначе wa<9 )

Отчаявшись,скопировал краута с http://e-maxx.ru/algo/determinant_crout ,и получил те же самые TL./WA

Эту задачу мне приходится решать довольно часто,и мне хотелось бы узнать от решивших как ее можно было сдать :)

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А числа целые?
14 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится
Можно сдать, используя китайскую теорему об остатках. Вычислим наш определитель по 100 простым модулям, каждый порядка 10^9. После этого наш определитель однозначно восстанавливается. Например можно использовать алгоритм Гарнера. А для вычисления определителя по модулю просто делаем обычного Гаусса, где вместо делений обратные элементы. Единственная трудность, ответ может быть отрицательным, но ее тоже легко обойти, если X - определитель по модулю p1*p2*...*pn, где pi - это наши простые модули, то он отрицательный только тогда, когда X+X >= p1*p2*...*pn и тогда ответ это (X-p1*p2*...*pn).
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Точно! Cпасибо!!!100 000 000 на определители  на плюсах должно влезть в TL=2 s.

    Вроде и теорему знал,но еще нигде никогда не применял)

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Пардон. Допустим наша матрица имеет вид |15|. Возьмем n=1, p1=17 и посчитаем определитель по этому модулю. Получим, вроде бы, 15. 15+15=30, 30>17, значит следует вернуть -2 ?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если произведение p1*p2*...*pn намного больше максимально возможного абсолютного значения определителя, например как минимум в 3 раза, то понятно что не может быть такого, что этот определитель больше чем (p1*p2*...*pn)/2 поэтому и берем его как отрицательный. Возможно проще на примере, если у нас матрица из одного элемента, например (-5), а модуль 101, то наше значение по модулю 101 - это 96, понятно, что такого быть не может, поэтому ответ 96-101.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да, если принимать во внимание боооольшую величину p1*p2*...*pn, то все становится логично. Понял ). Но вот как наперед оценить возможный размер ответа, это уже другой вопрос. В данной задаче можно подобрать очевидный тест где ответ 10^600, но является ли это потолком.
        • 14 лет назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится
          Очевидно, что потолок 10^600*100!, так как всего перестановок 100! и каждая оценивается 10^600 - это число примерно равно 10^760, мы брали 720 знаков и оно прошло.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Неужели неизвестно точной оценки для определителя матрицы N x N, если каждый элемент по модулю не больше P ?
            • 14 лет назад, # ^ |
                Проголосовать: нравится +3 Проголосовать: не нравится
              Более точную оценку можно получить по неравенству Адамара

              Когда N - степень двойки, она точная.
              Пример матрицы строится рекурсивно.
              A1 = (P)

              Если N не степень двойки, то эта оценка все равно очень близка к истине. Для этой задачи она дает 10700, мне удалось построить пример где-то на 10692 и он есть в тестах. То есть по количеству цифр близко, но по отношению, конечно далеко. Но я уверен, что можно построить и лучший пример.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Подскажите пожалуйста как решать задачу H "Сумма произведений" с тренировки 5 октября. Я просто двигал этот перемножающий отрезок домножая с одного края и деля с другого, и складывал текущие результаты. Делил расширенным Евклидом, получил TLE 19.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Немного поэкспериментировав, можно заметить следующую формулу, которая очевидным образом доказывается по индукции.
    Собственно, формула для подсчета этой суммы, если a=1, b=x.

    1*2*...*n+...+x*(x+1)*...*(x+n-1)=(x*(x+1)*...*(x+n))/(n+1).
     Понятно, что в числителе (n+1) число => одно из них делится на (n+1), тогда его можно сразу поделить, а все остальное просто перемножить и посчитать по модулю. Тогда ответ получается как разность ответов для случаев a1=1, b1=b и a2=1, b2=a-1.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Можно в лоб, но главное чтоб без делений Евклидом.

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

    Обобщив идею, можно рассчитывать n соседних произведений за 2*n умножений.

    Становимся в позицию a+n и считаем n произведений влево и право: left и right.

    Очередное произведение находится по формуле: left[i]*right[n-i]

    Переходим к позиции a+2*n. И т.д.

  • 14 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    Данная последовательность произведений, есть не что иное как сумма убывающих факториальных степеней
    xn = x * (x - 1) * (x - 2) * ... * (x - n + 1)
    an + (a+1)n + (a+2)n + ... + (b+1)n = (bn+1-an+1) / (n+1)
    В Грекхеме подробно написано доказательство этого факта, да и в любой книжке я думаю в которой рассматривается теория конечных разностей
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

На этой тренировке была еще одна задача(которую никто не решил). Сводилась она к извлечению квадратного корня из числа порядка 10100000 . Не знает ли кто-нибудь её решения?

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    дихотомия + фурье не пройдет?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Что именно вы имеете в виду? Бинпоиском искать ответ и возводить в квадрат Фурье? Тогда вряд ли пройдёт, учитывая, что это n2log(n) (тем более, что можно сделать просто за квадрат безо всякого Фурье, но и такое проходить не должно). Или вы хотите как-то по-умному?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да, именно так - дихотомия по ответу, возведение в квадрат фурье и сравнение с числом. Для дихотомии можно задать хорошие границы - что то вроде от n >> (bitlength(n) + 3) до n >> (bitlength(n) - 3).

        Я не совсем понял, откуда n^2log(n). Одно возведение в квадрат за nlog(n), возведений будет немного (< 20), если моя оценка на границы дихотомии верна.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Если в числе n знаков, то вообще бинпоиску надо будет O(n) итераций сделать. И, кажется, такие "умные" границы всё равно лишь вдвое уменьшат число итераций бинпоиска, или около того.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Какая именно это задача?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    G
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      это же определитель.
      откуда там извлечение корня?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        А, сорри, промахнулся с деревом комментов :)

        С корнем - не помню номер, но суть - про "? 1 ? 2 ... ? N = K". Там легко заметить, что при фиксированном N можно получить все K от -N(N+1)/2 до N(N+1)/2, но только той же четности, что и эти границы. В общем, если научиться быстро вычислять корень (ну и, пожалуй, быстро умножать два числа, но это боян),  - тогда задача решена.

        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          ну при условии что корень существует его за O(n) можно найти в принципе. но тоже работа с длинными числами. 
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Ну там надо так, что если корня нет, то подойдёт любое число в окрестности +-1 от корня :)

            А как за O(n)? Что-то очень круто, быстрее даже, чем умножение двух длинных :)

            • 14 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
              сорри, перепутал с другим алго, глупость написал.

              я вот думаю, число знаков мы может оценить в корне точно. и если по ним уже пускать дихотомию с умножением?




              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Очевидно же, что это вам почти не даст ускорения - чисел с данным количеством цифр тоже O(n).
                Я вот думаю, может, её предполагалось за квадрат запихивать (особенно если учесть, что в другой задаче этого контеста с числами размера 100000 у нас квадрат прошёл)?
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  возможно и так.
                  меня гораздо более интересует решение задачи про количество красивых функций.
                  Если рассмотреть всевозможные степени перестановок, то очевидно, что при возведении в какую-то степень количество различных перестановок будем уменьшаться только если у нас степень d не взаимно проста с модулем K, где за K обозначим максимальную возможную степень  + 1
                  правильный ли это подход?
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  А что за метод такой - за чистый квадрат, без логарифмов?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересно, как решать I(сумма различных делителей).
  • 14 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +9 Проголосовать: не нравится
    Несложно доказать, что если N = p1a1 * p2a2 * ... * pnan, то можно представить все натуральные числа от 1 до
    , где k - минимальное такое, что выполняется
    (или k = n, если такое не выполняется)
    Значит задачу можно решить так: раскладываем N на простые делители (стандартно пробегом до корня из N) и поддерживаем максимальное число, которое можем получить из уже найденных делителей. Таким образом либо разложим N полностью, либо поймём, что следующий простой делитель больше чем текущее максимальное число.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А не можешь показать доказательство формулы?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Если p1 > 2, то ответ 2.

        Пусть N = 2a1p2a2...pnan. Понятно, что числа от 1 до можно представить в виде суммы различных делителей. (Используя только степени двойки).
        Если M1 < p2 - 1, то понятно, что число M1 + 1 представить не получится.
        Пусть M1 ≥ p2 - 1. Пусть x = x0 + p2x1 + p22 x2 + ... + p2a2xa2, где xi ≤ M1, тогда xi можно представить в виде суммы различных делителей числа N1 = 2a1, значит и x можно. Таким образом можно представить все числа от 1 до .

        Дальше аналогично.
14 лет назад, # |
Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится
Вот ссылка на разбор всех задач этого контеста. (Я автор последних 4-х задач).
http://www.repetitor.ua/files/folders/8889/download.aspx
Эффективное вычисление корня из N за O(log2N) разобрано в лекции
http://www.repetitor.ua/files/folders/8890/download.aspx
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Что-то ссылки не открываются :(
    Значит, в задаче про корень предполагался таки квадрат от количества цифр? Зачем тогда надо было делать такие длинные числа? Чтобы все помучались с оптимальной реализацией? :)
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Сейчас выложу куда-нибудь по-нормальному.

      О корне.
      Важно, что мы можем взять большое основание 10000, и искать очередную цифру за константу.
      и квадрат здесь на самом деле от количества цифр корня, а не от числа, то есть это уже величина порядка 12500, что для квадратной сложности вполне нормально.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    По первой ссылке лежит то, что должно быть по второй, а вторая не работает.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вопрос по задаче тоже с ИТМО. Там была игра - типа нима. Дана куча из n камней и 1ый игрок берет от 1 до n-1 камней. второй может взять не больше удвоенного числа камней взятых первым и т.д. Я написал брут и он показал что проигрышные позиции для первого это числа Фибоначчи ( может тут накосячил конечно? ) Но там было n <= 10 ^ 100000. Вот и вопрос. Как определить что число - это число фибоначчи при таких ограничениях?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Задача была выставлена в первый день Севастопольских сборов(день Дмитрия Кордубана)

    Мы решали ее так. Забьем в какую-то сету хеши первых примерно 500000 чисел Фибоначчи(просто посчитаем их по модулю 2^64). Посчитаем наше входное число по этому же модулю. Если результат есть в сете - считаем, что наше число - число Фиббоначи, иначе - нет. Сомневался до последнего, что такое решение пройдет - но нет, все-таки прошло:-)

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Хм... Интересно) Я писал типа такого же - только считал по 2ум модулям простым - не прошло) Любопытно) Видимо кривые модули были
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Там еще с константой надо быть осторожным. Если память мне не изменяет, загнав в сет первые 400000 чисел Фиббоначи, мы получили WA.
14 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
думается мне по старшим нескольким цифрам и количеству разрядов мы довольно точно можем оценить номер данного числа в последовательности фиббоначчиевых. если и промахнёмся то на несколько чисел. 10^100000 это примерно (10^9)^11200, что можно найти возведением матрицы в степень если тл не очень туг.