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

  astrobomb написал 11.02.2013 в 22:26:

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

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

  NaxrenApm написал 11.02.2013 в 22:45:

  astrobomb написал 11.02.2013 в 22:26:

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

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

лошара

ОТВЕТ 42

  Charizma написал 11.02.2013 в 22:54:

ОТВЕТ 42

  ShadeOfLance написал 11.02.2013 в 21:11:

  Kant написал 11.02.2013 в 20:35:

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

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

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

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

  JOHNEE написал 11.02.2013 в 21:41:

  nooooob написал 11.02.2013 в 19:52:

збс ава

люблю рыжих

но они суки

 

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

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

 

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

  NaxrenApm написал 11.02.2013 в 22:15:

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

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

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

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

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

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

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

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

оно?

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

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

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

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

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

  Элитный Бобёр написал 11.02.2013 в 22:13:

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

читерство

Ludwig Van Beethoven - Ninth Symphony, Second Movement

ответ

  Greaver написал 12.02.2013 в 12:28:

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

 

оно?

 

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

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

 

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

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

 

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

Показать больше  

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

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

  givemefragplease написал 11.02.2013 в 21:22:

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

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

  JOHNEE написал 11.02.2013 в 21:41:

  nooooob написал 11.02.2013 в 19:52:

збс ава

люблю рыжих

но они суки

 

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

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

 

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

да

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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