131.md (8600B)
1 Source: https://codeforces.com/blog/entry/3256 2 3 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! 4 Also, sorry if I wrote something wrong, English isn't my first language. 5 Also, (a b) is a choose b (a!/(b!(a-b)!)). 6 **Problem A** 7 8 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. 9 10 It can be easly done in O(n), where n is the lenght of the string. 11 12 **Problem B** 13 14 First, let *count(i)* be the numbers of occurrences of the number *i* in the input, 15 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. 16 17 Since 0 "is opposite to itself", but "a client can't form a couple with 18 him/herself", the number of valid pairs *(0,0)* will be *(count(0) 2)*. Just sum 19 this value to the previous computed sum and print. 20 Use 64 bits-types to do the math. 21 22 **Problem C** 23 24 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. 25 26 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. 27 28 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). 29 30 **Problem D** 31 32 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'). 33 34 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'. 35 36 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. 37 38 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)*. 39 **Problem E** 40 41 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. 42 43 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}*. 44 45 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. 46 47 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). 48 49 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. 50 51 UPD: [nab](../../../profile/nab "Expert nab") said in the comments that an easier solution can be correctly done in O(m) time. Thank you! 52 53 **Problem F** 54 55 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*. 56 57 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. 58 59 1 60 S1F 61 1 62 63 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" 64 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. 65 66 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. 67 68 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*. 69 70 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).