blinnov’s blog

You have found an ancient carpet in your attic. It was originally black, but during it’s long life it obtained some white stains. Since it is so old we can’t remember maybe it was a white carpet, and the stains are black! You can not tell if it was white or black! Luckily you have found a bottle of Universal Spot Remover. A single drop of this magic liquid can change the color of any white spot to black, no matter how big the spot is. Amazingly, the same drop, if applied to a black spot, would change the color to white! You would like to remove all spots from the carpet. Since you do not know if it was initially black or white, you would be happy to have a carpet that is either completely black OR completely white. Just don’t waste the remover!
Your Task:
Write a program that finds the minimum number of drops needed to remove all stains from the carpet. Assume that the carpet is a MxN rectangle divided into M*N regular checks, some of which are black, some white. The stain is a group of checks of the same color connected side-by-side. For example, if the carpet were 8×8 (with alternating colors, like a chessboard), there would be exactly 32 white and 32 black stains. Note that when you remove a stain, it will merge with other neighboring stains.

Via RSDN

Upd: Answer can easily be found using Graph theory (look for something about finding the longest route in a graph or similar). Or, I just used a hint (chessboard) from the task, considering which it is easy to see that 3 drops would be enough for a carpet of 8×8 stains. The rest is trivial.

Вот уже пятый день, как ломаю WordPress.

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

• Многоязычный плагин gengo. Вроде работает, но не полностью совместим с WordPress 2.3.1 (пока?) – пришлось оторвать пару аппендиксов и нанести несколько серьезных ударов в печень. Кроме всего прочего, темплейты страниц должны быть творчески перекроены, чтобы ссылки на RSS и trackback URL не портились (gengo добавляет код языка пользователя в конец каждой ссылки по умолчанию, что для RSS и trackback недопустимо.
• OpenID плагин. Поддерживает только клиента (т.е. WordPress не становится OpenID провайдером сам). Кроме того, из коробки не работает, но, в отличие от gengo, не требует серьезного хирургического вмешательства. Чтобы дать возможность логиниться через OpenID, нужно модифицировать формы, если используется тема, отличная от default. Главное неудобство – пользователям других блогов может быть непонятно, как именно надо логиниться.
• LiveJournal comments.Удивительно, но работает сразу. Единственное “но” – не умеет отображать число коментов в LJ-копии поста, а очень хочется.
• Brian’s Threaded Comments. Наследие LJ – хочу видеть дерево комментариев. Плагин работает, вот только несовместим ни с чем. Скрестить с темой K2 мне пока полностью не удалось (да и не уверен, что буду дальше пытаться).
• Темы… выбор огромный, выбрать нечего. Буду ставить тему K2, но сначала надо нормально привинтить к ней OpenID контролы и решить, что буду делать с threaded comments.
• Пока не пробовал привинчивать аватары из ЖЖ.

В общем, провел достаточно времени, занимаясь PHP хакингом.

Пойду, отдохну немного на C++.