reiracofage's blog

By reiracofage, 13 years ago, In English

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 (vi, vj). When this edge is found, iterate from vi to vj (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 vi is the distance of father[vi] 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 i1 and i2, 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.


For each pair of lines i1 and i2 (i2 > i1) we will keep two indices (or pointers) j1 and j2 for the columns, with j2 > j1. During the algorithm, we will always analyze the rectangle formed by lines i1,i2 and columns j1,j2. Let's start with j1 = 0 and j2 = 2 (there won't be any star in the rectangle  i1,i2,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(i1+1,i2-1,j2), 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 (i1,i2,j1,j) for j >= j2 will be valid, so you need to sum m-j2 to the answer. Then, increment j1 and recalculate the numbers of stars in the rectangle. It will be equal to the previous number minus countstart(i1+1,i2-1,j1-1), (the definition of countstart() is analogous) since it's the number of starts that are "lost" when we move from j1-1 to j1. 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 j1 will always be less than j2, since a star needs 3 columns to exists.

Then, increment j2 and, without changing the value of j1, 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 j2 and j1 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(n2) pairs of lines, the total time used for the algorithm is O(n*m) + O(n2*m) = O(n2*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).

Full text and comments »

  • Vote: I like it
  • +29
  • Vote: I do not like it

By reiracofage, 13 years ago, In English
Hi, I have a suggestion!
How about letting users lock a problem without the need of passing them in the pretests? This would let them hack other's solutions without having one. Of course, after locked, the problem can't be submited anymore.
This would reward the coders that don't know how to solve a problem, but know how to NOT solve it.
This is possible in "the other coder site"...

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it