• Zero tolerance mode in effect!

Задачи, головоломки, загадки

А-а, вы про числа, которые не влазят в самое длинное слово. Ну, ладно, предположим. Только "числа длиной лог(Н)" тут по-прежнему ни при чем.

И какие арифметические действия надо эмулировать? Все решается ксорами.

Я пока ещё не придумал как всё решить через ксоры. В моём решении надо считать квадраты.
Ладно, надеюсь, завтра додумаю.
 
Любое число N в бинарном виде записывается (в твоей терминологии "состоит из") n=[log2(N)]+1 битами
Ну да, то есть для размещения массива из N чисел потребуется N × log N битов, а значит только для того чтобы просмотреть этот массив потребуется О(N log N) времени.
Все решается ксорами.
:muscle:
 
Никаких квадратов. Можно и без ксоров и без квадратов, но тогда не всегда гарантируется О(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).
Это да.
 
Без ксоров по-прежнему О(1) доп памяти, но потенциально больше
Похоже все равно там потребуется log N дополнительной памяти. Так? Не вижу в этом большого смысла, хотя... Мой алгоритм с ксорами требует двойного просмотра массива, если можно обойтись одним промотром, то стоит потратить на это log N памяти. В моем варианте это возможно, но это все равно требует ксора или другой элементарной операции сложностью log N.
 
В этом плане мне нравится задача - написать функцию вычисляющую N-е число Фибоначчи. Если N помещается в машинное слово Если результат помещается в машинное слово, то это не слишком сложно, т.к. можно легко предложить алгоритм сложностью О(1). А вот если N не ограничено, то придется попотеть чтобы найти решение сложностью О(N).
 
Последнее редактирование:
охоже все равно там потребуется log 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). Что, насколько я понимаю, проигрывает тому решению что я изначально привёл.
 
Минуточку, коллега.
:)
Теперь задача: найти алгоритм для поиска двух отсутствующих целых за асимптотическое время в O (N * log N).
Я конечно понимал, что условие прошлой задачи наложится на новую, но не мог же я явно подчеркнуть, что можно больше одного прохода. Прошу прощения за невольное сознательное введение в заблуждение.
 
ПС. Сознательное, т.к. была надежда, что кто-то предложит решение в один проход. Тем более что оно есть. ;)
 
Итак, снова пятница, а значит пришло время новой задачки для мегамозгов.

В известной игре Тетрис имеется 7 видов плоских фигур, которые можно составить из 4-х квадратиков. Все остальные фигуры можно получить поворотом одной из стандартных 7-ми.

Задача: заполнить семью стандартными фигурами тетриса прямоугольник 7х4 так, чтобы каждая фигура использовалась ровно один раз.
 
Экипаж, где решения? Не будет до завтра решений, начну выкладывать подсказки.
 
Если софтом найти решения, то будет двойной зачет.
Ты недооцениваешь суперкодеров. Они сложат. Потом, правда, найдут ма-аленький бажок, но это уже никого не будет волновать - проект-то закончен: открывай баг - починим.
 
Кстати, есть отличное продолжение (значительно более сложное) этой деццкой задачки.
 
А доказать?
Ты недооцениваешь суперкодеров. Они сложат. Потом, правда, найдут ма-аленький бажок, но это уже никого не будет волновать - проект-то закончен: открывай баг - починим.
Не тот случай. Найти решение трудно, но проверить верно ли оно - легко.
Кстати, есть отличное продолжение (значительно более сложное) этой деццкой задачки.
Давай.
 
Назад
Сверху Снизу