?

Log in

ponder this - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

ponder this [фев. 28, 2017|06:54 pm]
Anatoly Vorobey
[Tags|]

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

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

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

Comments:
[User Picture]From: dmitrmax
2017-02-28 06:21 pm
Ну очевидно, что этот многочлен от s образует... ох, забыл уже, группу или кольцо (?) по модулю 7. То есть вычислять его можно практически табличным методом и в s сохранять только его значение по модулю 7. Точнее двумя таблицами - для b = 0, и для b = 1.

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

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

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

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

Edited at 2017-02-28 18:32 (UTC)
(Ответить) (Thread)
[User Picture]From: avva
2017-02-28 09:44 pm
Основная часть того, что вы сказали, верна, насчет по модулю 7 и того, что функция, по сути, простая таблица от данных s,b. Но как вы заметили, значение r меняется тоже в зависимости от b, и в конечном итоге нужно как-то посчитать кол-во всех 42-битных последовательностей, в которых порядок b дает ненулевое r. Сомневаюсь, что это возможно аналитически, по крайней мере я не вижу как.

Бонус я решил в смысле числа, это легко, но немедленной связи с IBM не увидел и мне лень было копаться в этом. Так что мое имя там без звездочки :)
(Ответить) (Parent) (Thread)
[User Picture]From: dmitrmax
2017-02-28 10:07 pm
Ну в таком случае нужно применить метод динамического программирования. Прогнать для строки в 2-бита, получить все возможные пары (r,s) на конец прогона. Затем добавить 1 бит и выполнить все переходы из пар для 2-х бит в пары для 3-х бит. Пройдя половину пути можно выбрасывать пары, в которых r на столько большой, что уже точно не вернётся к нулю. Как-то так. Писать, если честно, лень )
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2017-02-28 10:21 pm
Вообще-то найти надо как раз кол-во таких, где r не возвращается к нулю, а не где возвращается. А это может случится хоть в самом конце. Так что удачного прогона по O(2^42) кандидатам :)
(Ответить) (Parent) (Thread)
[User Picture]From: dmitrmax
2017-03-01 12:46 am
Да, криво прочитал условие. Но (2^42 - Z), где Z - кол-во нулевых вариантов, спасёт отца русской демократии )

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

Edited at 2017-03-01 00:47 (UTC)
(Ответить) (Parent) (Thread)
From: epimorphisms-split.dreamwidth.org
2017-03-01 09:05 am
B. Note that to bet the bonus '*' you need to solve *a similar* problem...

перевожу: вы должны догадаться, какую похожую задачу надо решить, и решить ее.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2017-03-01 10:44 am
Если вы знаете, о чем речь и какой ответ, расскажите - мне это просто недостаточно интересно, чтобы гадать и разыскивать.
(Ответить) (Parent) (Thread)
From: epimorphisms-split.dreamwidth.org
2017-03-02 01:33 pm
Нет, не знаю. Подождем официального решения.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2017-02-28 06:46 pm
We would like to make as many watches as possible point to on of the four marks.

on это должно быть one? Или у меня с английским проблемы?
(Ответить) (Thread)
[User Picture]From: avva
2017-02-28 07:07 pm
one, да, описка у них.
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2017-02-28 07:48 pm
Вот тебе задача по обществоведению, но на ту же тему. Математики играют в такую игру: они выкладывают на стол 12 векторов из пространства (Z/3Z)^4 и начинают в них тупить. Как только один из них увидит аффинное одномерное подпространство, он забирает его себе и получает очко (а если оказывается, что он ошибся, то вместо очка он получает в морду). На место убывших векторов подсыпают из кучи неиспользованных векторов, и так продолжается, пока все векторы пространства не кончатся. Внимание вопрос: как называют математики эту игру?
(Ответить) (Thread)
[User Picture]From: spamsink
2017-02-28 08:01 pm
Продавцы этой игры называют ее Set, а как ее называют математики?
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2017-02-28 08:02 pm
ну это ж задача по обществоведению, секретное знание тут заключается в том, что математики тоже люди
(Ответить) (Parent) (Thread)
[User Picture]From: utnapishti
2017-03-02 01:51 am
Говорят, есть люди, которые все мат. абстракции "видят".
6-мерные кубы там.
Интересно, есть ли кто-нибудь, кто, играя в эту-игру, действительно переводит всё в {0,1,2}^4, воображает геометрически, и визуально находит подпространства.

И вот тебе другое задание: опиши так судоку.
(Ответить) (Parent) (Thread)
[User Picture]From: migmit.dreamwidth.org
2017-03-02 10:14 am
Два игрока по очереди ломают друг другу ноги. Проигрывает тот, кто не может ходить.
(Ответить) (Parent) (Thread)
[User Picture]From: beldmit
2017-03-03 05:52 am
Кстати. Какое максимальное количество векторов может быть на столе, чтобы подпространства таки не образовывалось?
(Ответить) (Parent) (Thread)
From: (Anonymous)
2017-03-01 08:01 am
3XXX6523XX264, простой динамикой
(Ответить) (Thread)
[User Picture]From: avva
2017-03-01 08:41 am
Ага, верно!
(Ответить) (Parent) (Thread)
From: (Anonymous)
2017-03-02 09:54 pm

Adult purlieus

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
(Ответить) (Thread)