Need an efficient algorithm to solve the following problem
-
The problem is the following: Given N containers with different sizes between 1 and N (2 <= N <= 10^5), each of them placed in a line, determine how many places can be freed if one container can be placed in another only if its size is less that the others size and they don't have any other containers between them. Multiple placings can be made, so if there are containers placed in each other, they can be placed in another container (if the bottom container size is less than the others size), a container can be placed in another group of container (if its size is less than the top container size), and a group of containers can be placed in another group of containers with similar rules. Example: if N = 8 and the containers are placed in the following order: 1 8 2 4 3 6 7 5, then 7 places can be freed; we place 3 in 4, then 2 in 3, 6 in 7, 5 in 6, 4 in 5, 7 in 8, and 1 in 2. This way all the containers can be packed in a single group. My idea of solving this problem is the following: calculate the minimum difference between all the neighbour containers sizes, then find the first pair where this minimum appears and make a placement. Then repeat the whole process again until no placements can be made. Then calculate the freed places. This can be done trivially in quadratic time, but that is too slow. The other thing that bothers me that this method may not lead to the optimal solution. Note: I have to implement the algorithm in C++, and my program has to finish in 200ms. This is why a quadratic solution has no chance. Also, I don't want to have my job done by others, I posted this because I got stuck solving the problem, and needed some help to know if my approach is correct or how can I make optimizations.
-
The problem is the following: Given N containers with different sizes between 1 and N (2 <= N <= 10^5), each of them placed in a line, determine how many places can be freed if one container can be placed in another only if its size is less that the others size and they don't have any other containers between them. Multiple placings can be made, so if there are containers placed in each other, they can be placed in another container (if the bottom container size is less than the others size), a container can be placed in another group of container (if its size is less than the top container size), and a group of containers can be placed in another group of containers with similar rules. Example: if N = 8 and the containers are placed in the following order: 1 8 2 4 3 6 7 5, then 7 places can be freed; we place 3 in 4, then 2 in 3, 6 in 7, 5 in 6, 4 in 5, 7 in 8, and 1 in 2. This way all the containers can be packed in a single group. My idea of solving this problem is the following: calculate the minimum difference between all the neighbour containers sizes, then find the first pair where this minimum appears and make a placement. Then repeat the whole process again until no placements can be made. Then calculate the freed places. This can be done trivially in quadratic time, but that is too slow. The other thing that bothers me that this method may not lead to the optimal solution. Note: I have to implement the algorithm in C++, and my program has to finish in 200ms. This is why a quadratic solution has no chance. Also, I don't want to have my job done by others, I posted this because I got stuck solving the problem, and needed some help to know if my approach is correct or how can I make optimizations.
You set no limit on N, so there is no solution that will always "finish in 200 ms" ... (which is a long time) ... unless you add a timer; if it runs too fast.
"(I) am amazed to see myself here rather than there ... now rather than then". ― Blaise Pascal