ponder this

[avva]

(это тоже для программистов)

IBM продолжают публиковать нелегкую задачку для программистов (в широком смысле слова) каждый месяц. Задача за февраль, кажется, легче, чем обычно, ненамного выше по уровню, чем серьезное техническое интервью. Я решил ее на выходных, написав код на Питоне, где-то за два часа. Основная идея там - разобраться в том, как упростить происходящее, и потом как ловко оптимизировать вычисление, чтобы не на миллион лет.

Задача за март выглядит посложнее, забавная, с матрицами. Думаю и набросал кое-какой код, но пока не решил.

Comments

[dmitrmax.livejournal.com]

Ну очевидно, что этот многочлен от s образует... ох, забыл уже, группу или кольцо (?) по модулю 7. То есть вычислять его можно практически табличным методом и в s сохранять только его значение по модулю 7. Точнее двумя таблицами - для b = 0, и для b = 1.

Соответственно r = 0 в том случае, когда количество s % 7 = 1 равно количеству s % 1 = 0.

А дальше нужно найти все переходы от таблицы для b = 0, к таблице для b = 1 и наоборот, чтобы это равенство выполнялось, что скорее всего может быть посчитано чуть ли не аналитически. Нет?

Upd. Переходы внутри таблицы тоже надо учитывать (это ситуация когда следующий бит равен текущему). Надо ещё немного подумать ) Но думаю, что основная часть решения приведена )

А бонус вы решили? Там поди какой-нибудь год основания IBM )

[avva.livejournal.com]

Основная часть того, что вы сказали, верна, насчет по модулю 7 и того, что функция, по сути, простая таблица от данных s,b. Но как вы заметили, значение r меняется тоже в зависимости от b, и в конечном итоге нужно как-то посчитать кол-во всех 42-битных последовательностей, в которых порядок b дает ненулевое r. Сомневаюсь, что это возможно аналитически, по крайней мере я не вижу как.

Бонус я решил в смысле числа, это легко, но немедленной связи с IBM не увидел и мне лень было копаться в этом. Так что мое имя там без звездочки :)

[dmitrmax.livejournal.com]

Ну в таком случае нужно применить метод динамического программирования. Прогнать для строки в 2-бита, получить все возможные пары (r,s) на конец прогона. Затем добавить 1 бит и выполнить все переходы из пар для 2-х бит в пары для 3-х бит. Пройдя половину пути можно выбрасывать пары, в которых r на столько большой, что уже точно не вернётся к нулю. Как-то так. Писать, если честно, лень )

[avva.livejournal.com]

Вообще-то найти надо как раз кол-во таких, где r не возвращается к нулю, а не где возвращается. А это может случится хоть в самом конце. Так что удачного прогона по O(2^42) кандидатам :)

[dmitrmax.livejournal.com]

Да, криво прочитал условие. Но (2^42 - Z), где Z - кол-во нулевых вариантов, спасёт отца русской демократии )

Ещё можно хранить вместо множества пар (r;s) ассоциативный массив (r;s)->k, где k - кол-во последовательностей, которые прогоняются до этого состояния. И тогда в конце можно получить количество вариантов для любого r.

[epimorphisms_split (from livejournal.com)]

B. Note that to bet the bonus '*' you need to solve *a similar* problem...

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

[avva.livejournal.com]

Если вы знаете, о чем речь и какой ответ, расскажите - мне это просто недостаточно интересно, чтобы гадать и разыскивать.

[epimorphisms_split (from livejournal.com)]

Нет, не знаю. Подождем официального решения.

[(Anonymous)]

We would like to make as many watches as possible point to on of the four marks.

on это должно быть one? Или у меня с английским проблемы?

[avva.livejournal.com]

one, да, описка у них.

[xxxxx.livejournal.com]

Вот тебе задача по обществоведению, но на ту же тему. Математики играют в такую игру: они выкладывают на стол 12 векторов из пространства (Z/3Z)^4 и начинают в них тупить. Как только один из них увидит аффинное одномерное подпространство, он забирает его себе и получает очко (а если оказывается, что он ошибся, то вместо очка он получает в морду). На место убывших векторов подсыпают из кучи неиспользованных векторов, и так продолжается, пока все векторы пространства не кончатся. Внимание вопрос: как называют математики эту игру?

[spamsink.livejournal.com]

Продавцы этой игры называют ее Set, а как ее называют математики?

[xxxxx.livejournal.com]

ну это ж задача по обществоведению, секретное знание тут заключается в том, что математики тоже люди

[utnapishti.livejournal.com]

Говорят, есть люди, которые все мат. абстракции "видят".
6-мерные кубы там.
Интересно, есть ли кто-нибудь, кто, играя в эту-игру, действительно переводит всё в {0,1,2}^4, воображает геометрически, и визуально находит подпространства.

И вот тебе другое задание: опиши так судоку.

[migmit (from livejournal.com)]

Два игрока по очереди ломают друг другу ноги. Проигрывает тот, кто не может ходить.

[beldmit.livejournal.com]

Кстати. Какое максимальное количество векторов может быть на столе, чтобы подпространства таки не образовывалось?

[(Anonymous)]

3XXX6523XX264, простой динамикой

[avva.livejournal.com]

Ага, верно!

Adult purlieus

[(Anonymous)]

Started unusual snare throw
http://new.pics.hotblog.top/?entry.natalie
free paraplegic porn tiny teen porn pix sexy classy porn ayashi no ceres porn daphne flor porn star