Задача на миллион

заебашить хэштаблицу

Угу, что-то сразу не подумал.

заебашить хэштаблицу

Угу, что-то сразу не подумал.

лошара

ОТВЕТ 42

ОТВЕТ 42

Массив реально доступных 1кк инт32 ты никак не сможешь хранить в меньшем объеме, это тупо физически невозможно.

Можешь слить в строку и сжать гзипом например, в словарь запихнуть или еще как-нибудь заархивировать, но это уже не просто массив с инт32.

не ну подразумевается, что я его как-то сожму и потому смогу восстановить

типа главное чтобы инфа нужная для восстановления занимала меньше 2мб

збс ава

люблю рыжих

но они суки

 

тему не читал офк

осуждаю автора

 

Нихуя не так, Эмма Стоун <3

Единственное, что пришло на ум - отсортировать числа по возрастанию и хранить:

а - первое число

б - x, такой что a+x=второе число

в - y. такой что a+x+y=z и так далее

и отдельно хранить таблицу порядкового номера для каждого полученного числа.

На крайних случаях нада удостоверится что будет работать.

ты удивишься какой объем памяти займет таблица с порядковыми номерами чисел от 1 до 1000000

http://habrahabr.ru/post/65503/

оно?

массив перемешивать можно или как?

числа рандомные и могут повторяться?

как происходит проверка того, что число не потерялось?

в итоге нужно будет развернуть массив обратно в 4 мб или пох?

upd: по ссылке не то

У меня 42 получилось.Сам программист.

читерство

Ludwig Van Beethoven - Ninth Symphony, Second Movement

ответ

http://habrahabr.ru/post/65503/

 

оно?

 

массив перемешивать можно или как?

числа рандомные и могут повторяться?

 

как происходит проверка того, что число не потерялось?

в итоге нужно будет развернуть массив обратно в 4 мб или пох?

 

upd: по ссылке не то

я хуй знает это была первая пара и я пришел на последние минуты 2 потому что лень вставать было

помню точно, что он сказал, что числа повторяться могут и в самом худшем случае может быть чуть больше 2 мб

когда ты выбрал программирование ты с тем же успехом мог бы порезать себе в ванной вены,ну или на люстре там взвеситься это же ёбанный пиздец попробовать узнать что-то на пд,нахуя же тебе оно надо если ты не бум-бум?

если ты считаешь, что все дотеры такие же тупые как ты, у меня плохие новости

збс ава

люблю рыжих

но они суки

 

тему не читал офк

осуждаю автора

 

Нихуя не так, Эмма Стоун <3

да

вопщем посоны найдено решение без сохранения порядка элементов

спасибо юзеру ckyka за подсказку с алгоритмом

добавив немного рекурсии в тот алгоритм оказалось, что можно сжать все до 156 килобайт

без сохранения порядка? ХАХАХ

блять, это не решение тогда.

точнее решение, но не этой задачи.

ответ в студию, и ищи другой.

тебя препод нахуй пошлет, без сохранения порядка, вот увидишь.

по идее с сохранением порядка это невозможно сделать

насчет двух мегабайт хз, но сжимать можно.

скинь решение сюда, лол

сложно что ли догадаться?

ну кароче посортим массив и возьмем у каждого числа (в двоичной форме рассматривать будем) префикс из 16 цифр и сделаем массив из всевозможных префиксов длины 16 где будем хранить количество чисел с данным префиксом. Максимально 1кк может быть, значит массив будет по 20 бит то есть 65536 * 20

далее в исходном массиве уберем у каждого числа первые 16 цифр ну и оставим последние 16, таким образом будет массив из 1кк элементов по 16 бит

ну и получается 65 536 * 20 + 1 000 000 * 16 ну и это чуть больше двух мб

но для массива постфиксов можно проделать такую же хуйню, и так далее можно мутить и в итоге получится что-то около 160 кб

итого ты получаешь сжатие до 4%

это странно пахнет