Не только. Если лист в середине и спрашивается опять, то он должен быть поднят наверх.
Для этого нужен именно двусвязанный список и еще хеш-таблица, для отслеживания какой лист на каком месте. Как правильно сказали в самом первом комментарии.
Мне кажется это проблема присуща большинству структур данных.
— двоичный поиск будет попадать мимо кеша поначалу
— AVL и RB -деревья тоже могут попадать мимо кеша
А большинство сортировок похоже будут хорошо ложится в кеш:)
Поясню, а то два разных ответа. Я ответил про простой случай, в котором нет возможности FindNext и FindPrevios, а Invizory выше про дерево уже с такими возможностями.
Такие соотношения вообще можно держать в хеше, и получится быстродействие O(N) (если грубо), что оптимальнее данного алгоритма, особенно на практике.
Но чаще держат в B-деревьях, так как они оптимизированы под работу блочной структурой диска со сложность N log N.
А что с памятью? Вроде в статье есть беглая оценка в O(U) — это странно.
Ведь если каждая операция log(log(U)) времени, то памяти займем не более чем n * log(log(U)), если не делать зверских предобработок.
1. Написать, что after[k] берется равным bf * before[k].
2. Фраза где K — количество камней… явно имеется в виду где K — номер кучки и т.д.
3. Показать, что, что after[k] < before[k], за счет выбора k.
Если bf != 0, то нужно определить, какой ход приведет в проигрышное состояние (т.е, af == 0):
af = bf ^ before[k] ^ after[k] = bf ^ before[k] ^ (af ^ before[k]) = 0, где k — то количество камней из кучки before[k], старший ненулевой бит которого отличается от нуля. Так как при это ходе xor-сумма равна нулю, то теорема доказана.
Вообще переход не простой. ИМХО можно написать подробнее, а тут еще и ошибка, так что врубиться в него могут только настойчивые.
Как минимум надо переписать так:
Если bf != 0, то нужно определить, какой ход приведет в проигрышное состояние (т.е, af == 0):
af = bf ^ before[k] ^ after[k] = bf ^ before[k] ^ (bf ^ before[k]) = 0, где k — то количество камней из кучки before[k], старший ненулевой бит которого отличается от нуля. Так как при это ходе xor-сумма равна нулю, то теорема доказана.
Если bf == 0, то текущее состояние или и так проигрышное (т.е, из него нет переходов), или переходы имеются, но для них выполняется равенство af == bf[i] ^ af[i], но так как before[i] != after[i], а bf != 0, то переход ведет в выигрышное состояние.
1. Вначале предполагается, что bf == 0, а затем используется, что bf != 0.
2. В одном предложении используются то before[i], то bf[i]. Разные ли это вещи?
Предлагаю переписать, на что-то вроде:
Если bf = 0, то текущее состояние или и так проигрышное (т.е, из него нет переходов), или переходы имеются, но для них выполняется равенство af = bf[i] ^ af[i], но так как bf[i] != af[i], то af != 0, а значит переход ведет в выигрышное состояние по индукции.
Натуральные и положительные числа в сумме не дают 0, если их самих не ноль. Это, хотел сказать GORKOFF. Если конечно там не имеется в виду xor-сумма, но вроде там еще рано.
Мне кажется эту фразу просто можно выкинуть.
Да, я понял, что неправ) Думал, что стандартные перестановки работают только с перестановками без повторяющихся элементов. Эта задача старая. В те времена были задачи, которые сейчас можно решить стандартными средствами (их немного).
Я хотел сказать, что стандарты знать надо, но большинство задач имеют алгоритм решения по месту.
Например, могли попросить генерировать правильные скобочные последовательности, какие-нибудь обходы или еще чего. Тут стандартом не обойдешься, придется думать алгоритм по месту. Но в целом ваше замечание правильное.
Для этого нужен именно двусвязанный список и еще хеш-таблица, для отслеживания какой лист на каком месте. Как правильно сказали в самом первом комментарии.
Я не являюсь организатором и опубликовал эту новость по просьбе знакомого.
Пытаюсь у непосредственных организаторов выяснить, почему не доступны другие заявленные языки.
— двоичный поиск будет попадать мимо кеша поначалу
— AVL и RB -деревья тоже могут попадать мимо кеша
А большинство сортировок похоже будут хорошо ложится в кеш:)
Такие соотношения вообще можно держать в хеше, и получится быстродействие O(N) (если грубо), что оптимальнее данного алгоритма, особенно на практике.
Но чаще держат в B-деревьях, так как они оптимизированы под работу блочной структурой диска со сложность N log N.
А те же проверки заменятся на равно (не равно) null.
Ведь если каждая операция log(log(U)) времени, то памяти займем не более чем n * log(log(U)), если не делать зверских предобработок.
2. Фраза где K — количество камней… явно имеется в виду где K — номер кучки и т.д.
3. Показать, что, что after[k] < before[k], за счет выбора k.
Если bf != 0, то нужно определить, какой ход приведет в проигрышное состояние (т.е, af == 0):
af = bf ^ before[k] ^ after[k] = bf ^ before[k] ^ (af ^ before[k]) = 0, где k — то количество камней из кучки before[k], старший ненулевой бит которого отличается от нуля. Так как при это ходе xor-сумма равна нулю, то теорема доказана.
Вообще переход не простой. ИМХО можно написать подробнее, а тут еще и ошибка, так что врубиться в него могут только настойчивые.
Как минимум надо переписать так:
Если bf != 0, то нужно определить, какой ход приведет в проигрышное состояние (т.е, af == 0):
af = bf ^ before[k] ^ after[k] = bf ^ before[k] ^ (bf ^ before[k]) = 0, где k — то количество камней из кучки before[k], старший ненулевой бит которого отличается от нуля. Так как при это ходе xor-сумма равна нулю, то теорема доказана.
Если bf == 0, то текущее состояние или и так проигрышное (т.е, из него нет переходов), или переходы имеются, но для них выполняется равенство af == bf[i] ^ af[i], но так как before[i] != after[i], а bf != 0, то переход ведет в выигрышное состояние.
1. Вначале предполагается, что bf == 0, а затем используется, что bf != 0.
2. В одном предложении используются то before[i], то bf[i]. Разные ли это вещи?
Предлагаю переписать, на что-то вроде:
Если bf = 0, то текущее состояние или и так проигрышное (т.е, из него нет переходов), или переходы имеются, но для них выполняется равенство af = bf[i] ^ af[i], но так как bf[i] != af[i], то af != 0, а значит переход ведет в выигрышное состояние по индукции.
почтивсегда преподают, что 0 не натуральное.А статья на русском, значит логично заменить на неотрицательные.
Мне кажется эту фразу просто можно выкинуть.
Я хотел сказать, что стандарты знать надо, но большинство задач имеют алгоритм решения по месту.
Например, могли попросить генерировать правильные скобочные последовательности, какие-нибудь обходы или еще чего. Тут стандартом не обойдешься, придется думать алгоритм по месту. Но в целом ваше замечание правильное.