Сайт отличный — не раз пользовался им, когда нужно было быстро освежить в памяти некоторые детали.
Между прочим, сам Максим тот ещё молодец: его профиль на TopCoder
Каждый ключ имеет двух потомков — «левого» и «правого», как в бинарном дереве поиска. «Правый» потомок ключа является в то же время «левым» потомком следующего ключа.
В принципе, я здесь ничего дурного не вижу. Мы же не храним копии всех промежуточных массивов, и даже указатели не храним — мы их вычисляем по известному алгоритму. И пусть себе пересекаются на здоровье, проблем от этого не будет.
Тут дело в том, что элементы в матрице не просто отсортированы как один большой массив, а ОТДЕЛЬНО по каждой строке и ОТДЕЛЬНО (т.е. независимо от строк) по каждому столбцу.
Поэтому поиск нужно вести по каждой строке независимо от остальных, коих N штук, и это не просто O(N), а O(N * log(M)), так как в худшем случае придётся запускать N бинарных поисков.
Как я понимаю, каждая клетка в таком случае есть узел дерева, а два его потомка — это две таблицы, которые останутся при ходе вверх и вправо.
Вроде похоже (если не заснул окончательно ещё:))
Вообще-то это означает, что free является NaN
Между прочим, сам Максим тот ещё молодец: его профиль на TopCoder
Два из двух — 100%, однако :)
Ильич был сильно прав: телефон, телеграф и почта — наше всё :)
В принципе, я здесь ничего дурного не вижу. Мы же не храним копии всех промежуточных массивов, и даже указатели не храним — мы их вычисляем по известному алгоритму. И пусть себе пересекаются на здоровье, проблем от этого не будет.
Поэтому поиск нужно вести по каждой строке независимо от остальных, коих N штук, и это не просто O(N), а O(N * log(M)), так как в худшем случае придётся запускать N бинарных поисков.
Вроде похоже (если не заснул окончательно ещё:))
Но это «надо увидеть», а я проглядел:)