124A - The number of positions
Enumerate all the integers i and find out those that satisfy both i - 1 ≥ a and n - i ≤ b.
Generate all the feasible permutation patterns and find out the one under which the difference between the maximum number and the minimum integer is the smallest.
We divide the positions into the following sets. A2 = (2, 4, 6, ..., 2m1), A3 = (3, 6, 9, ..., 3m2), A5 = (5, 10, 15, ..., 5m3),...
One can see that for any prime integer p > 2, Ap always has at least one common position with A2, as long as the index 2p does not exceed the range. Thus, we find out the maximum such prime integer p', and then count the total number of different positions belonging to sets A2, A3, ...Ap'. These positions must have the same letters, while the other positions can have any letter. Therefore, the left work is to determine whether we have enough number of the same letter.
We first focus on the first condition and consider y = 0. One can see that the bad points are distributed on the X-axis with distance 2a. After increasing y to 1, 2, ... + ∞ , one can find that the bad points form multiple lines with - 45 degrees. Similarly, the second condition results in multiple lines with + 45 degrees.
As a result, the bad points have divided the whole plane into infinite grids. To get from the starting point to the ending point, we have to cross several (maybe zero) grids. The answer is just the least number of grids that we have to cross. In fact, this is quite similar to the Manhattan Distance. We consider the lines with + 45 and - 45 degrees as the “X” and “Y” axis, respectively. Then, we can calculate the manhattan distances of the two points, along the “X” and “Y” axis, as Dx and Dy. The answer is max(Dx, Dy).
I read the tutorials and I think the ideas behind this problem is really very amazing. It needs quite strong insight to reduce the problem to single dimension, which is not that straightforward, at least for me. I think I should work harder to improve my insight.
Комментарии (0)
