Архив форума

Может будем рассказывать решения какого размера имеем на данный момент? Конечно это убьет интригу, зато повысит накал и улучшит результаты. ;)
На данный момент я имею 115716 байт ;) Сейчас (23:41 14.04.2004) я спать, а завтра попробую один модный алгоритм реализовать ;)

15.04.2004 0:45 97355
15.04.2004 1:05 95977

А я вот ее на Тимус сдал (http://acm.timus.ru/status.aspx?space=1&pos=565470).
text.txt у меня пакуется до 99917 байт.

Ай, молодца ;) Мое решение на контесте действительно немного до AC недотягивало. На Тимус не сдаю, т.к. с FreePascal'ем пока бороться не хочу ;)

Архив на каком языке генерируется? ;)

Кстати результат улучшил до 95918. Похоже выжал все что мог. Надо новый путь искать.

92110 :)))
Только вот я уже не знаю куда больше оптимиздить... :(

Кстати! Кто-нибудь решает архиватор на С++?
ПодЕлитесь впечатлениями?

2:06 95887

Прорыв!!!!
2:36 81524

Чем ответит Паша? :lol:

PS Во многом прорыв благодаря Паше, который научил меня обходить одну фенечку Delphi ;)

Знал я, что доброта наказуема.... Да ничего с собой поделать не мог :))

так, какое еще 2:36??? линчевать тех, из-за кого Расковалов не выспался сегодня ночью :evil: :evil: :evil:

Ну что? Кто-нибудь еще кроме меня за 90000 вылез?
8)

в какую сторону? :lol: есть алгоритм, который до 55 жмет, только я его понять не успею, а брать чужой код не позволяет совесть и (возможно) условия конкурса.

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

щаз есть хаффман и 113 кб (до 108 пожалось + 3 кб из-за ограничения чарсета + 2 кб на декомпрессор). ден, у тебя по началу тоже оно было? заффтра (то есть уже сегодня) прикручу его поверх чего-нибудь со словарями.

один перец сотворил 66 кб. всем сдаваца :cry:

у меня в 82-85 уложится, если успею дописать до завтра.

И кто это, интересно? Что-то не верится в 66кб.Вот-вот, допиши сначала :)

А у меня сейчас 87553 байт.

Отослал волкову 83938

Только сейчас понял, что могу еще меньше. Работаю!!!
Ожидается что-то не сильно больше 80000

Прямо приятно поднять такую бучу :-)

Чтобы внести ясность:
Засчитывать буду только честные решение. Обязанность определять, какое решение честное, а какое нет, оставляю за собой.

Пример: взять RARовский SFX и упаковать его в программу - нечестно. сканировать мой винт чтобы найти там файл text.txt и перекопировать его куда следует - нечестно.

Аааа... Бойтесь люди. Написал я PPMII. Жмет до 49458. Сейчас собираю программу-архив. Нацелен на 75Kb ;(

нацелен на 60 кб, только уже сдавать пора, а мне еще писать пару часов :(

71580.
Скромно и со вкусом :)

Назову текущую группу лидеров, но, чтобы не убивать интригу, не буду называть их результаты. Решения буду принимать до 16.00.

Сразу оговорюсь: результаты предварительные - т.е. это просто размеры, я еще ничего не компилировал, не выполнял, не проверял на честность...

1. Крохалев
2. Егоров
3. Крашенниников
4. Копылов
5. Расковалов
остальные дальше...

Это промышленный терроризм!!! :)

Когда я работать то буду?!?!?!?

НЕ ЧЕСТНО! ТРЕБУЮ до 14.00.

Ведь в условиях было четко:
Решения принимаются по адресу электронной почты volkov@skbkontur.ru вплоть до 14.00 пятницы, 16 апреля 2004 года.

Поддерживаю...
Только ведь тут не демократия, а тоталитарный режим с ЛВ на вершине :)))

хм... а ведь формально противоречия нет :)
Решения принимались до 14:00? принимались... Так что все, типа, нормально :)

14.00 было вывешено без согласования со мной, я собирался принимать до 16.00

Ну и правда - нет противоречия :-)

Успевайте!
По состоянию на 15.00

1. Крохалев
2. Расковалов
3. Егоров
4. Густелев
5. Крашенинников

но ведь еще целый час впереди!

Последнее посланное мною решение было на C. Реализован был PPMII. Жал файл до 49 с копейками. Сам архив весил целых 69 килобайт ;( 10 килобайт кода распаковщика! C-шные инициализаторы строковых констант сильно хуже в этой задачке Delphi'ских ;(

Ну что - завтра награждение...
Сохраню интригу до победного. Призы будут вручаться начиная с 16.00 во время первого дня ДММ в конференц-зале на Тургенева.
За призами ожидаются (но порядок пока не разглашается!) Александр Крашенинников, Василий Густелев, Денис Расковалов, Евгений Крохалев, Павел Егоров.

Прикольно, я до последнего не знал что мне 3-е место все же дали... :-).
Ден, а ты зачем на С писал PPM2 ???

Любовь - штука иррациональная ;) Там код был сложный и его было много. В сумме паковщик/распаковщик под 40K. C сильно проиграл по длине строковых констант. Слишком много запрещенных символов. Но отступать мне было некуда. Да и решение Жени тоже было на C.

А после того, как я от Лени узнал, что Женя меня сделал на 300 байт, я честно из своего исходника "убрал" еще килобайт. Мог бы и больше. У Жени данных реально на 5Kb больше. Но Женя победил очень красиво! :lol: У него был единственный "человеческий" распаковщик. Жене респект! :D

Ну что? Рассказывайте, какое решение принял ЛВ! :)

Я не знаю выиграл ли что-нибудь мой Архиватор, но свои мысли "по теме" таки расскажу :)

Часть первая. "LZ"
Четверг. Вечер. Реализую две новые гениальные мысли по оптимизации банального LZ. На этот момент я уже знал, что в Дельфяцкой строке можно хранить все символы кроме двух:
#10 и #39 (апостроф). Кстати в IDE Delphi исходник без #13 символов крайне забавно выглядит :)) Но при этом работает!
Итак, алгоритм у меня стал с задатками оптимального кодирования выходной информации. Словарь - треть входного файла, пара (смещение, длина) кодируется либо 2 либо 3 байтами в зависимости от! Биты в байтах распределены таким образом, чтобы те самые #10 и #39 встречались как можно реже. Добиваюсь 83960 (если не ошибаюсь...) Пытаюсь прикрутить еще пару идей - выигрыша не дают...
Замученный сабмичу и иду спать :)

Пятница. Утро.
Понимаю, что 8 часов назад, определённо будучи не в себе, почему-то оставил неиспользованными 2 бита, при 3-байтовом кодировани :)) Срочно правлю, делаю какую-то тривиальную ошибку в декодере, кучу времени отлаживаю (ибо с размером словаря 2^17 байт отладка становится мучительно долгой :))
Когда, наконец, все заработало, получаю 83060 (или около того). Целых 2 лишних бита дали выигрыш всего в 1 Кб!!!!
Жуть. Даже сабмитить не стал.... Отчаился...

Часть вторая. "zlib"
Пятница. Утро. Работа.
На работе, как известно, настроение рабочее. На геройства и исследования не тянет. Как-то получается взглянуть на задачу и предложенные инструменты (C++ и Delphi) с другой (рабочей) cтороны.
Хм... хм-хм...
Не долго думая создаю новый проект в Дельфе, пишу:

uses 

  Classes, zlib;

:))
И действительно! Предлагаемый инструмент Delphi имеет достаточно продвинутое средство для решения предложенной задачи. Грех не воспользоваться!!! И главное формально все честно:
Запретить использовать модули - нельзя! Ибо С-шники без подключения заголовочных файлов вообще ничего сделать не смогут. zlib никакие сторонние библиотеки не использует - линкует obj-файлы. zlib поставляется с Delphi, как неотъемлемая его часть.
Формально, назвать такой способ читерством нет никаких возможностей %)
Однако, почему-то остается чувство вины перед остальными участниками... К чему бы это? ;))

Короче свой второй солюшен я написал минут за 40. Все, что надо было - это избавиться от #10 и #39 после zlib-ования, а в декодере вернуть их обратно перед де-zlib-ованием :))

В общем на сколько мне известно, мой первый LZ-солюшен занимал 5-ое место, а второй zlib-овый - 3-е.
Кто виноват? ЛВ конечно! %) Если надо проверить умение решать квадратное уравнение, не надо давать испытуемому калькулятор с кнопкой "решить квадратное уравнение" :))
Вот такую вот себе задачку подкинул ЛВ - решить что же делать с zlib-ом :)
А я вот сижу и мучаюсь, так и не зная, как же он этот казус обошёл... Может расскажете, а?
На самом деле я бы совершенно спокойно это принял, если бы мой zlib-овый солюшен дисквалифицировали. Но стал бы спорить! Спорить и спорить! Ибо я был прав, хоть и поступил нечестно :)) А поскольку поступил нечестно, то и не постил этот пост раньше награждения :)

А я пока отдельно поздравляю Дена Расковалова и Женю Крохалева! Они сделали промышленный zlib!!!
Легко и непринужденно :))

Правда к zlib требования немного другие... Быстрая упаковка, да всё такое прочее... но это неважно :)

Поздравляю! :))

PS. Эй! Кто еще не спит? Ну расскажите, кто какие места заполучил!!!
Я на ДММ прийти не смог - сейчас от любопытства мучаюсь...

> uses
Classes, zlib;

может, надо было отсабмитить решение, которое качает файл из интернета? :lol: если твое приняли, то и такое должны были :)

> Реализован был PPMII.

вечный двигатель второго рода? :)

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

свои впечателения: реализовал нечто, что после недавнего прочтения доков оказалось ppm-1, а вот арифметическое кодирование изобрести не смог :lol: в итоге оно пожалось хуже, чем без контекстов... руки опустились, ушел спать и проспал почти сутки.

Глупости! Никто не гарантировал наличие инета на проверочной машине.
Равно как и установленного RAR и наличия файла text.txt "где-то рядом" и тд. и тп.

А вот наличие модуля zlib, как составную часть Delphi, гарантировали, сказав, что принимаются решения на Delphi.

тебе ли не знать, что у меня сходу была идея подключить стандартную библиотеку для сжатия :) просто, панимаешь, наглости не хватило :) ну да фиг с ним :) зато как хорошо задача "архиватор" сдалась постле трехдневного траха с этим вашим порри гаттером :) меньше чем за час и с первого раза :) а на контесте на нее почти все пять часов убил...

ЛВ, запости плииииз у кого сколько байтиков, причем все 14 человек, ну ооочень интересно :-)

Еще маленький штрих к портрету. Мифический пункт про "честность" Лёня добавил после того, как я покаялся ему в ЧУday2, что мой лучший солюшен на тот момент - RAR'овский SFX, который выплевывается на винт и запускается.

А вообще, я считаю, давать на олимпиаду ДММ "промышленные задачи" не совсем правильно. Оценивается не способность придумать что-то свое в сжатые сроки, а найти инфу и грамотно ее "подхватить". Что поиск гамильтонового цикла, что архивирование - задачи важные, нужные и избитые. Правильно ли это?

Люди! Кончайте издеваться! Скажите мне уже, наконец результаты :))
Я уже 6 постов назад попросил :))

за читерство предлагаю одно из двух наказаний:

1) не сознаваться, зачли ему решение или нет
2) сказать, что он победил, но приз не дадут, потому что "после церемонии вручения призы не выдаются" (с) стена рядом с кафедрой алгебры.

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

лирическое отступление:
я реализовал три солюшна, первый сдал в пятницу в 13:30
это был "вродепочти" ppm в 1 файл размером в 100 000 байт.
следующий солюшн я сдал после того как наконец покушал - в 14:00 я дописал кое что интересное в свой архиватор, сжал исходный текст до 49 458 + распаковщик (посчитайте сами сколько) = 73853.
я согласен что это очень далеко до первого места.
тем не менее в пятом часу я с ужасом узнал что решения принимались до 16-00 и попытался сделать что то еще. но, увы время кончилось, и я работал уже ради спортивного интереса.
итог: 49 458 + оптимизированный распаковщик в 18 275 байт = 67 733 байт.
я попросил ЛВ хотя бы просто рассмотреть мое решение, понятно что засчитано оно не будет. ведь мне на самом деле не нужны ни деньги, ни даже стажировка в СКБ (хотя не отказался бы), но важно знать насколько я плохой программист. каковы мои шансы сидя в соседних отделах с тем же Деном Расковаловым сдать проект лучше его. и я хочу просто знать:
на сколько я отстал от первого и второго места???
какие результаты были у ребят, и, наконец, посмотреть, как они этого добились? сколько это на самом деле: "невообразимое число байт" ?

я думаю, ответить может не только ЛВ, верно?