Add all the vectors together, and check whether the result is a zero vector or not.
We first enumerate all the sections, and for each section we check all the players to find the one who participates and has the minimum time to finish this section. Then, for this section, we can just bet on this selected player and obtain the corresponding profit. Finally, we add the profits of all the sections together to obtain the required answer.
This problem is solved by straightforward implementation. One should be careful that whenever a new query comes, we should immediately check whether a new composite element can be obtained. If yes, we should implement this operation and update the results at once.
I think this is a very nice problem to practice dealing with a game, which two people take turns to play using the optimal strategy.
At first, one can find that it is not necessary to take the "reflection" operations into consideration. When someone first chooses to reflect x and y, it in fact means that he must have been in a losing state. However, the competitor can reflect the coordinates again, and thus it returns to the previous state. In other words, the two reflection operations from different players cancel each other.
Next, for each coordinate (x, y), we assign it with a state, indicated by 'losing and winning', which gives the final result that one player can achieve if he starts to move from this position. For each position, we can obtain all the feasible positions that he can move to according to the given vectors (note that only the positions inside the circle should be viewed as "feasible"). Moreover, if any of them is a losing state, this position should be assigned with winning state, otherwise with losing state. We can start from the initial position and implement DFS to calculate the states. Note that for some position, if all the next positions to which it can move fall outside the circle, it is definitely a losing state, and this serves as the "return condition" in DFS.
This sort of problem in fact has a general solution, which uses BFS rather than DFS. It looks a little like Topological Order. One can check the book in http://mirror.codeforces.com/blog/pllk for more details.
This problem turns out to be quite easy if one uses the "set<>" in STL of C++. When a new element enters the sliding window, we increase the times that it appears by one, while if an element moves out of the sliding window, we decrease it by one. If one element appears exactly once, then we insert it into the set; otherwise we erase it from the set. Sorting is automatically implemented and maintained in set, and thus the maximum value can be obtained at any time with constant complexity O(1). "Insert, erase, sort" are all implemented with complexity O(logN), which leads to a total complexity of O(NlogN).
Comments (0)
