A. Почти простые числа

Это задача на реализацию: для каждого числа от 1 до n разложим его на простые множители и посчитаем количество различных простых делителей.

B. Правильная скобочная подпоследовательность

Будем читать строку слева на права и поддерживать на каждом шаге баланс скобок (т.е. разность между количеством выписанных открывающих и закрывающих скобок). Этот баланс должен быть всегда неотрицательным. Поэтому если он равен нулю и мы читаем закрывающую скобку, ее нужно пропустить и не выписывать. Ответ будет равен удвоенному количеству выписанных закрывающих скобок.

C. Паркет

Докажем несколько необходимых условий для существования паркета. Если какое-то из них не выполнено, ответ "IMPOSSIBLE".
1. m*n должно быть четным, т.к. это общая площадь паркета, а площадь каждой плитки четна.
2. Допустим, что m (количество столбцов) нечетно. Раскрасим гостиную в черный и белый цвета следующим образом: первый столбец черный, второй белый, третий черный, ..., последний черный. Число черных квадратов будет на n больше, чем число белых. Плитки 1x2 и 2x2 содержат равное число черных и белых квадратов, поэтому разность нужно компенсировать с помощью плиток 2x1, и их число должно быть хотя бы n/2. В этом случае мы можем замостить последнюю колонку этими плитками, уменьшить b на n/2 и уменьшить m на единицу.
3. Если n нечетно, то аналогично получаем a ≥ m / 2.
4. Теперь  m и n четны. Похожие рассуждения показывают, что число использованных плиток 1x2 и 2x1 должно быть четным. Поэтому если a нечетно, уменьшим его на 1, и то же самое с b.
5. Теперь должно быть mn ≤ 2a + 2b + 4c, иначе не хватит общей площади плиток.
6. Если все условия были выполнены, мы можем завершить замощение: разделим гостиную на квадраты 2x2 и заполним каждый либо одной плиткой 2x2, либо двумя плитками 1x2, либо двумя плитками 2x1.

D. Билеты

Если мы изобразим график числа доступных 10-евровых банкнот, это будет ломаная линия с началом в точке (0, k) и концом в точке (m+n, n+k-m). Ровно m звеньев идут вниз, остальные n звеньев — вверх. Поэтому общее число возможных графиков равно C(m + n, m) (биномиальный коэффициент). Нам нужно найти число графиков, которые не заходят под ось X. Мы посчитаем "дополнительное" значение: число графиков, которые заходят под ось X, то есть пересекают прямую y=-1.

Для этого мы используем "принцип отражений". Рассмотрим любой график, который пересекает прямую y=-1, и возьмем последнюю из точек пересечения. Отразим часть графика, начиная с этой точки, относительно прямой y=-1. Получится новый график, оканчивающийся в точке (m + n,  - 2 - n - k + m). Обратно, любой график, оканчивающийся в этой точке, пересекает прямую  y=-1, и мы можем применить к нему ту же операцию. Итак, число графиков, которые нас интересуют, равно числу графиков, начинающихся в точке (0, k) и заканчивающихся в точке (m + n,  - 2 - n - k + m). Пусть a и b — число звеньев в таком графе, идущих вверх и вниз соответственно. Тогда a + b = m + n, a - b + k =  - 2 - n - k + m. Отсюда a = m - k - 1, и число таких графиков равно C(m + n, m - k - 1).

Таким образом, вероятность того, что график зайдет под ось X, равна C(m + n, m - k - 1) /  C(m + n, m) = (m!n!) / ((n + k + 1)!(m - k - 1)!) = (m(m - 1)... (m - k)) /  ((n + 1)(n + 2)... (n + k + 1)). Ответ к задаче: 1 -  (m(m - 1)... (m - k)) / ((n + 1)(n + 2)... (n + k + 1)).

E. Multithreading

Ясно, что w должно удовлетворять неравенствам 1 ≤ w ≤ Σ_i n_i. Если это так, покажем, как достигнуть такого результата в трех случаях:
1. N = 1, w = n₁. Очевидно.
2. N ≥ 2, w ≥ 2. Для w = 2 схема такая: 1, все циклы процессов 3..N, n₂ - 1 циклов второго процесса, 1, 2, n₁ - 1 циклов первого процесса, 2. Для w > 2 нужно переместить несколько циклов из середины последовательности в конец.
3. N  ≥ 2, w = 1, и существует i такое, что n_i = 1. Схема такая: i, все циклы остальных процессов, i.

Теперь покажем, что в остальных случаях результат w недостижим. Случай N = 1, w ≠ n₁ очевиден. Осталось разобрать ситуацию, когда N ≥ 2,  w = 1, и n_i > 1 для всех i. Допустим, что существует последовательность, для которой результат оказался равным y = 1. Рассмотрим последнюю операцию записи в этой последовательности, пусть ее провел процесс с номером i. Тогда соответствующая операция чтения должна была прочитать значение y=0. Это значит, что до нее не было произведено ни одной операции записи. Но это невозможно, т.к. n_i > 1, и i-й процесс к этому моменту произвел n_i - 1 циклов чтения/записи.

ВНЕЗАПНО вклад dAFTc0d3rа упал с over +20 до under -20, а brainail вырвался в топ лидеров.

A. Дана строка...

Переберём все подстроки, начиная с самых длинных, и для каждой посчитаем, сколько раз она встречается. Сложность — O(L⁴) с маленькой константой.

I'm sure we won't need this post after Codeforces comes out of beta, but meanwhile it could be useful :) Feel free to suggest what should be added here.

Competitions: general

Q. What are the rules of these contests?

A. Read this.

A. The judge machines are Core 2 Duo, 2.67 Ghz (E6750). The full list of supported languages and compiler options can be found in this post

Q. How do I hack other's solutions?
A. First lock your own solution in the main ('problems') tab. Then in your room double click or Ctrl+click the solution you want to hack. Check this post for complete rules concerning hacking.

Q. How is rating calculated?
A. The rating system is described in these two posts. Note that even for a joined contest the rating updates are calculated separately for the first and the second divisions. Therefore, a situation is possible, when a div2-coder performed worse than a div1-coder in the same contest, but gained more rating points.

Competitions: writing code

Q. How do I read/write 64bit integers in C/C++?
A. If you submit under "GNU C++" or "GNU C" option, use this:
   printf("%I64d\n",n);
but NOT this:
   printf("%lld\n",n);

If you submit under "MS C++" option, both variants should work.

And of course, with C++ you can always write
   std::cout << n << "\n";

Q. How can my program determine whether it runs in Codeforces server?
A. For most programming languages Codeforces environment defines the symbol ONLINE_JUDGE. Again, see this post for details.

Using the site

Q. How do I read other people's code?
A. After the contest is over, go to its page (for example, http://codeforces.com/contest/15 ) and click on this picture: . You will see a page with several submits (currently 100, I think). You can sort and filter the solutions there. To see the fastest solutions, you need to manually paste a URL like this: http://codeforces.com/contest/15/status/A?order=BY_ARRIVED_ASC
(currently there's no way to do this via UI)

A. Письмо

Чтобы найти наименьший прямоугольник, содержащий картинку, переберем все пары (i,j), для которых j-й символ в i-й строке равен '*', найдем минимальные и максимальные значения i и j среди этих пар. Искомый прямоугольник — [i_min, i_max] × [j_min, j_max].

Two parallels came into my mind:

1. Level of knowledge of a foreign language. Something like this:
Pre-intermediate -> Intermediate -> Upper-intermediate -> Advanced -> Fluent
There can be a 'preferred language' field in profiles, and then they will look this way:

Petr

• Contest rating: 2046
• Fluent in Java

2. Software release life cycle. It's pretty self-explanatory, I think:

Pre-alpha -> Alpha -> Beta -> Release Candidate -> Release
User's handle could look like this:
adamax^β

A. Бросок кубика

Пусть максимум из очков Якко и Вакко -- a. Тогда Дот выиграет, если выбросит не меньше a очков. Вероятность этого равна (6 - (a-1)) / 6. Поскольку a принимает всего 6 значений, ответы можно просто вычислить вручную.