You can also download the entire editorial from here.
Problem A: SPOJ BSHEEP
Have to find the convex hull of the points. An O(n logn) approach is required as ‘n’ is large. Use Graham’s scan to find the convex hull. Pretty straight forward. Avoid floating point calculations as much as possible. This problem offers all annoying details one can think of(collinear points, repeated point coordinates, less-than-3-point inputs,...). When all the points are collinear, you have to return twice the distance between the furthest pair.
Problem B: LightOJ-1129(Consistency Checker)
This problem can be solved by the data structure named TRIE. Those who haven’t come across this algorithm please read this blog. All you need to do is push all the strings into the trie and later check if all the endpoints of the strings are leaves of the trie tree. This problem can also be solved by hashing. First we precalculate the hash value of all the indices of all strings. Then for each string we check if there is any other string whose prefix of equal length has the same hash value as our given string.
Problem C: LightOJ-1137(Expanding Rods)
We get two equations here: L' = r1 * ang; L = 2 * r2 * sin(ang/2); where ang is the angle subscribed by the arc L’ at the centre. Now we binary search on r (r1==r2) to obtain the value of ang and the final answer is r — r*cos(ang/2).
Problem D: Codechef Shift The String
This was the only problem on KMP in the contest. Due to technical problems, this problem statement was not properly visible, but this problem is worth solving. Let's say we append string B at the end of string B. We get: B1,B2...BN B1,B2...BN. The thing worth noting is that after K shift operations we get BK+1,BK+2...BN,B1,B2...BK. This string(which we get after K shift operations) is now a substring of the new string that we got by appending B at the end of B.
KMP helps us in finding all prefixes of a string X in string Y. So we'll search A in B.B(means concatanation of B with B) which will help us in knowing which prefixes of A are present in B. We'll choose an answer that gives us the largest prefix, also it'll give the index at which that prefix matches, from which we can find the number of shifts required.
Problem E: LightOJ 1224
This is another problem that requires TRIE. Insert all the strings into the trie and keep a counter how many times each node is visited. Each time while visiting a node update the answer with max(answer, depth of node*number of times the node is visited) .
Problem F: LightOJ 1258(Making Huge Palindromes)
With Manacher’s algorithm find the length of the longest palindrome that finishes at the last character of the string. If this length is ‘a’ and the size of the string is ‘sz’ then the smallest length that needs to be appended to make the string a palindrome is (2*sz-a).
Problem G: LightOJ 1267(POINTS IN RECTANGLE- II)
Compress the y coordinates(so that you can use a data structure like BIT or segment tree) . The DS will keep track of the y coordinate;ie, if j’th position in your DS has value 2 that means until now we have found 2 points as having ‘j’ as ordinate. Now line sweep from left to right. When you encounter a point, increase the count in your data structure(BIT) by 1. When you encounter start edge of a rectangle, say it stretches from y1 to y2, keep track of the number of points that occur between y1 to y2 until now. These are the points that occur between y1 to y2 but are located to the left of starting edge of the rectangle and thus outside the rectangle. When you encounter the finishing edge of a rectangle, say it also stretches from y1 to y2, find the number of points that occur between y1 to y2 . These are all the points that occur to the left of finishing edge, and thus may occur inside or outside the rectangle. Remember, we kept track of the number of points occurring to the left of the starting edge of the rectangle which are outside the rectangle. Therefore, number of points inside the rectangle = number of points to the left of finishing edge(within y1 to y2) — number of points to the left of starting edge(within y1 to y2). Use the DS to find out the number of points within y1 to y2.
Problem H: POJ HOTTER COLDER
This problem is straight forward implementation of half planes.
Problem I: Weakness and Poorness
F(x)=max(abs(a1-x),abs(a2-x),…,abs(an-x)) Here we have to find the value of x for which F(x) is minimum.
A little observation will help you find out that F(x) is a convex function(not exactly convex, but lets use this word anyway). Use Ternary Search to obtain the value of ‘x’, for which f(x) is minimum.
Problem J: CodeChef MAKPALIN
First, if we are inserting a character at i’th position and want this to be a valid position, we should ensure that prefix of length i−1 is equal to suffix of length i−1 in the original string. This can be pre-computed in O(N) time. Another way is to pre-compute the prefix and suffix hashes of the string as F[i] denoting the hash of prefix of length ii and B[i] denoting the hash of suffix of length ii. While validating, we can simply check if F[i] evaluates to the same value as B[i]. Secondly, the character that would be inserted at i’th position would now be equal to (N−i−1) th position. The only thing left to validate is whether the substring S[i,N−i−2] is palindrome or not. This can again be pre-computed in a separate array as in: F(i,N−i−2) is palindrome if and only if F(i+1,N−i−3) is palindrome and S[i] is equal to S[N−i−2]. This can again be done in O(N). The same thing can also be checked using Prefix and Suffix hashes if pre-computed before. Do not forget to check some corner cases, and when you are inserting the characters at > N/2 positions. You might have to do small changes in the implementation. If both the checks are valid, then we add +1 to our count of valid positions.
Problem K: UVA 866(Intersecting Line Segments)
Find out the number of total intersections with the help of cross product . Consider only proper intersections. Total number of line segments = No. of Original line segment + Total Intersections
