|
•a_h1926
|
 |
« Răspunde #3 : Octombrie 31, 2012, 15:35:30 » |
|
1. We want to count separately the number of palindromic sequences with even length and uneven length. We will now try to solve the problem for even palindromic sequences, as the other case is symmetrical. For every i from 1 to n, we will count how many palindromic sequences are centered on (i, i+1), which is equivalent to finding the largest possible L such that subsequence (i-L, i+1+L) is a palindrome. We can use binary search to find this value, and we now need to implement fast string comparison, which we can do by preprocessing some hash values.
2. Let’s consider the function F(x) = the maximum number of occurences of some substring of length x from the original string. We can observe that F is a decreasing function, thus we can use binary search to find the largest x such that F(x) >= k. Now we need to compute F(x) efficiently. We will iterate over the original string and insert the hash code for every substring of length x in a table. The maximum number of equal values in this table will be the value of F(x), and this can be easily computed in O(n) if we update the maximum value everytime we insert a new substring in the hash (for every code we keep in the table how many elements have that code). The final complexity is O(nlogn)
3. We could use binary search to find the side length of the square, and for a fixed length L, we want to see if there are at least 2 squares that are identical. For every element in the bitmap, we will compute a hash code that represents the substring formed by it and the previous L-1 elements on its line. Now, we apply the same process to the newly computed table, but for the previous L-1 elements on it’s column, and so, every element in the final table will have the hash code for an entire square. The only thing left to do is iterate over the elements in the final table and see if there is at least one duplicate. Final complexity is (n^2 logn), if the bitmap has size nxn.
4. If the string has period L, then S[1..L] = S[L+1...2L] = ... = S[k*L+1, (k+1)*L], with k from 0 to N/L - 1. This is exactly what we will try to find out, if the substring S[1...L] equals every other substring considered above, and for this we can use precomputed hash codes. Now, we just need to check this for every L from 1 to N. The number of steps is n (1 + 1/2 + 1/3 + ... + 1/n) = nlogn, so the final complexity is O(nlogn).
5. We build the hash code for both strings. Now, we will literally rotate one of the strings by updating its hash code (we erase the first character and add the new one), and we only need to see if there is at least one position in which the two hash codes are equal. Since there are n possible rotations, we have O(n) time complexity.
6. For two polygons to be similar, the corresponding angles must be equal and the ratio between the corresponding segments must be the same (if we have n vertices A1, A2, ..., An and B1, B2, ..., Bn, then A1A2 / B1B2 = A2A3/B2B3, etc.). From A1A2/B1B2 = A2A3/B2B3, we also deduce that A1A2/A2A4 = B1B2/B2B3, and similarly we have the equivalence between the previous relations and A(k)A(k+1)/A(k+1)A(k+2) = B(k)B(k+1)/B(k+1)B(k+2). Now, for every vertex in each polygon, we will associate it two values: the angle formed by the two segments incident in it, and the ratio between the two segments. We notice that each polygon was reduced to a string, in which a character consists of these two values. We observe that for the two polygons to be similar, one of the strings must be a rotation of the other, and we reduced this problem to the previous one which has an O(n) solution. Also, the number of steps to build the two “strings” takes time O(n), so the final complexity is O(n). The only thing at which we must be careful is in case we can "mirror" one of the polygons, case in which we just need to check with one of the strings reversed, so this doesn't influence the time complexity.
7. We will try to see the longest periodic prefix that has a fixed period L. This is equivalent to finding the largest k such that S[1...L] = S[L+1...2L] = ... = S[(k-1)L+1...kL], and the length of that prefix will be L*k. We can proceed just as in problem 4 and the resulting complexity is O(nlogn).
8. We will use a DFS and we keep a stack with the currently active nodes, so we can determine quickly which is the k-th father of a node. Let’s denote F[ x ][k] = the k-th father of x. Now, when we are at a node x, we want to see if the string formed by F[ x ][k-1], F[ x ][k-2], ..., F[ x ], x matches string P. We can do this by computing hash codes for every node x based on the hash code of its father, and compare it with the hash code of string P. When we compute the hash code for node x, the new character added to the string is the one associated with this node and the character we delete is the one associated to the k-th father of x. Resulting complexity is (n), where n is the number of nodes.
|
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena