пост-дыбр

30 ноября 2008 года

Мне только что совсем недавно диагностировали диабет - аккурат на следующий день после попытки въехать на Аманам (шериф остановил, тогда это было запрещено). Я б все равно не въехал, где меня шериф остановил, это была еще относительно легкая часть.

Работал я тогда в Гугле, ненавидел его, и искал куда свалить, мечтая, чтоб меня сократили (и денег дали при этом). Конец ноября, мы собираемся в милейший Орегон (в милейшую его часть, то есть, на океанское побережье).

А так-то жизнь была ничо. Велосипед, керамика. Я тогда брал курс керамики, wheel-throwing. Помогало от эмоций по поводу Гугла. Где окружали меня изумительно отменные идиоты. Кроме, конечно, чемпионов кубика Рубика, которые как раз собрались в этой "команде". Один мог правой рукой программировать, а левой, не глядя, крутить кубик. Другой был просто чемпион мира по кубику. Но это, конечно, не влияло на общий маразм.

Ну и старшая блядь этого борделя, Ками Хаксон... ох, тьфу. Совсем настроение себе испортил, вспоминая.

решение через полукольцо

(10x antilamer)
source

Итак, задача. Имеется список чисел, найти максимальную сумму подсписка отрезка данного списка. Известная задача на интервью; некоторые умудряются сделать её n³ - я не очень-то понимаю как, в принципе, задача линейная.

for ((current, maxfound) = (0, -infinity), i = 0; i < list.length; i++) {
  current = max(current + list[i], 0);
  maxfound = max(maxfound, current);
}

Но если условие усложннить, попросив распараллелить задачу (типа список очень большой), то непонятно, как бы это сделать-то.

И тут нам поможет полукольцо. ( шо це за параша, полукольцо )

Так вот, в нашей задаче мы имеем две операции, max и +. msx дистрибутивна относительно слодения: a + msx(b, c) = max(a + b, a + c). Так что мы можем представить целые числа с операциями max и + как полукольцо, обозначив + через *, а max через +.

Кроме того, 0, будучи нейтральным элементом относительно нового умножения, в нашем полукольце становится 1, а -infinity, соответственно, будучи нейтральным элементом относительно нового сложения, cтановится 0.

Перепишем содержимое цикла:

current = current * list[i] + 1;
maxfound = maxfound + current;

Это у нас получается линейное преобразование над тремя элементами, current, maxvalue и 1.

Точнее, берём вектор (current, maxfound, 1) и применяем к ней матрицу

list[i],  0  1
   1      1  0
   0      0  1

Начальное значение вектора (1, 0, 1); когда его умножить на все матрицы вышеуказанного вида, наш ответ окажется средним элементом этого вектора.

Но раз есть матрицы, их же можно а) перемножать попарно, так что требуется всего логарифмическое количество операций; б) распараллелить, нарезав вектор на кусочеки.

Вот и всё!

Мораль: учите алгебру, программисты.

дебильнейший вопрос

А вот фашисты постоянно носят какие-то нарукавные повязки со свастикой в белом круге. Как народные дружинники типа. Это что такое, кому было положено повязки носить? И когда? Вот идёт важный фашист в бой, а у него на рукаве тоже повязка, чтобы отличить дружинника? Или что это?

(Вообще, заебала уже эта вездесущая фашистская культура, честно говоря. Попадается на глаза, имхо, чаще картин советских художников-монументалистов.)