Hi guys, my brother came up with an interesting question. I tried to come up with a solution but I reduce its complexity. The question goes as such: Given N rectangles of size(hi, wi)(rectangle i has height hi and weight wi), find the rectangle with the smallest area that can fit all the other rectangles without them overlapping. You can rotate the rectangles. N, wi, hi <=10^4 I'm open to any kind of discussion.

Hello, I recently got an interesting question from my old teacher. Given two strings A and B(of size <=2000000) find the sum of the longest common prefixes of A and all substrings of B. I reduced this to finding the longest common prefix of A and all suffixes of B and found a solution in O(NlogN) time using suffix arrays. Because it consumed a lot of memory, I switched to hashing and it worked to some extent but it seems O(NlogN) is too large as I get TLE. I was thinking whether I could change the KMP algorithm a bit to get exactly what I need but I can't seem to find a way. Do you guys have any ideas?

So I was given a question that sounded something like this: Given N numbers(N<=400000), I have to answer M queries(M<=1000000). A query consists of 2 numbers (a,b) and I have to find the b-th greater element than the element at position a. Since b<=5 I generated all the answers before answering the queries so that I could answer any query in O(1). Problem is, I know how to generate this array in O(NlogN) and this takes too much time. I was told I could adjust the Next Greater Element problem idea(http://www.geeksforgeeks.org/next-greater-element/ — this question), and get an overall time complexity of O(n) (rather O(5*n) as b<=5). Any hints would be greatly appreciated.