Вы используете устаревший браузер. Этот и другие сайты могут отображаться в нём некорректно. Вам необходимо обновить браузер или попробовать использовать другой.
Ну да, то есть для размещения массива из N чисел потребуется N × log N битов, а значит только для того чтобы просмотреть этот массив потребуется О(N log N) времени.
Никаких квадратов. Можно и без ксоров и без квадратов, но тогда не всегда гарантируется О(1) доп памяти. Но если это требование смягчить, то ляхко обходимся без ксоров.
Ну да, то есть для размещения массива из N чисел потребуется N × log N битов, а значит только для того чтобы просмотреть этот массив потребуется О(N log N) времени.
Эт я поал, я не поал клаузы "числа настолько большие, что состоят из лог(Н) битов". Это кагбэ от размера числа не зависит - число битов всегда /лог2(Н)+1/.
Эт я поал, я не поал клаузы "числа настолько большие, что состоят из лог(Н) битов". Это кагбэ от размера числа не зависит - число битов всегда /лог2(Н)+1/.
Это конечно верно, просто в таких задачах у суперкодеров принято предполагать по умолчанию что N помещается в элементарное машинное слово (32 или 64 или 128 бит, не суть) и тогда все элементарные операции принято считать выполняющимися за О(1).
Если же N гораздо больше, то элементарные операции начинают стоить больше чем О(1).
Кстати, я там криво выразился. Без ксоров по-прежнему О(1) доп памяти, но потенциально больше (раз уж мы биты считаем), чем с ксорами. Но я не суперкодер, мне простительно.
Это конечно верно, просто в таких задачах у суперкодеров принято предполагать по умолчанию что N помещается в элементарное машинное слово (32 или 64 или 128 бит, не суть) и тогда все элементарные операции принято считать выполняющимися за О(1).
Если же N гораздо больше, то элементарные операции начинают стоить больше чем О(1).
Похоже все равно там потребуется log N дополнительной памяти. Так? Не вижу в этом большого смысла, хотя... Мой алгоритм с ксорами требует двойного просмотра массива, если можно обойтись одним промотром, то стоит потратить на это log N памяти. В моем варианте это возможно, но это все равно требует ксора или другой элементарной операции сложностью log N.
В этом плане мне нравится задача - написать функцию вычисляющую N-е число Фибоначчи. Если N помещается в машинное слово Если результат помещается в машинное слово, то это не слишком сложно, т.к. можно легко предложить алгоритм сложностью О(1). А вот если N не ограничено, то придется попотеть чтобы найти решение сложностью О(N).
Ну так сходу вроде нет. Потенциально дополнительная память нужна для впихивания в нее суммы массива, то бишь N^2. Но если числа не лезут в слово, то да.
Ну, примерно, так. Один раз целиком, второй - когда нашел недостающий ксор - половинками. За один раз можно, но тогда со "счетами" и там скорее всего снова всплывет log(N)
Похоже все равно там потребуется log N дополнительной памяти. Так? Не вижу в этом большого смысла, хотя... Мой алгоритм с ксорами требует двойного просмотра массива, если можно обойтись одним промотром, то стоит потратить на это log N памяти. В моем варианте это возможно, но это все равно требует ксора или другой элементарной операции сложностью log N.
Минуточку, коллега. Тот что разрешено 2 прохода по массиву - это всё меняет! Я ведь пытаюсь решить это за 1 проход, при этом не выходя за требования по памяти и кол-ву операций!
Конечное кол-во проходов по данным не влияет на О-алгоритма, но в начальном условии не кто иной как лично Вы требовали найти решение именно за 1 проход!
А вот вариация для продвинутых членов экипажа носящих городое имя Кодер.
Все то же, только в массиве сидят все числа от 1 до N+2 кроме двух! Нужно за один проход найти недостающие числа (опять же не выделяя отдельного массива).
Скажем так, во-первых, говоря теоретически, т.е. игнорируя размер регистра и то что операция со всеми его битами является по сути одной коммандой, разумеется что O(N*log(N)) - это нижний лимит, меньше этого никак. Т.е. это просто "посмотреть" на биты всех N чисел.
Меньше O(log(N)) памяти тоже нельзя, т.к. это просто величина одного элемента. Вобщем-то сам ответ уже O(log(N)).
Если разрешается совершить два прохода, то задача решается довольно легко таким образом:
Первый проход: находим XOR всех чисел, и XOR-им его с "каноническим" значением. Полученное значение - не 0, т.к. это означало бы что пропущенные числа равны.
Выбираем любой ненулевой бит.
Второй проход: находим отдельно XOR всех чисел в которых этот бит 1, и отдельно тех где этот бит 0. XOR-им с "каноническими" значениями. Получаем ответ.
Если разрешается дополнительно O(log(N)) памяти, т.е. по сути O(log(N)^2), то задачу можно решить за один проход (просто изначально высчитывать массив потенциально полезных значений, и потом выбрать). Но в этом случае потребуется также больше операций, O(log(N)^2). Что, насколько я понимаю, проигрывает тому решению что я изначально привёл.
Я конечно понимал, что условие прошлой задачи наложится на новую, но не мог же я явно подчеркнуть, что можно больше одного прохода. Прошу прощения за невольное сознательное введение в заблуждение.
Итак, снова пятница, а значит пришло время новой задачки для мегамозгов.
В известной игре Тетрис имеется 7 видов плоских фигур, которые можно составить из 4-х квадратиков. Все остальные фигуры можно получить поворотом одной из стандартных 7-ми.
Задача: заполнить семью стандартными фигурами тетриса прямоугольник 7х4 так, чтобы каждая фигура использовалась ровно один раз.
Ты недооцениваешь суперкодеров. Они сложат. Потом, правда, найдут ма-аленький бажок, но это уже никого не будет волновать - проект-то закончен: открывай баг - починим.
Ты недооцениваешь суперкодеров. Они сложат. Потом, правда, найдут ма-аленький бажок, но это уже никого не будет волновать - проект-то закончен: открывай баг - починим.
На данном сайте используются файлы cookie, чтобы персонализировать контент и сохранить Ваш вход в систему, если Вы зарегистрируетесь.
Продолжая использовать этот сайт, Вы соглашаетесь на использование наших файлов cookie.