A. Letter

When searching for the result all we have to do is to save the minimum and the maximum value for line/column indexes where we find an '*' character. The result consists of a submatrix, from (lmin,cmin) to (lmax,cmax). The result is obtained in O(nxm).

B. Young Photographer

At the beginning determine the intersection of all the n segments (beware when a>b). If the intersection is void then the answer is -1, otherwise determine the distance from the photographer's location to that segment. This algorithm needs O(1) memory and O(n) operations.

C. Four Segments

It is useful to define some structures, such as POINT and SEGMENT and a function to verify if two POINTS are equal, and a criteria for ordering the POINTS. Create an array consisting of all distinct endpoints and check whether it has exactly four elements or not. After that check if the projections of those points on Ox and Oy axis contain exactly two values. In the end search for the existence of the segments formed by every two consecutive points in the set of the initial four segments.

D. Two Paths

Consider an undirected graph having n vertices and n-1 edges (a tree). Remove and put back, one by one, each of its edges. After one edge is removed there are exactly two connected components. For each of them calculate the maximum distance between two vertices. This can be done performing two breadth-first traversals. The best product is saved. The number of operations depends on how the graph is represented. If we use adjacency matrix for breadth-first traversal and the list of edges for the tree itself, we have a total of O(n^3) operations.