A. Almost Prime

This is a straightforward implementation problem: factor every number from 1 to n into product of primes and count the number of distinct prime divisors.

B. Regular Bracket Sequence

Read the string from left to right and calculate the balance of brackets at each step (i.e., the difference between the number of "(" and ")" characters written out). We need to keep this balance non-negative. Hence, every time when the balance equals 0 and we read the ")" character, we must omit it and not write it out. The answer to the problem is twice the number of ")" characters that we wrote out.

C. Parquet

We'll derive several necessary conditions for the parquet to be possible. If some of them is not fulfilled, the answer is "IMPOSSIBLE".
1. m*n must be even, because it equals the total area of the parquet, and the area of each plank is even.
2. Suppose m (the number of columns) is odd. Paint the living room in two colors — black and white — in the following way: the first column is black, the second one is white, the third one is black, ..., the last one is black. The number of black squares is n greater than the number of white squares. The planks 1x2 and 2x2 contain an equal number of black and white squares, so we must compensate the difference with 2x1 planks, and their number must be at least n/2. In this case we can parquet the last column with these planks, decrease b by n/2 and decrease m by one.
3. If n is odd, then by similar reasoning a ≥ m / 2.
4. Now m and n are even. A similar reasoning shows that the number of 1x2 planks used must be even, and the number of 2x1 planks used must be even. So, if a is odd, we decrease it by 1, and the same with b.
5. Now we must have mn ≤ 2a + 2b + 4c, because otherwise the total area of planks would not be enough.
6. If all the conditions were fulfilled, we can finish the parquet: divide it into 2x2 squares, and use one 2x2 plank, two 1x2 planks, or two 2x1 planks to cover each square.

D. Tickets

If we picture the graph of the number of 10-euro banknotes, it will be a broken line, starting at the point (0, k) and ending at the point (m+n, n+k-m). Exactly m segments on the line are 'going down', and other n segments are 'going up'. Hence the total number of possible graphs is C(m + n, m) (the binomial coefficient). We need to find out the number of graphs which don't go under the X axis. To do that, we'll calculate the complementary number: the number of graphs which go under the X axis, or, equivalently, intersect the line y=-1.

Here we'll use the so-called 'reflection principle'. Consider any graph that intersects the line y=-1, and take the last point of intersection. Reflect the part of the graph from this point to the end with respect to the line y=-1. We'll have a new graph, ending at the point (m + n,  - 2 - n - k + m). Conversely, any graph ending at this point will intersect the line y=-1, and we can apply the same operation to it. Hence, the number of graphs we're interested in equals the number of graphs starting at the point (0, k) and ending at the point (m + n,  - 2 - n - k + m). Let a and b be the number of segments in such a graph which go up and down, respectively. Then a + b = m + n, a - b + k =  - 2 - n - k + m. It follows that a = m - k - 1, and there are C(m + n, m - k - 1) such graphs.

So, the probability that the graph will go down the X axis is 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)). The answer to the problem is 1 - (m(m - 1)... (m - k)) / ((n + 1)(n + 2)... (n + k + 1)).

E. Multithreading

It's clear that we must have 1 ≤ w ≤ Σ_i n_i. If this condition is true, we show how to achieve the desired result in the following cases:
1. N = 1, w = n₁. Obvious.
2. N ≥ 2, w ≥ 2. For w = 2, the schedule is the following: 1, all loops of processes 3..N, n₂ - 1 loops of the second process, 1, 2, n₁ - 1 loops of the first process, 2. For w > 2, we just need to move several loops from the middle of the sequence to the end.
3. N ≥ 2, w = 1, and there exists an index i such that n_i = 1. Then the schedule is the following: i, all loops of other processes, i.

Now we'll show that in any other case the result w is impossible. The case N = 1, w ≠ n₁ is obvious. We have one more case left: N ≥ 2, w = 1, and n_i > 1 for each i. Suppose that there exists a schedule which results in y = 1. Consider the last writing operation in this schedule; suppose it is executed by the process i. Then the corresponding reading operation should have read the value y=0. This means that there were no writing operations before. But this is impossible, since n_i > 1, and this process executed n_i - 1 read/write loops.

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

A. You're given a string...

Iterate over all substrings, starting with the longest ones, and for each one count the number of appearances. The complexity is O(L⁴) with a small multiplicative constant.

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. Letter

To find the smallest rectangle containing the picture, iterate through the pairs (i,j) such that the j-th symbol in i-th line is '*'; find the minimum and maximum values of i and j from these pairs. The rectangle to output is [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. Die Roll

If the maximum of Yakko's and Wakko's points is a, then Dot will win, if she has not less than a points. So the probability of her win is (6 - (a-1)) / 6. Since there are only 6 values for a, you can simply hardcode the answers.