the_grue: (Default)
Прощай, Таиланд! Привет, широкополосный интернет! :)

the_grue: (Default)
Вышел второй Humble Bundle для Андроида.

Humble Bundle - это сайт, который регулярно релизит компиляции из нескольких игр инди-разработчиков. Пользователи сайта сами выбирают, сколько заплатить разработчикам (минимум 1 цент) и как разделить между ними эти деньги.
the_grue: (Default)
Варкалось. Шорьки хрюкотали,
Пырялись зелюки в мове.
А молодого Бармаглота
Барабардали по наве.

Граахнул гром, и под Тумтумом,
В глуши, ужасный исполин.
Огнем стрижает очень взычно --
О, бойся Брандашмыга, сын!

***
Дум полон мюмзик светозарный:
В глущобе пылкает и ждет.
Но в рымку хливкую ужасно
Граахнул милый Бармаглот.

для тех, кто в танке )

(Совместное творчество с [livejournal.com profile] jinn)

The Horror

Mar. 13th, 2012 05:11 pm
the_grue: (Default)
Что-то у меня многовато о рашке в последнее время, но есть вещи, мимо которых нельзя пройти.

Вот и теперь - история такая, что нарочно не придумаешь. Сюжет фильма "Ворошиловский стрелок" воплотился в жизнь. Только если в фильме физические страдания девушки закончилось групповым изнасилованием, в жизни за ним последовало придушение удавкой и сожжение заживо.

Фильм, кстати, посвящен "проклятым 90-м" - тем самым, которые "остались" у нонешней стабильной рашки "позади".

the_grue: (Default)
Статья на Ленте.ру:
Житель Казани попал в реанимацию после изнасилования в полиции.
<...>
Родные убеждены, что в отделе полиции мужчину избили и изнасиловали бутылкой из-под шампанского.
<...>
"Даже если факт избиения подтвердится, ответственные за произошедшее будут наказаны", - пообещал полицейский.

Как вы думаете, что на самом деле хотел сказать "полицейский"?
(source)
the_grue: (Default)
Случайно наткнулся на эту запись 93-го года с Иосифом Бродским, где он высказывает свое мнение о русском/советском менталитете. Бродского выслали из Союза в 72-м, но его слова о той России, которую он знал, в равной степени хорошо описывают и реальность 90-х.

Вот и еще 20 лет накапало с 93-го года, и снова я слышу смешные разговоры о том, что там теперь все по-новому. Но смотрю я эту запись и понимаю, что там
Никогда. Ничего. Не изменится.

the_grue: (Default)
Некоторые бывшие соотечественники искренне удивляются и строят разной степени конспиративности теории о том, почему эмигранты называют их страну (и все снг заодно) сраной рашкой или совком. Популярная версия, например, такая: "вот мы уехали, и теперь все в шоколаде, а быдло вроде вас оставили в говне (где вам и место)!" Так вот, я созрел на это ответить, но сначала для наглядности свежий пример.

Как такое количество подонков уместилось в один день одного человека? Это, конечно, частный случай, но я видел N таких случаев. Много, постоянно, везде. И мое субъективное мнение о сраной рашке таково: личностей вроде [livejournal.com profile] vartlokkur в рашке абсолютное меньшинство. А большинство - инертное, раболепное стадо. Подонки без ума и совести, но с поразительной лояльностью и безграничной терпимостью к царю. Отправь их в 33-й год, они и там приживутся как родные. Вот это скотсво я в рашке и запомнил. Из-за него уехал.

Еще одна распространенная утка - это что за 15 лет в рашке что-то изменилось. Этот аргумент меня особенно поражает. По-моему, это все равно, что назвать черное белым. Мое детство прошло в рашке 90-х. Я близко познакомился с теми отморозками, которые сейчас составляют костяк этого общества. В отличие от родителей, которые были просто нищими рабами, эти познали радости беспредела. Поэтому со знанием дела заявляю: если что-то изменилось, то в худшую сторону. Высокие цены на нефть могут маскировать это за достатком, но в душах осталась та же жесть.

Так почему мы говорим и пишем на языке сраной рашки? Почему думаем о ней? Помимо очевидных ответов, таких как, на минуточку, культура и менталитет, остается еще неосевший осадочек от той мерзости, от которой я сбежал, и переживание за меньшинство, которое осталось там. За тех, кто родился с хребтом и не сломался, не продался, не превратился в животное. Носителей моего менталитета, моей культуры и моего языка. И за них мне тоже больно. Поэтому я и дальше буду об этом думать. И говорить.
the_grue: (Default)
Раз никто не решил задачу о двух массивах, публикую ответ. Если хотите решить сами, не смотрите под катом :)
Read more... )

Открытый вопрос: как решить задачу не с двумя, а с n (для начала хотя бы с n=3) отсортированых массивов? (Это не та же самая задача, что с матрицей, т.к. здесь неизвестно взаимное расположение элементов в разных массивах.)
the_grue: (Default)
Раз такая пьянка, еще одна задача на k-поиск.

Даны два отсортированых одномерных массива (необязательно одинаковой длины) с произвольными числами. Найти k-е по величине число среди всех чисел этих двух массивов. Если выглядит слишком просто, то спросите себя, нельзя ли решить быстрее :)

+ за элегантность (у меня пока вышло грязновато)

UPD: требуемое время для массивов общей длиной n: O(log n).
the_grue: (Default)
Условия: дана матрица (для простоты скажем, что она квадратная) n*n с произвольными числами (необязательно целыми). Все строки отсортированы слева направо, а столбцы - сверху вниз. Требуется дать алгоритм по нахождению k-го (0<=k<n^2) по величине элемента матрицы.

Эта задача уже когда-то всплывала, но давно и не у меня (в оригинале взята с интервью). Не знаю, чего ожидали на интервью, но у этой задачи есть весьма нетривиальное, магическое решение - сложностью O(n). Для сравнения, лучшее простое решение, которое мне известно, требует O(k*log(n)) времени, т.е. O(n^2 * log(n)) для k порядка n^2. Я тогда долго над ним медитировал, но интуитивно так и не понял (может быть потому, что там рассматривалась более сложная задача, втч матрицы могли иметь "пустые" ячейки). А пару дней назад прошелся по нему снова и - наконец - понял, что центральная идея - это просто рекурсивное разбиение массива. И вот стало мне интересно: сможет ли кто-нибудь из моих френдов найти то самое магическое решение своими силами (а не через гугл, хехе) с этими подсказками:
1. вам пригодятся подматрицы из предыдущего поста
2. алгоритм поиска k-го элемента в одномерном массиве за линейное время



В качестве мотивации для такой задачи, пример ее применения: даны отсортированные массивы чисел A и B, |A|=|B|=n. Найти k-й по величине элемент массива ci,j, определенного так: ci,j := bj - ai.

Чтобы свести задачу (2) к описанной задаче (1), вместо массива "c" будем работать с массивом di,j := bj - an-i-1. В этом массиве все строки и столбцы отсортированы, что и требуется условиями задачи (1).

Например:
A=1,2,3,4   B=-3,2,6,8

A\B|  -3  2  6  8
-----------------
4  |  -7 -2  2  4
3  |  -6 -1  3  5
2  |  -5  0  4  6
1  |  -4  1  5  7


Следовательно, если мы можем решить задачу нахождения k-го элемента произвольной матрицы за время O(n), то можем решить и эту за время O(n). Самая прекрасная деталь здесь состоит в том, что для решения задачи (2) не надо даже строить промежуточный массив из n^2 элементов: вместо этого мы можем работать с такой имплементацией класса Matrix, которая просто эмулирует массив, а на самом деле ее at(i,j) возвращает b(j)-a(n-i-1), size() возвращает (n,n), итд. В итоге мы можем решить задачу (2) целиком за линейное время!

Если кому-то это интересно (и если никто меня не опередит), напишу потом развернутое оптимальное решение этой задачи.
the_grue: (Default)
Легкая, конечно, но не настолько, как кажется на первый взгляд. Приведите реализацию следующего интерфейса (здесь код на Scala, но ответы принимаются на любом языке):
trait Matrix[T] {
  // returns the element at i,j
  def at(i:Int, j:Int): T

  // returns the number of rows and columns in this matrix
  def size(): (Int,Int)

  // returns a new matrix, whose (i,j)'th element is the (d*i+r, d*j+c)'th
  // element of this matrix (d>=1, r,c>=0)
  def divide(d:Int, r:Int, c:Int): Matrix[T]
}

object Matrix {
  def make[T](arr: Array[Array[T]]) = ???
}


На всякий случай объясню словами: надо написать враппер для двухмерного массива, который
1) умел бы выполнять все обычные операции над массивом, кроме модификации ячеек. Известно, что массив, над которым конструируется враппер, никогда не изменится (immutable).
2) умел бы возвращать подматрицу, содержащую строки исходной матрицы с индексами вида d*i+r и её столбцы с индексами вида d*j+c. Визуально это можно представить так: мы разбиваем нашу матрицу на квадраты размером d*d ячеек (смещенные на r строк вниз и c столбцов вправо) и возвращаем новую матрицу, содержащую только верхний левый элемент каждого из квадратов.

Требования к сложности времени выполнения: O(1) для всех операций над всеми объектами типа Matrix.

Ответ: dHJhaXQgTWF0cml4W1RdIHsKICAvLyByZXR1cm5zIHRoZSBlbGVtZW50IGF0IGksagogIGRlZiBhdChpOkludCwgajpJbnQpOiBUCgogIC8vIHJldHVybnMgdGhlIG51bWJlciBvZiByb3dzIGFuZCBjb2x1bW5zIGluIHRoaXMgbWF0cml4CiAgZGVmIHNpemUoKTogKEludCxJbnQpCgogIC8vIHJldHVybnMgYSBuZXcgbWF0cml4LCB3aG9zZSAoaSxqKSd0aCBlbGVtZW50IGlzIHRoZSAoZCppK3IsIGQqaitjKSd0aCBlbGVtZW50IG9mCiAgLy8gdGhpcyBtYXRyaXggKGQ+PTEsIHIsYz49MCkKICBkZWYgZGl2aWRlKGQ6SW50LCByOkludCwgYzpJbnQpOiBNYXRyaXhbVF0KfQoKb2JqZWN0IE1hdHJpeCB7CiAgZGVmIG1ha2VbVF0oYXJyOiBBcnJheVtBcnJheVtUXV0pID0gTWF0cml4SShhcnIsIDEsIDAsIDApCn0KCgoKY2FzZSBjbGFzcyBNYXRyaXhJW1RdKG06QXJyYXlbQXJyYXlbVF1dLCBkaXZpc29yOkludCwgb2Zmc2V0cjpJbnQsIG9mZnNldGM6SW50KSBleHRlbmRzIE1hdHJpeFtUXSB7CiAgZGVmIGF0KGk6SW50LCBqOkludCkgPSBtKGkqZGl2aXNvcitvZmZzZXRyKShqKmRpdmlzb3Irb2Zmc2V0YykKICBkZWYgYXBwbHkoaTpJbnQsIGo6SW50KSA9IGF0KGksaikKICBkZWYgc2l6ZSgpID0gKHN6KG0sIG9mZnNldHIpLCAgc3oobSgwKSwgb2Zmc2V0YykpCiAgZGVmIGRpdmlkZShkOkludCwgb2ZmcjpJbnQsIG9mZmM6SW50KSA9IE1hdHJpeEkobSwgZGl2aXNvcipkLAoJCQkJCQkJCQkJCQkgIGRpdmlzb3Iqb2ZmciArIG9mZnNldHIsCgkJCQkJCQkJCQkJCSAgZGl2aXNvcipvZmZjICsgb2Zmc2V0YykKICBwcml2YXRlIGRlZiBzeltWXShtOkFycmF5W1ZdLCBvZmZzZXQ6SW50KSA9IChtLmxlbmd0aC1vZmZzZXQrZGl2aXNvci0xKS9kaXZpc29yCn0KCgp2YWwgYSA9IE1hdHJpeC5tYWtlKEFycmF5LmZyb21GdW5jdGlvbigoaTpJbnQsajpJbnQpID0+ICIiICsgaSArICIsIiArIGopICgxMDAsMTAwKSkK
the_grue: (Default)
Это гениально. Сериал "Жуков" в поэтическом изложении: и зритель сразу понимает, что в Этой Долбаной Стране...
the_grue: (Default)
Еще из жизни улиток. Финал, конечно, на 100% прогнозируем, но техника хороша.
the_grue: (Default)
Что-то везет мне в последние дни на находки. Вот еще один поразительный мультик, наложенный на песню Tool:

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

С трудом удалось найти полный оригинал, но, честно говоря, с Тулом он лучше вставляет :) Это французский мультфильм 1965-го года под названием "Улитки".
the_grue: (Default)
Если кто еще не видел это чудо - обязательно смотрите! Я так впечатлился вчера, что меня хватило аж на два раза подряд. :)

(В фильме есть субтитры на английском - жмите CC.)

Кстати, у автора фильма очень интересный взгляд на копирайт. Если вкратце, она считает, что культура и искусство не являются собственностью и не могут никому принадлежать. Поэтому фильм сделала бесплатным и свободным для распространения. Только вот оказалось, что записи в саундтреке (которым уже 80 лет) до сих пор закопирайчены, так что уже после создания фильма автору пришлось выложить $50k в штатах, и еще минимум столько же придется в Германии. Но она выложила и оставила фильм бесплатно-свободным.

Если вам понравилось, не пожалейте $10 автору (линк для пожертвований есть на странице ютюба).
the_grue: (Default)
Случайно придумалось красивое "программистское" решение для суммы геометрической прогрессии вида an = 1 / kn. Для k=3:

sum{n=1,inf} (an) = 1/3 + 1/32 + ... = (0.111...)3 = (0.222...)3 / 2 = 1/2

Отсюда уже легко обобщить для всех k.
the_grue: (Default)
Those who don't understand Haskell are condemned to reinvent it, poorly?

The author (none other than Bjarne Stroustroup) claims that С++ concepts are somehow different from Haskell typeclasses, but, unless there was a dramatic change since 2008, they are not.

the_grue: (Default)
Это ужасно. Эта мерзость сейчас висит в топе. Сам пост малоинтересен, но комменты!!!!11

tl;dr
1. любовь
2. гангстеры
3. изнасилование
4. ???
5. PROFIT!

UPD: посмотрел пристальнее, и стало ясно, что это в комментах виртуалы резвятся. И не так уж их много - 70 штучек всего. Вот тут, например, они все есть в списке френдов: http://marsel-l.livejournal.com/profile
Все созданы в середине января, но ухоженные, с наполнением, юзерпиками и проч. Сильно кто-то постарался ради этого поста. Кажется, о нановекторной психологии мы еще услышим ;)
the_grue: (Default)
Прочел на Ленте.ру интересную деталь из нашумевшей истории про саудовского журналиста, которому грозит смертная казнь за богохульство в Твиттере. До сих пор не упоминалось, что именно написал богохульник, и вот наконец это возмутительное святотатство стало доступно и для нашего порицания.
В твите, за который арестовали Кашгари, он написал, обращаясь к пророку Мухаммеду: "Что-то в тебе я любил, что-то - ненавидел, и многое в тебе я не понимаю. Я не буду молиться тебе".

http://lenta.ru/news/2012/02/13/tweet/
the_grue: (Default)
Тот редкий случай, когда нельзя не перепостить (действующие лица - шишки юных путиноидов):
Кристина Потупчик – Василию Якеменко (12 сентября 2011 г.)
стартовые 150 тысяч просмотров мы дали этому ролику, поставив его в топ ютуба. а остальные сотни тысяч накрутил тесей. Но мы никогда такими раскрутками не пользовались, т. к. это спам раскрутка через вконтакте. ролик крутили по запросу "печеньки", т е люди хотели увидеть не путина, а печеньки. а "печеньки" в интернете-это женские половые органы.их так в интернете называют. я считаю, что ролик про путина мы не можем крутить таким способом.главный минус этой спам раскрутки-60 процентов аудитории не досматрело ролик до конца. просто кликнули, не увидели печенек и свалили.

Казалось бы, какое отношение печеньки могут иметь к службе Отечеству? А вот.
Page generated Jul. 22nd, 2017 10:40 pm
Powered by Dreamwidth Studios