reiracofage's blog

By reiracofage, 8 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.

  1
S1F
  1

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

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

8 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Problem E can be done in O(n+m) -- i.e. O(m) when m is at least on the order of n.

For the horizontal case, we determine the leftmost and rightmost queen on each row in O(n+m). The vertical and diagonal cases are similar. Then, we can compute the number of attacked queens for each queen in O(m) by simply checking whether it is the leftmost, rightmost, etc. in it's row/column/diagonals.
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Why only if m >> n? This solution works for all n and m. O(m)
    • 8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      The solution in the blog is O(m*logm). My solution is O(n+m) = O(max(n,m)), which can trivially be reduced to O(m) if you use an associative array and only compute rows/cols/diagonals with queens on them, but the overhead is unnecessary.
      • 8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        My solution is probably the same as yours. By saving the left most, right most, top most etc...
        But, I was just wondering why did you write m >> n (which you have changed now, see Rev 1 or your first comment).
        • 8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Indeed the first revision of the comment wasn't too clear, so I edited it to be more clear and accurate.
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Wow, that's correct! We don't need to know all the line[i]/column[i] array, but only their first and last element. It can be done in linear time.
    Thank you very much!
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thank you........this is very useful................
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it
I implemented the same solution for D, but it was long. I stumbled upon this thread:

http://codeforces.com/blog/entry/3255

Have a look. It's clever.
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, if you do as many search as the number of "in-cycles" vertices, isn't the time O(n^2), that is n times BFS ?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Indeed, this solution consists in doing a BFS n times. However, notice that the sets of vertices and edges visited by each BFS don't intersect — a BFS will not visit a vertex or an edge that was already visited by some other BFS. This happens due to the "tree-likeless" of the graph. For each in-cycle vertex, the subgraph trasversed by its BFS is a tree and cannot reach the other trees, rooted at the other in-cycle vertices. Since each vertex and edge is visited only once during all BFSs, the solution remains O(n).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help tell me why I am getting WA for problem D or where my code goes wrong.

Here's my submission. 11783845

I have used the same algo as mentioned in the editorial above.

Thanks. :)

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thank you so much

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any ideas why my code for problem E giving TLE on case 29. I don't think i am doing anything different from the editorial given. Any optimisation? https://codeforces.com/contest/131/submission/55425664

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can read my solution here : Link

    Pretty straightforward to understand.

»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem D, you also can detect all vertices in a cycle based on the degree of vertices. The ideal is mentioned in this article. Check my submission for more detail.