Hi, these are just some ideas of what I did to solve the problems in #95 (div 2). They're just what I did, better solutions may exist and will be very welcome!
Also, sorry if I wrote something wrong, English isn't my first language.
Also, (a b) is a choose b (a!/(b!(a-b)!)).

Problem A

Just do what the statement asks you to. Check if all letters are uppercase, except for the first one, that you don't need to check. If so, change the case of the entire string. If not, do nothing. Please notice that an one-letter string must have its case changed.

It can be easly done in O(n), where n is the lenght of the string.

Problem B

First, let count(i) be the numbers of occurrences of the number i in the input,
    for -10 <= i <= 10. Remember that there may be negative numbers in the input, so one can use an offset to store these values (use an 21-sized array C and store count(i) in C[i+10]). Except for 0, possible matching are pairs (i,-i), for 1 <= i <= 10. It's easy to see that there will be exactly count(i)*count(-i) valid matching for each i, so just sum them all.

Since 0 "is opposite to itself", but "a client can't form a couple with
him/herself", the number of valid pairs (0,0) will be (count(0) 2). Just sum
this value to the previous computed sum and print.
Use 64 bits-types to do the math.

Problem C

Since the constraints are small, let's just iterate through all possible numbers b of boys in the group and count how many ways we can form the group with b boys.

First, consider only the values where b >= 4. Given b, it's clear that the number of girls in the group must be g = t - b. If g < 1, don't consider this case. Given the values of b and g, there are (n b)*(m g) ways to form the group, since we can combine the boys independently the girls. Just sum (n b)*(m g) for each pair (b,g). Again, use 64 bits-types to do the math.

One could precompute all the values of (i j) using the Pascal triangle, but one could also compute it with the traditional formula, if its implementation takes care of possible overflow (30! doesn't fit in 64-bit integer type).

Problem D

A graph-related problem. The statement makes you sure that the given graph is connected and contains one (and exactly one) cycle. What you have to do is to compute the distance, in number of edges, from all vertexes to the cycle (print 0 for the vertex that are in the cycle. We will call these vertexes 'in-cycle').

First, let's find the cycle and find the vertexes whose answer is 0. The cycle can be found with a regular Depth-First-Search (DFS), storing the fathers of the vertexes. Notice that, during the search, there will be exactly one back edge, say (v_i, v_j). When this edge is found, iterate from v_i to v_j (using the father array) and label the vertexes as 'in-cycle'.

After that, let's compute the answers for the other vertexes. One could "compact" the graph by merging all the 'in-cycle' vertexes into a single vertex. Then, just do another search starting by this vertex and compute the distances, knowing that the distance of a vertex v_i is the distance of father[v_i] plus one.

Also, it's also possible to do as many searchs as the number of 'in-cycle' vertexes if you don't consider others 'in-cycle' vertexes during the search. The running time would still be O(n + m), that, in this problem, is O(n + n) = O(n).

Problem E

Let's first consider that the queens can only attack the other pieces standing in the same line - the case with the columns and both diagonals will be analogous.

Let line[i] be an array that will store all the queens that are in the i-th line on the chessboard. Since it's indexed by the line number, it's only necessary to store the column number of the pieces. So, for example, if we have queens at positions (4,6), (4,8) and (6,5), we will have line[4] = {6,8} and line[6] = {5}.

To check if the queen at position (i,j) is attacking someone in its line, you must check if there is some number greater than j and/or less than j in line[i]. To do that, presort line[i] and binary search j in it. Notice that j will always be successful found by the search. Notice also that there will be some number greater than j iff the found element is not the last one of line[i]. The same applies for the other case: check if j is not the first element of line[i]. If j is not the first nor the last element, the queen is attacking 2 pieces in its line. If j is the only element, the queen is attacking no one, and it's attacking 1 piece otherwise.

Do the same thing (compute all column[i], sort them and, for each queen, binary search) to the column, to the "/" diagonal, and to the "\" diagonal. Remember that a piece at position (i,j) is at the diagonals i+j and i-j. Like in problem B, use an offset to handle the negative numbers in the last case. Store the line number in the column[i] array. There's no different in witch index (line or column) to use in the diagonals arrays (but, of course, use the same chosen index for everyone).

It seems that the sorting part of the algorithm will run in O(n*n*logn) time, since we have O(n) lines, columns and diagonals. However, the sum of the sizes of all these arrays will be m, the numbers of queens. So the running time will be actually near O(m*logm). Binary searching for every queen will take less than O(m*logm), too.

UPD: nab said in the comments that an easier solution can be correctly done in O(m) time. Thank you!

Problem F

The main idea is to, for each pair of lines i₁ and i₂, count the ways you can form the rectangle using a sweep line-like algorithm. The idea is similar to the somewhat classic idea used for the problem that is, given an array of numbers, count how many contiguous sub arrays exists witch sum is equal or greater to some given k.

Let's first of all identify all the points where a star can be found, in its "starting" position and "finish" position. These are the S and F position shown below.

  1
S1F
  1

For each pair of lines i₁ and i₂ (i₂ > i₁) we will keep two indices (or pointers) j₁ and j₂ for the columns, with j₂ > j₁. During the algorithm, we will always analyze the rectangle formed by lines i₁,i₂ and columns j₁,j₂. Let's start with j₁ = 0 and j₂ = 2 (there won't be any star in the rectangle  i₁,i₂,0,(0 or 1) simply because a star won't fit in it). Let's then count the number of stars found in this rectangle. It will be equal to countfinish(i₁+1,i₂-1,j₂), where countfinish(I1,I2,J) is the number of "finish"
positions in the column J between the lines I1 and I2. If this number is equal or greater than k, this rectangle and all the rectangles (i₁,i₂,j₁,j) for j >= j₂ will be valid, so you need to sum m-j₂ to the answer. Then, increment j₁ and recalculate the numbers of stars in the rectangle. It will be equal to the previous number minus countstart(i₁+1,i₂-1,j₁-1), (the definition of countstart() is analogous) since it's the number of starts that are "lost" when we move from j₁-1 to j₁. Check again if the new number is greater or equal than k and repeat the process until the number is less than k. Notice that j₁ will always be less than j₂, since a star needs 3 columns to exists.

Then, increment j₂ and, without changing the value of j₁, repeat the process. Notice that this part of the algorithm will take O(m)*T time (where T is the time needed to calculate countstart and countfinish), since both j₂ and j₁ will "walk" in the columns only one time.

A trick can be made to make T = O(1). For each column j, precompute an array countstart[j], where countstart[j][i] = countstart[j][i-1] + (1 if (i,j) is a "starting" position, 0 otherwise). To compute countstart(I1,I2,J), just use the formula countstart[J][I2] - countstart[J][I1-1], that gives the value in constant time. Do the same with countfinish.

Precomputing countstart and countfinish takes, for each column, O(n) time, so all the precomputing can be done in O(n*m) time. Since we use an O(m)*O(1) = O(m) time for O(n²) pairs of lines, the total time used for the algorithm is O(n*m) + O(n²*m) = O(n²*m). A bit high for n=m=500, but the time limit for this problem was higher than the usual too (5 seconds instead of 2).