Heuristic Approach for Finding Order Frequency Test
In the article An example of how to write tests in Yandex.Contest, recommendations were given for successfully passing Yandex tests. One of the tests – finding the largest number of orders for a given area of a rectangle, we solved by simply enumerating all orders, which increases the complexity of finding a solution exponentially. But there is a more elegant solution. However, such solutions do not come immediately – the task is worked out in the subcortex for some time (several days), and then suddenly, when you go to the subway or walk with the dog, bam and the solution is ready almost instantly.
Eureka #1
So what’s “eureka” here? All orders have x and y coordinates. Then we write them into a 3-dimensional int array[][][]where the first index is x, the second is y, and the value is a list of order numbers at that point on the map (a one-dimensional array of int[]). Yes, in order not to create an empty space, we will determine the minimum values of the coordinates of orders and subtract them from x and y – that is, we will do a “detuning from emptiness”.
Thus, sorting through the points inside the rectangle (the algorithm for finding its sides is given in the solution of the problem in the above article), we directly access the list of order numbers using the coordinates in this array, and if it is empty, then we skip the point, otherwise we take the length of the list of order numbers and sum up with the current amount of orders inside the current rectangle.
Eureka #2
But that’s not all. Now we can start calculating the required values inside the rectangle without going through all the points inside, but just subtracting all the points of one edge and adding all the points of the opposite one (if the first rectangle has already been calculated). For example, if we move the rectangle up, say, along the Y axis, then we iterate over all the points on its lower edge (horizontal), and subtract them from the total orders inside the previous rectangle, and take the edge of the new rectangle – at the level y + dy + 1 (opposite horizontal) and add all points from it to the result. Where dy is the y-size of the rectangle and y is the current rendering level. Thus, we significantly reduce the number of calculations. It is clear that if we move the rectangle along the X axis, say from left to right, then we also process its vertical sides.
Eureka #3
Well, it’s not eureka of course, but still. We can start using the intermediate results from the first pass (bottom up). Then further we do not need to calculate all the positions each time, we will again use the approach with subtracting and adding points of opposite edges, but already moving horizontally – for example, from left to right. This will not improve the algorithm much – but you can play around with the lengths of the sides and choose the direction of the first pass, depending on which side of the rectangle is smaller – vertical or horizontal.
conclusions
In general, this is an eternal struggle between the speed of execution and the memory used – the more memory is used, the faster the task is solved and the less calculations. In fact, this is a trivial cache))
