На последней тренировке была такая "простая задача":найти определитель матрицы NxN (<=100)где
|числа| <=10^6
Я ,написал давно известный мне рекурсивный вариант за N^4-TL,Гаусса-TL/WA из за точности в BigDecimal,если ставить >250-то TL9,иначе wa<9 )
Отчаявшись,скопировал краута с http://e-maxx.ru/algo/determinant_crout ,и получил те же самые TL./WA
Эту задачу мне приходится решать довольно часто,и мне хотелось бы узнать от решивших как ее можно было сдать :)
Точно! Cпасибо!!!100 000 000 на определители на плюсах должно влезть в TL=2 s.
Вроде и теорему знал,но еще нигде никогда не применял)
Когда N - степень двойки, она точная.
Пример матрицы строится рекурсивно.
A1 = (P)
Если N не степень двойки, то эта оценка все равно очень близка к истине. Для этой задачи она дает 10700, мне удалось построить пример где-то на 10692 и он есть в тестах. То есть по количеству цифр близко, но по отношению, конечно далеко. Но я уверен, что можно построить и лучший пример.
Можно в лоб, но главное чтоб без делений Евклидом.
Очевидно как посчитать два соседних произведения только через умножения, используя их перекрываемость.
Обобщив идею, можно рассчитывать n соседних произведений за 2*n умножений.
Становимся в позицию a+n и считаем n произведений влево и право: left и right.
Очередное произведение находится по формуле: left[i]*right[n-i]
Переходим к позиции a+2*n. И т.д.
На этой тренировке была еще одна задача(которую никто не решил). Сводилась она к извлечению квадратного корня из числа порядка 10100000 . Не знает ли кто-нибудь её решения?
А, сорри, промахнулся с деревом комментов :)
С корнем - не помню номер, но суть - про "? 1 ? 2 ... ? N = K". Там легко заметить, что при фиксированном N можно получить все K от -N(N+1)/2 до N(N+1)/2, но только той же четности, что и эти границы. В общем, если научиться быстро вычислять корень (ну и, пожалуй, быстро умножать два числа, но это боян), - тогда задача решена.
Ну там надо так, что если корня нет, то подойдёт любое число в окрестности +-1 от корня :)
А как за O(n)? Что-то очень круто, быстрее даже, чем умножение двух длинных :)
Я вот думаю, может, её предполагалось за квадрат запихивать (особенно если учесть, что в другой задаче этого контеста с числами размера 100000 у нас квадрат прошёл)?
Пусть 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 до
Дальше аналогично.
http://www.repetitor.ua/files/folders/8889/download.aspx
Эффективное вычисление корня из N за O(log2N) разобрано в лекции
http://www.repetitor.ua/files/folders/8890/download.aspx
Значит, в задаче про корень предполагался таки квадрат от количества цифр? Зачем тогда надо было делать такие длинные числа? Чтобы все помучались с оптимальной реализацией? :)
О корне.
Важно, что мы можем взять большое основание 10000, и искать очередную цифру за константу.
и квадрат здесь на самом деле от количества цифр корня, а не от числа, то есть это уже величина порядка 12500, что для квадратной сложности вполне нормально.
Задача была выставлена в первый день Севастопольских сборов(день Дмитрия Кордубана)
Мы решали ее так. Забьем в какую-то сету хеши первых примерно 500000 чисел Фибоначчи(просто посчитаем их по модулю 2^64). Посчитаем наше входное число по этому же модулю. Если результат есть в сете - считаем, что наше число - число Фиббоначи, иначе - нет. Сомневался до последнего, что такое решение пройдет - но нет, все-таки прошло:-)