We can adopt two hash tables to record the total number of letters appearing in the first two strings and the third string, respectively. Then, we check whether the two hash tables are exactly the same or not.
It is clear that if y%a = 0, it is definitely not inside any square. Otherwise, we first calculate which row does the point fall into, and then the left work is straightforward implementation.
Notice that the squares are infinitely extended from bottom to top, and the figure only serves as a simple illustration.
There exists a solution with complexity O(N2logN).
Let us denote the number of taller people standing in front of each person as a[i]. At first, we sort all the people in an increasing order of a[i]. Note that we are going to arrange all the people in this order, and the left work is to assign a reasonable height to eacg person.
We enumerate each person, and find the tallest a[i] people standing in front of him, whose height are denoted as b1 ≤ b2 ≤ ... ≤ ba[i] and increase their height by one while “assigning” him a height of b1. If this succeeds till the last person is processed, then we have found a feasible answer.
The main idea is to transform the original problem into a shortest path version. Note that only positions like x - p and x + d matter, since for any other two positions, their distance (here, the distance corresponds to the time it costs to move between them) is a constant integer. For more details, one can check the tutorials (I also learned from that).
Besides, I think this is a very wonderful problem to practice several techniques.
1) Data compression: note that the given range is too large to directly store the positions based on arrays. Thus, one should first compress (or “remap”) the given data into smaller range. A neat method has been introduced in the last notes.
2) Dij algorithm based on priority queue: For sparse graph, using priority queue can achieve a complexity of order O(ElogE). I have found a very well written code 1029303, and I think one can check the “spfa” function there.
3) struct and STL in C++: a well designed struct and STL can simplify the relationship among various data and help write neat codes. I think the code 1029303 has also clearly shown how powerful they are.
Comments (0)
