Hello the community,

I want to invite you to take part in the Topcoder Open '17 Marathon competition.

The first round is about to start tomorrow, April 12 at 17:00 UTC, and will last for 2 weeks.

There is a short article from our long-time marathoner, wleite, who describes why you definitely should participate.

As one of the bloggers this year, I wrote some introductory articles you may also want to check:

Marathon Challenges: An Introduction

Approaching A Marathon Match Task, Pt. 1

Final Results Of Marathon Match 93

Note that this year the rules have changed quite a bit, I encourage you to read them if you plan to participate.

UPDATE: The contest is postponed to 21:00 EST today (25:00 UTC).

С огорчением обнаружил, что рейтинг сообщения в блоге или комментарии на Codeforces постепенно превращается во что-то вроде голосования. В стиле, если я не согласен с сообщением, ставлю "-", а если меня всё устраивает, то "+". Я считаю, что это не совсем верный подход, т. к. эти кнопочки на форумах исторически использовались для борьбы с неуместными (грубыми, непристойными, оскорбительными) высказываниями. Сейчас же на Codeforces, по крайней мере, можно получить негативный рейтинг вклада просто за то, что ты мыслишь не как большинство в сообществе, а за троллинг можно при определённых обстоятельствах уйти в высокий "плюс". Это наводит на неприятные мысли о стагнации сообщества. Скажу более -- если кто-то начнет идти против системы и отмечать "+" сообщения, которые, на его взгляд, необоснованно потоплены, он и сам рискует получить негативный бонус к своему "вкладу". В данной ситуации самый простой выход, конечно, игнорировать рейтинг вклада в силу его глубокой субъективности, но как же это сделать, когда он на самом виду?

I was in a process of analyzing market state in SW outsourcing field and unexpectedly got an article (http://www.yegor256.com/2015/10/27/outsourcing-doesnt-work.html) on why outsourcing does not work anymore. The main thesis in the article is that outsourcing business' needs contradict with their customer's targets. To be more concrete, outsourcing company wants to get as much money from their client as possible, while customer wants to maximize quality/cost ratio.

Доброго времени, дорогие Кодфорсчане!

Я хочу разрекламировать результат своей бакалаврской жизнедеятельности, программу MathLogic. Её можно бесплатно (в прошлом планируется взимание таксы) скачать с сайта, посвящённого мне: http://balancedtree.lv. Акция проходит в рамках осенней распродажи купонов на бесплатные программные обеспечения и сухари.

Прошу судить мягко и выражаться о программе здесь.

UPD: добавил ссылку на mercurial repository этой программы на сайт -- http://logic:[email protected]/scm/hg/logic.

Во время соревнования, что неудивительно, зная мои математические способности, не придумал идею для задачи D. Как уже было отмечено в других сообщениях, оптимальным в большинстве случаев будет ответ "солдаты не могут занять больше, чем пол площадки". Здесь чудесным образом всплывает раскраска плаца на квадратики "под шахматную доску". Я не буду рассматривать более "логичные" решения этой задачи, вроде паросочетания в двудольном графе; моя цель — доказать, прежде всего самому себе, что для больших досок нельзя изобрести ничего лучшего.

Заметим закономерность: каждый солдат (С) может "атаковать" (по аналогии с шахматами) до 8 клеток включительно:

-*-*-
*---*
--C--
*---*
-*-*-

Понятно, что, если он стоит на границе доски, то количество атакуемых клеток меньше.

Идея доказательства следующая: в данной расстановке, когда солдаты стоят в шахматном порядке, каждую пустую клетку, которая стоит как минимум на расстоянии 2 от края доски, атакует ровно 8 солдат. Допустим, наша расстановка не оптимальна, и какую-то пустую клетку можно атаковать аж 9-ю или более солдатами (таким образом, мы пытаемся увеличить общее количество солдат на доске). Здесь стоит остановиться и заметить, что 9-го солдата просто некуда поставить, в силу симметричности атакующих солдат и атакуемых пустых клеток (К):

-С-С-
С---С
--К--
С---С
-С-С-

Мы же не можем, не имеем права ставить двоих солдат в 1 клетку!

Так как нас интересуют только большие доски, а отношение краев доски к ее середине стремится к нулю в пределе при больших размерах досок, то можно считать, что все хорошо, мы решили, что заполнять центр доски можно и нужно в шахматном порядке. Что делать с краями — остается рамочка шириной в 2 клетки... Если нарисовать ту же шахматную расстановку для крайних клеток, то получится, что и здесь каждая пустая клетка атакована максимально возможным количеством солдат.

Это доказательство не совсем строго (даже совсем не строго). В частности, интересно, как доказать формально, что из того, что все пустые клетки атакованы по максимуму вытекает то, что больше солдат поставить нельзя. Также я не рассмотрел случаи с маленькими досками (размеры 1×x, 2×x), на которых, мягко говоря, все вышесказанное не действует.

P. S. кажется, вспомнил, где я мог видеть это доказательство... Это "Детская энциклопедия Математика". То-то я думал, что у меня дежавю с этой задачей :), а ведь открывал я эту книгу последний раз лет 6 назад.