Lets assume that we have more boys than girls (the other case is solved similarly). Then we can construct one of the optimal solutions in the following way: we add pairs consisting of a boy and a girl (BG, in that order) to the end of the line until we don't have girls any more. Then add remaining boys to the end of the line. For instance, with 7 boys and 4 girls we will come to the solution BGBGBGBGBBB.
For each x from 1 to 5000 calculate count(x) — the number of measurements equal to x. The iterate over all possible minimal values m (from 1 to 5000). For a fixed m we can easily figure out which numbers we have to erase: we should erase every number k that k < m or k > 2·m. To find out the number of such values in the given sequence, we should sum up values count(k) for all such k.
One of the solutions to the problem is breadth-first-search (BFS). Vertices of the graph correspond to all possible pairs (r, c), denoting the row and the position of the cursor. Each vertex has at most four arcs leaving it (these arcs correspond to pressing the buttons). So we need to find the shortest path from one vertex to the other. There are at most 107 vertices and at most 4·107 arcs. This problem can also be solved with some greedy observations.
Lets iterate over all pairs of rows i, j (i < j), that bounds the sub-table from the top and from the bottom. Then for each character ch make a list of such column numbers k that T[i, k] = T[j, k] = ch. Consider such list for some fixed character ch. All we need to count is the number of pairs l, r (l < r) in this list such that the sub-table with corners at (i, l) and (j, r) contains not more than k characters "a". This can be done using two standard techniques: two-pointer method and calculating partial sums.
First lets learn how to simulate the process with all priorities known. We will keep the priority queue of tasks. The task enters the queue when the printer receives this task, and leaves the queue when the printer finishes it. Then every change in the queue happens when one of the two possible events occurs: the printer receives some task or finishes printing some task. Between the consecutive events printer just prints pages from the tasks with the highest priority. So, if we maintain a set of events, the simulation can be done in O(NlogN).
To solve the problem, make an obvious observation: the higher priority the task has, the sooner the printer finishes it. Then the required missing priority can be found using binary search. Also we can search the missing priority among O(N) values. The overall complexity is O(Nlog2(N)).
This problem also has O(NlogN) solution, which will be described later.
Không có nhận xét nào:
Đăng nhận xét