New Year is coming, and Jaehyun decided to read many books during 2015, unlike this…
- User
New Year is coming, and Jaehyun decided to read many books during 2015, unlike this year. He has n books numbered by integers from 1 to n. The weight of the i-th (1 ≤ i ≤ n) book is wi.
As Jaehyun's house is not large enough to have a bookshelf, he keeps the n books by stacking them vertically. When he wants to read a certain book x, he follows the steps described below.
- He lifts all the books above book x.
- He pushes book x out of the stack.
- He puts down the lifted books without changing their order.
- After reading book x, he puts book x on the top of the stack.
He decided to read books for m days. In the j-th (1 ≤ j ≤ m) day, he will read the book that is numbered with integer bj (1 ≤ bj ≤ n). To read the book, he has to use the process described in the paragraph above. It is possible that he decides to re-read the same book several times.
After making this plan, he realized that the total weight of books he should lift during m days would be too heavy. So, he decided to change the order of the stacked books before the New Year comes, and minimize the total weight. You may assume that books can be stacked in any possible order. Note that book that he is going to read on certain step isn't considered as lifted on that step. Can you help him? Input
The first line contains two space-separated integers n (2 ≤ n ≤ 500) and m (1 ≤ m ≤ 1000) — the number of books, and the number of days for which Jaehyun would read books.
The second line contains n space-separated integers w1, w2, ..., wn (1 ≤ wi ≤ 100) — the weight of each book.
The third line contains m space separated integers b1, b2, ..., bm (1 ≤ bj ≤ n) — the order of books that he would read. Note that he can read the same book more than once.
Output
Print the minimum total weight of books he should lift, which can be achieved by rearranging the order of stacked books.
Examples
Input
3 5 1 2 3 1 3 2 3 1
Output
12
Note
Here's a picture depicting the example. Each vertical column presents the stacked books.
Assistant
We need to interpret problem correctly.
We have n books with weights w_i. They are stacked vertically (order is a permutation). There is a process to read a book:
- Lift all books above book x.
- Push book x out.
- Put down lifted books without changing order.
- After reading, put book x on top.
So effectively, when reading a book x, we remove it from its current position in the stack and then place it on top. The cost incurred is the sum of weights of the books above x (i.e., those we lift). Books are not counted as lifted if they are the one being read.
We are given a sequence b_1,...,b_m of books to read (in order). We can choose the initial stack ordering (permutation) to minimize total cost (sum over days of sum of weights of books above the book being read that day, before removal). The process updates the stack after each day: after reading, book x is placed on top. So the stack evolves deterministically given initial ordering and reading sequence.
Goal: choose initial permutation to minimize total lifted weight.
Observations: The process is similar to "move-to-front" (MTF) operation on a list. We have a list (stack from bottom to top? Actually stack vertical: bottom is first, top is last? Usually stack: books placed on top; reading: lift books above x, so books above are those on top of it. So order from bottom to top is the stack order, with top being highest. When we remove x and put it on top, that's like moving x to the front (top). But careful: "put x on top" means after reading, it becomes the topmost book. So the stack after operation: all other books remain in same relative order (the lifted ones go down, then x on top). So indeed it's like we move the accessed element to the front of the list (where front is top). But note that lifting cost: sum of weights of books above x. That is sum of weights of elements that are before x in the list if we consider list from top to bottom? Let's define ordering.
We can represent the stack as a sequence from top to bottom? Actually easier: Let's consider the order of books from top (position 1) to bottom (position n). The cost to access book x is sum of weights of books that are above it, i.e., those with positions smaller (closer to top) than x's position. So if we denote the stack as a list L where L[1] is top, L[2] next, etc., then cost = sum_{i=1}^{pos(x)-1} w_{L[i]}. Then after reading, we move x to top: new list L' = [x] + (L without x). So it's exactly the standard move-to-front (MTF) list update.
Given a request sequence, total cost depends on initial ordering. This is reminiscent of the optimal static ordering for a list under MTF cost model. But here the cost is not the position (or comparisons) but sum of weights; it's a weighted version. We can choose the initial order arbitrarily.
But maybe we can minimize total cost by ordering books in some optimal way. However, the process is dynamic: after each access, the list changes. So the cost of future accesses depends on order. This is similar to problem of minimizing total cost for weighted MTF, but with fixed sequence of requests. Is there known approach? For standard unweighted case (all weights 1), total cost is fixed regardless of initial order? Actually, under move-to-front, total cost (sum of positions-1) is something like? I recall that for any initial order, the total cost for a sequence of accesses under MTF is the same? That seems unlikely. Let's test small examples.
Suppose books 1,2,3, weights all 1, requests: [1,2,1]. Starting order (1,2,3) with 1 at top? Actually let's define top as first. If initial order = [1,2,3] (top=1, bottom=3). Day1: access 1, cost=0 (since top). After move-to-front, list stays [1,2,3]. Day2: access 2, position 2 => cost 1 (book 1). After: move 2 to top => [2,1,3]. Day3: access 1, position 2 => cost 1 (book 2). Total=2.
If initial order = [2,1,3]: Day1: access 1, position 2 => cost w2=1. After: [1,2,3]. Day2: access 2, position 2 => cost 1 (book 1). After: [2,1,3]. Day3: access 1, position 2 => cost 1. Total=3.
So total cost differs. So initial ordering matters.
Now with weights: we can choose ordering to minimize total cost.
We need an algorithm for n up to 500, m up to 1000. This suggests DP or greedy.
We need to model the effect of ordering on cost. Let's try to formulate.
We have a list that evolves via MTF. The cost of an access is sum of weights of books that are before it in the current list (i.e., on top). After access, that book goes to front.
This is reminiscent of optimal offline static list for MTF: it is known that the best static order (one that does not change) for a sequence of accesses is to order books by decreasing frequency (or some metric) but here list is dynamic; but we can choose initial order. However, due to MTF, the list keeps changing. But perhaps we can think of the final order after processing sequence? Actually, the process is deterministic given initial order. Another way: total cost can be expressed as sum over pairs of books of some interaction count times something.
Idea: Consider contributions of each pair (i,j). When accessing a book x, the cost includes weight of another book y if y is above x at that moment. So for each ordered pair (y,x) where y != x, the total cost contributed by weight of y is the number of times y is above x at the moment of accessing x.
We can sum over pairs: total cost = sum_{x} sum_{y != x} w_y * (number of accesses to x when y is above x).
We can think of the relative order of books in the list at each time. Under MTF, the relative order of books evolves in a certain way. It might be similar to the "list update problem". There's known results: for offline optimal static order (i.e., fixed order that does not change), the optimal ordering is by decreasing ratio of access frequency to weight? Actually, there is something called "frequency order" for list accessing with MTF? Wait, we are not keeping order static; we allow dynamic changes because we have to follow MTF rule. But we can choose initial order.
Maybe we can treat it as: we have an initial permutation, and then sequence of moves. The cost for each access to x is sum of weights of books that precede x in current list. Equivalent to: we start with some order, then for each request to x, we add to cost the sum of weights of books that are before x, then move x to front.
This process is essentially the same as the "move-to-front" list update algorithm. The total cost depends on initial order. But we are allowed to choose initial order arbitrarily, so we want to minimize total cost.
One approach: Since n is small (500) and m is 1000, we could consider DP over subsets? 2^500 too large. Need smarter.
Observation: The evolution of the list under MTF has a property: the relative order of books that have been accessed at least once after some time becomes something like: they appear in reverse order of last access time (most recently accessed at front). Meanwhile, books never accessed retain their relative order among themselves but appear after all accessed books? Actually, after some accesses, the list will consist of a prefix of books that have been accessed at least once, sorted by recency (most recent at front), and then a suffix of books that have never been accessed, in their original order. Because when you access a book, you move it to front; if it was in the suffix (never accessed before), you bring it to front and the relative order of other never-accessed books stays same. If it was already in the prefix, you move it from its position to front, shifting the prefix.
So the state can be described by the set of books that have been accessed so far (or the order among them by recency) and the order of untouched ones.
Given that m=1000, we could simulate any initial order and compute cost, but there are n! possible orders, too many. However, maybe optimal order has a special structure: it might be sorted by weight or something.
Let's try to derive expression for total cost.
Let the request sequence be b_1,...,b_m. For each access, cost = sum of weights of books that are before it in current list.
Consider two distinct books a and b. How many times does a's weight contribute to cost when accessing b? That is, count number of times that a is above b at the moment b is accessed. Similarly, count of times b contributes when accessing a.
Under MTF, the relative order between two books changes only when one of them is accessed. Initially they have some order (either a above b or b above a). When a is accessed, a moves to front, so after that, a is above b regardless of previous order. When b is accessed, b moves to front, so after that, b is above a. So the relative order after each access depends on which was accessed more recently: the one accessed later is above.
Thus, at any time, for any pair (i,j), the relative order is determined solely by which book had its most recent access later (or if neither has been accessed, their initial order). So we can think of a timeline: each access flips order to put accessed book on top.
Now consider contributions: When we access book x, the books above it are exactly those books whose last access occurred after the last access of x (i.e., more recent), plus possibly some books never accessed (if x hasn't been accessed yet, its last access is at time -infinity). Actually, careful: The order after some accesses: the list is sorted by descending last access time (with ties broken by initial order for those never accessed). Because MTF ensures that after each access, the accessed book gets the most recent timestamp. So if we assign each book a timestamp equal to the time it was last moved to front (or initial order timestamp for those never accessed, but we need a total order). More precisely, we can represent the state by a list sorted by decreasing "last access time". For books that have never been accessed, we can assign them a "virtual" last access time of -infinity, and among them, their relative order is as in the initial stack (from bottom to top? Actually, initially, the stack has some order. For never accessed books, they appear in the order they were initially, but they are all below any accessed book? Let's simulate: Initial order: say [c, d, e] (top first). None accessed. After first access to e: lift books above e: that includes c and d (if e is not top). Then move e to top => new order: [e, c, d]. So after access, e is on top, and the relative order of c and d remains same (c above d). So indeed, after first access, the list is: e (most recent), then the remaining in original order. After second access to d: d may be below e? Suppose we have [e, c, d]. Access d: d is at position 3, so above it are e and c. After moving d to top: [d, e, c]. So now d is most recent, then e, then c. So order of accessed books is by recency.
Thus, the invariant: At any time, the list consists of a sequence of books that have been accessed at least once, sorted by decreasing last access time (most recent first), followed by the books that have never been accessed, sorted in the order they had initially (which is the same as original order among them, but note that initially they are from top to bottom: originally, all books are in initial order. The ones never accessed remain in that relative order but appear after all accessed ones because accessed ones are moved to front, pushing them down? Actually, after moving some to front, the never-accessed ones get shifted down but their relative order remains the same as initial. So yes, suffix is initial order restricted to never-accessed set.
Therefore, the state can be described by: a set of accessed books and their last access times (order) and the relative order of never-accessed ones as per initial.
Now consider total cost. For each access to b_j, the cost is sum of weights of books that are above b_j. These are:
- All books that have been accessed more recently than b_j (i.e., with last access time > time of this access? But we are at the moment before moving b_j; b_j's own last access time is its previous access time, if any, else -infinity. Books above are those with last access time greater than b_j's current last access time? But careful: b_j is about to be accessed now; before access, its last access time is some t_prev (or -inf). The books with last access time > t_prev are those that have been accessed after b_j's last access; they are above b_j. Also, among books with last access time equal to -inf (never accessed), their order relative to b_j depends on initial order if b_j also never accessed? If b_j has never been accessed, then its position among never-accessed books is determined by initial order; books above are those never-accessed that are initially above it, plus all accessed books (since accessed books are always above never-accessed? Actually, yes, accessed books have been moved to front, so they are above all never-accessed books. So if b_j is never accessed before this access, then above it are all accessed books (any) plus those never-accessed that are initially above it. So it's more complicated.
Maybe we can think in terms of pairwise contributions: For a pair (a,b) with a != b, each time we access b, we add w_a if a is above b at that moment. Similarly for access a.
We can compute number of times a is above b during the entire sequence as a function of initial order and request times.
Let’s denote the requests times 1..m. For each pair (a,b), consider the relative order over time. Initially, either a is above b or b is above a (depending on initial ordering). Then each time either a or b is accessed, the relative order may change.
Specifically, we can model the state of the pair as a binary variable: which book is on top (i.e., above the other). Initially, it's either a above b or b above a. When a is accessed, after the access, a becomes above b (since moved to front). When b is accessed, after the access, b becomes above a. So the relative order after an access is determined solely by which of the two was accessed more recently (or initial if neither accessed yet). Therefore, just before an access, the relative order is determined by the last access among the two before that time.
Now, for each occurrence of b in the request sequence, we need to know if a is above b at that moment (just before access). That is equivalent to: at that time, the most recent access among {a,b} (strictly before this access) is to a (if any), or if neither accessed yet, then initial order: a above b initially means a is above b.
Similarly, for accesses to a, we count if b is above a.
Thus, the total contribution from pair (a,b) to total cost is: w_a * (number of accesses to b where a was accessed last among the two before that access) + w_b * (number of accesses to a where b was accessed last among the two before that access).
We can compute these counts given the request sequence and the initial order (which matters only when neither has been accessed before that access). Also note: after an access to a, a becomes most recent; before that access, we need to consider state.
Let's formalize:
Let T_a = set of times when a is accessed (request indices). Similarly T_b.
We want, for each access to b at time t (in T_b), determine if just before time t, the last access among {a,b} with time < t was an access to a, or if none, then check initial order.
Define L(t) = max{ s < t : s in T_a ∪ T_b }. If L(t) is from T_a, then before time t, a is above b (since a's last access more recent). If L(t) is from T_b, then b is above a (so a not above b). If no such s (i.e., neither a nor b accessed before t), then relative order is determined by initial order: a above b if initially a is above b, else not.
Thus, the count of times a is above b at access to b = number of t in T_b such that: either (there exists s < t in T_a ∪ T_b and the latest is in T_a) OR (no prior access and initial order has a above b).
Similarly for accesses to a.
So total contribution = w_a * C_{a→b} + w_b * C_{b→a}, where C_{a→b} is number of accesses to b where a is above b just before that access.
Now note that for a given pair, the contributions depend on initial order only in the case when the first access among the two is to b? Actually, if the first access among the two is to b, then before that access, neither has been accessed, so initial order matters: if initially a above b, then at that first b access, a is above b, so we count w_a. If initially b above a, then at that first b access, a is not above b, so we don't count. Similarly for first a access.
After the first access of either, the relative order is determined solely by which was accessed last. So initial order only matters for the first access of the pair (the one that occurs first in time). Also possibly if there are no accesses to a or b? But both appear in sequence? Not necessarily: some books may never be accessed; but then they never contribute as accessed, but they may be lifted when other books are accessed. For a pair where one book is never accessed, say b never accessed, a accessed multiple times. Then for accesses to a, we need to know if b is above a before each access. Since b never accessed, its "last access" is never. So for any access to a, the last access among {a,b} before that time is either from a (if prior a) or none. If none (first access to a), then initial order matters: if b above a initially, then at first a access, b is above a, so we add w_b. After first a access, a becomes most recent, so b is below a (since a is more recent) => for subsequent accesses to a, b is below a, so no contribution. So for a never-accessed book, its weight may contribute to cost only at the first access to any other book that is accessed? Actually, consider pair (b never accessed, a accessed). At any access to a after the first, b is below a, so no contribution. At the first access to a, contribution from b if b initially above a. Also b might be above a at accesses to other books? If we access c, and b is above c? That is covered by pair (b,c). So each pair's contribution is limited.
Thus, for each unordered pair {i,j}, the total contribution from their interaction depends on initial order only for the first access among the two (the earlier one). Because after that, the order is determined by which was accessed later.
Let's try to derive expression.
Define for each pair (i,j) with i≠j. Let the request sequence be considered. We can compute times of accesses to i and j. Let the times be sorted. Consider the first time among accesses to either i or j. Suppose the first access is to i at time t0. Then just before that access, neither i nor j has been accessed before, so relative order is initial. So if initially j is above i, then at this access to i, we add w_j (since j above i). After this access, i becomes most recent, so now i is above j. Then consider subsequent accesses: for any later access to i, the last access among {i,j} before it will be the previous i (or possibly a j, but if j is accessed later, that may flip). Similarly for first access to j if j is accessed later.
We need to compute total contributions across both directions.
Let’s denote:
Let sequence of events for pair (i,j) be the accesses to i and j in chronological order. This forms a sequence of letters (i and j). The state before the first event is determined by initial order: either i above j or j above i.
After each event (say event on x), the contribution from the other book's weight to this event depends on the state before the event. Then after event, state becomes x above the other (i.e., the event book becomes top).
Thus, the process for the pair is a deterministic finite state with two possible states: i-above-j or j-above-i. The transition: when we have an event on x, if state is "other above x" then we incur cost w_other; else incur 0. Then after event, state becomes x-above-other (i.e., the event book on top). So essentially, it's like: at each occurrence in the sequence, we pay cost of the weight of the other if the other is currently on top, then set that book on top.
This is similar to a "bit-flip" cost model. For a given sequence of events (say S over {i,j}), and initial state s0 ∈ {i,j} indicating which is above, we can compute total cost for that pair as sum over events: for event x, if current state has other (not x) on top, pay w_other; then set state to x.
We can compute this cost easily given the sequence S and initial state. But we have many pairs, and the events for different pairs are interleaved with other books, but the events for a pair are independent of others? Actually the state of each pair evolves only when either of the two books is accessed, independent of others. So we can compute contributions per pair separately. This is a crucial simplification: The total cost is sum over all unordered pairs of the cost incurred from interactions between that pair, because each lift operation's cost is sum of weights of books above the accessed one, which can be decomposed as sum over each other book's weight if that other book is above. So yes, total cost = Σ_{i<j} (w_i * (number of times i is above j when j is accessed) + w_j * (number of times j is above i when i is accessed)). That's exactly sum over unordered pairs of pairwise contributions.
And the evolution of the relative order of i and j depends only on the sequence of accesses to i and j. So we can compute for each pair (i,j) separately, given the request sequence b_1..b_m. Then we need to choose the initial order for each pair, i.e., for each unordered pair we need to decide which one is initially above the other, but note that these decisions are not independent because the initial order must be consistent across all books (a total ordering). So we have a global initial permutation; that imposes for each pair (i,j) a binary relation: either i above j or j above i, consistent with a linear order.
Thus, we have a problem: We have n items. For each unordered pair (i,j), we have a cost function that depends on which of i or j is initially above the other. Specifically, given the request sequence, we can precompute two values: cost_{i,j}^{iAbove} = total contribution from pair (i,j) if initially i is above j; and cost_{i,j}^{jAbove} = total contribution if initially j is above i. Actually, careful: The total contribution from the pair (i,j) to total cost includes both directions: w_i * (times i above j at accesses to j) + w_j * (times j above i at accesses to i). This total depends on initial order. So we can compute for each unordered pair the cost when i is initially above j, denote C_{i>j}, and when j is initially above i, denote C_{j>i}. But note that these costs are not necessarily symmetric.
We can compute these costs by simulating the pair's interaction given the request sequence and the initial order. Since n up to 500, m up to 1000, there are O(n^2) pairs (up to ~125k) and for each we can simulate O(m) to compute costs? That would be 125k1000=125 million, which might be okay in C++ (0.125e9) but borderline. But we can do smarter: For each pair, we only need to process accesses that involve either i or j. The number of such accesses per pair is at most the frequency of i plus frequency of j, which across all pairs could sum to O(n * m) if we sum over all pairs? Actually sum_{i<j} (freq_i + freq_j) = (n-1) * sum_i freq_i = (n-1)m = up to 5001000 = 500k, times constant. So we can compute efficiently by iterating over requests once and updating states for all pairs? But state for each pair is binary and we need to know current state when processing each request to update counts? We want to compute the total cost contributions for each possible initial ordering. However, we can compute the cost for each pair independently by scanning the request sequence and simulating the state machine for that pair. Since total accesses per pair sum over pairs is O(nm), we can compute both C_{i>j} and C_{j>i} simultaneously maybe.
But even 125k pairs * average frequency? n=500, m=1000, average frequency per book = m/n=2. So sum_{i<j} (freq_i+freq_j) = (n-1)m = 4991000=499k. So we can simulate each pair with O(freq_i+freq_j) time, total O(n*m) = 500k, which is fine. So we can compute the two possible costs per pair easily.
Now we have a set of items and for each unordered pair (i,j), we have two costs depending on relative order. We need to choose a linear order (a permutation) that minimizes sum over pairs of the cost corresponding to the orientation in that order. This is reminiscent of a minimum linear arrangement or weighted feedback arc set? Because we have an objective that for each pair we pay cost based on which direction we choose. This is exactly a problem of finding a linear order that minimizes sum of weights for directed edges? Actually, it's like we have a complete directed graph with two possible weights for each direction? But we have only two costs, not necessarily related.
Let's define for each ordered pair (i,j) (i != j), we could think of cost if i is before j (i.e., i above j) is something? But careful: "i above j" means i is physically higher in stack, so when we consider the stack order from top to bottom, i appears before j. That is, i precedes j in the list (top is first). So if we define order as a permutation π where π_1 is top, π_n bottom, then for each pair i, j, we have a relation: i above j iff π^{-1}(i) < π^{-1}(j) (i appears earlier). So we need to assign positions.
For each unordered pair {i,j}, the cost we incur is either C_{i>j} (if i above j) or C_{j>i} (if j above i). So we need to choose orientation for each pair consistent with a total order.
This is equivalent to: we have a tournament? Actually, we can view each unordered pair as having two possible contributions. Choosing an order essentially decides for each pair which direction is taken. And the constraints of transitivity (order must be linear) make the problem potentially hard. This is like the minimum linear ordering problem or weighted feedback arc set where we have a directed graph with weights for each direction and we want to find an ordering that minimizes sum of weights of edges that go backward (or forward) depending on definition.
Specifically, suppose we define for each ordered pair (i,j) a weight w_{i→j} that we pay if i is before j (i above j). Then total cost for order π is sum_{i before j} w_{i→j}. That's a classic problem: given a complete directed graph with edge weights (maybe zero for missing), find a linear order minimizing sum of weights of edges that go from earlier to later? But that's easy: if we can choose any orientation, we would just for each pair choose the orientation with lower cost, but transitivity might force some choices to be consistent. For example, if we have three items, and pairwise costs: A above B cost 0, B above A cost 10; A above C cost 0, C above A cost 10; B above C cost 0, C above B cost 10. Then the optimal consistent order would be A before B before C, cost 0+0+0=0, which is fine. But if we have conflicting low costs: A above B = 0, B above A = 100; B above C = 0, C above B = 100; but A above C = 100, C above A = 0. Then what is the best order? Options: A before B before C: costs: A before B =0, A before C=100 (since A before C pays w_{A→C}=100), B before C=0 => total 100. B before A before C: B before A =100, B before C=0, A before C=100 => total 200. A before C before B: A before C=100, A before B=0, C before B=100 => 200. C before A before B: C before A=0, C before B=100, A before B=0 => 100. C before B before A: C before B=100, C before A=0, B before A=100 => 200. B before C before A: B before C=0, B before A=100, C before A=0 => 100. So min=100. But the pairwise lower costs are: for (A,B) choose A above B (0), (B,C) choose B above C (0), (A,C) choose C above A (0). These three choices are cyclic (A>B, B>C, C>A) which is inconsistent with a total order. So we need to break cycle by incurring higher cost on at least one edge. This is exactly a minimum feedback arc set problem on a tournament? But here we have two weights per pair (not necessarily complementary). The problem of finding a linear order minimizing sum of weights of edges that go forward (or backward) is known as the Linear Ordering Problem (LOP), which is NP-hard in general. However, here n is only 500, which is large for NP-hard, so there must be special structure.
Thus, the pairwise costs likely have a special form that makes the problem solvable by a greedy approach, maybe by sorting by some criteria.
Let's derive the expressions for C_{i>j} and C_{j>i} in terms of the request sequence and weights. Perhaps they satisfy a property like C_{i>j} - C_{j>i} = something like (w_i - w_j) * something, leading to consistent ordering by weight? Or maybe the costs are such that the optimal order is by some function of frequencies and weights? We need to compute these costs and see pattern.
We'll analyze the pairwise cost dynamics in depth.
Consider two books i and j with weights w_i, w_j. We have request sequence with occurrences of i and j.
Let the times when i is requested be t_i1 < t_i2 < ... < t_i_{a} (a = freq_i). Similarly for j: t_j1 < t_j2 < ... < t_j_{b} (b = freq_j).
We'll consider the merged timeline of these events. The interaction cost for this pair can be computed by simulating state machine.
Define state: which book is on top initially? Two possibilities: i above j or j above i.
We'll derive formulas for total cost contribution from this pair, in terms of these events.
Let's denote S = sequence of events (i/j) in order. For each event, we pay cost if the other is on top; then set the event book on top.
We can compute total cost directly: it's like each time we have an event, if the current top is not the event book, we pay weight of the current top, and then swap top to event book.
This is reminiscent of the cost of serving a sequence with a two-element cache using move-to-front: cost of accessing an element is 1 if the other is at front, else 0. But here cost weight can differ.
Alternatively, we can think of it as: initially, we have some ordering. After processing the sequence, what is total cost? Perhaps it equals something like: for each consecutive pair of accesses, if they are different, we add weight of the one that was accessed earlier? Actually, let's simulate small sequences.
We'll derive expression:
Let the sequence be e_1, e_2, ..., e_k where each e ∈ {i,j}. Let initial state s0 ∈ {i,j} indicating which is on top.
Define cost = sum_{t=1..k} ( if e_t != current_top then w_{current_top} else 0 ); then set current_top = e_t.
Now, what is total cost? We can compute by looking at each transition. The state changes only when e_t is different from current_top. If e_t == current_top, cost 0 and state unchanged. If e_t != current_top, we pay w_{current_top} and state becomes e_t.
Thus, cost is sum of weights of elements that are "evicted" from top when a different element is accessed.
Now, note that the state evolves deterministically. Suppose we list the times when the accessed element changes from one to the other. In a sequence, the cost occurs at each time we have a switch (from i to j or j to i) and the cost is the weight of the element we switch from.
But if there are consecutive same accesses, no cost.
Thus, total cost = sum over each occurrence in the merged sequence where e_t != e_{t-1}? Not exactly, because if there is a switch but the top was already the other? Actually, after a switch, top becomes the new element. The next time we access the other, we will pay cost (weight of current top). So essentially, each time we have a change in the type of event compared to the previous event in the merged sequence? Let's test:
Sequence: i, j, i, i, j. Starting state s0.
Case s0 = i.
t=1: e=i, current_top=i -> cost 0, top remains i. t=2: e=j, current_top=i -> cost w_i, top becomes j. t=3: e=i, current_top=j -> cost w_j, top becomes i. t=4: e=i, current_top=i -> cost 0. t=5: e=j, current_top=i -> cost w_i, top becomes j. Total = w_i + w_j + w_i = 2w_i + w_j.
Now, looking at changes: events: i->j at t2, j->i at t3, i->j at t5. At each change we pay weight of the element we are leaving (the one that was top before). So total cost = sum over each change (from x to y) of w_x. This holds regardless of initial state? If initial state is j, then:
s0=j. t1: i, current_top=j -> cost w_j, top becomes i. t2: j, current_top=i -> cost w_i, top becomes j. t3: i, current_top=j -> cost w_j, top becomes i. t4: i, current_top=i -> cost 0. t5: j, current_top=i -> cost w_i, top becomes j. Total = w_j + w_i + w_j + w_i = 2w_i + 2w_j? Wait compute: w_j + w_i + w_j + w_i = 2w_i+2w_j. But earlier with s0=i we got 2w_i + w_j. So difference. So the total cost depends on initial state.
But if we look at changes: the sequence of transitions: from s0 to first event may cause a cost if s0 != e1. So there is an implicit change from initial top to first event if different. So we can treat initial top as a preceding state.
Thus, total cost = sum over each time the accessed book differs from the previous "top" (which is either initial top or previous accessed book). That is, cost incurred at time t if e_t != e_{t-1}? Not exactly because if we have e_t = i, e_{t-1}=j, but after t-1, top becomes j? Actually after each access, top becomes the accessed book. So after t-1, top = e_{t-1}. Therefore, at time t, we compare e_t with e_{t-1}. If they are different, then cost = w_{e_{t-1}} (the previous book's weight). If they are the same, cost = 0. Additionally, at time t=1, we compare e_1 with initial top s0; if different, cost = w_{s0}. So total cost = (if e_1 != s0 then w_{s0}) + sum_{t=2..k} (if e_t != e_{t-1} then w_{e_{t-1}}).
Thus, the total cost for the pair (i,j) can be expressed as:
cost = (if e_1 != s0) * w_{s0} + sum_{t=2..k} (if e_t != e_{t-1}) * w_{e_{t-1}}.
Now e_t are either i or j.
Thus, cost depends on s0 and the sequence of events.
We can rewrite it as: For each occurrence of an access, we add the weight of the previously accessed book (or initial top) if it is different from the current book. This is reminiscent of counting transitions.
Now, we can compute the cost for both possible s0: s0 = i or s0 = j.
Let the merged event sequence be S of length k = freq_i + freq_j. We can compute:
Let C_i = total cost if initially i on top; C_j = total cost if initially j on top.
We need to compute both.
We can derive formulas in terms of the sequence.
Define the sequence S[1..k] ∈ {i,j}. Define transitions: For t from 2 to k, if S[t] != S[t-1], we have a transition from S[t-1] to S[t]. Also initial transition if S[1] != s0.
Now, cost contributions: For a transition from x to y, we add w_x.
Thus, total cost = sum over transitions (including initial) of weight of the source.
Now, if s0 = i, then we have an initial source i if S[1] != i. If s0 = j, similar.
Now, note that transitions internal to the sequence are independent of s0. Only the initial transition may differ.
Thus, C_i = T + (if S[1] != i) * w_i, where T = sum_{t=2..k} (if S[t] != S[t-1]) * w_{S[t-1]}. Similarly, C_j = T + (if S[1] != j) * w_j.
Thus, the difference C_i - C_j = (if S[1] != i)*w_i - (if S[1] != j)*w_j.
If S[1] = i, then C_i = T (since no initial cost), C_j = T + w_j (since S[1] != j, so add w_j). So difference = -w_j. If S[1] = j, then C_i = T + w_i, C_j = T, difference = +w_i. If S[1] is something? Only i or j.
Thus, C_i - C_j = if first event is i: -w_j if first event is j: +w_i
Alternatively, we can write C_i = T + (S[1]==j ? w_i : 0) , C_j = T + (S[1]==i ? w_j : 0).
So essentially, the only difference between the two initial orders is the cost of an initial transition if the first event is the other book. And the internal transitions cost T is independent of initial order.
Thus, the total cost for the pair (i,j) given initial order (i above j) is: cost_{i>j} = T + (if first event = j then w_i else 0) cost_{j>i} = T + (if first event = i then w_j else 0)
But careful: We defined s0 = i above j means initially i is on top, so state is i. Yes.
Now, T is the sum over internal transitions: for each change from x to y, add w_x.
We can compute T easily from the merged sequence. Also note that T does not depend on initial order.
Thus, the decision for each pair is: which initial ordering yields lower cost? That is determined by comparing the extra cost: either we add w_i if first event is j, or we add w_j if first event is i. So we would prefer initial order i above j if (if first event=j) w_i >? Actually we want cost_{i>j} <= cost_{j>i}? cost_{i>j} - cost_{j>i} = (first=j? w_i : 0) - (first=i? w_j : 0). So:
- If first event = i, then cost_{i>j} = T, cost_{j>i} = T + w_j, so i above j is better (lower) by w_j.
- If first event = j, then cost_{i>j} = T + w_i, cost_{j>i} = T, so j above i is better by w_i.
- If first event is? Always i or j.
Thus, the optimal orientation for the pair is: put the book that is requested first among the two on top (i.e., initially above the other). Because if i is requested first, then having i above j avoids paying w_j at the initial step (or more precisely, if i first, then initial order with i on top gives no initial cost, while j on top would incur cost w_j). So optimal is to have the first-requested book on top. This seems like a local rule: for each pair, to minimize cost for that pair, the initially higher book should be the one that appears first in the request sequence among the two.
But wait, there is also T, which is the same for both orientations. So indeed the pairwise decision is independent of T and simply: initial order should have the book that occurs earlier in the request sequence (overall) placed above the other. But is that always optimal? Let's test with earlier example: i and j, first request is i. Then optimal is i above j. That yields lower cost by w_j. So if w_j is positive, yes. So orientation depends on which book is requested first. If both appear? They have a first occurrence. So the optimal orientation is determined solely by the order of first appearances of the two books in the overall request sequence.
But is that always consistent with a total order? Let's think: The rule "book A should be above book B if its first occurrence is earlier than B's first occurrence" defines a strict total order based on first occurrence times? Since first occurrence times are distinct? Not necessarily; two books might have their first occurrence at the same time? They cannot because the request sequence is a list; each position is one book. However, two different books can first appear at different times. So we can assign each book a value f(i) = the first day (index) when book i is requested. Then the rule says: for any pair (i,j), if f(i) < f(j), then i should be above j to minimize cost for that pair. This yields a total order: sort books by increasing f(i) (i.e., earlier first request appears higher/top). This order is a linear order (since f(i) are distinct? Could two books have same f? Only if the same book? No, first occurrence of distinct books are at different times because the sequence entries are single books; the first time each appears might be same index? Impossible: the same index cannot be two different books. So f(i) are distinct. So the ordering by f(i) is a total order. Moreover, it is consistent: if f(i) < f(j), then i should be above j; and if f(j) < f(i), j above i. So the orientation decisions are globally consistent; there is no cycle because it's based on a total order of first occurrences.
Wait, is it really that simple? Let's verify with more complex scenario: What about pairs where one book never appears? Then f(i) is undefined. But can a book never be requested? Possibly yes, because m can be less than n? Actually m can be up to 1000, n up to 500, it's possible some books are never requested. The problem statement: "He decided to read books for m days. In the j-th day, he will read the book numbered bj." It doesn't guarantee that all books appear. So some books may never be read. For such books, they are never accessed. How does that affect pair costs? For a pair where one book never requested, let's analyze.
Consider books i (never requested) and j (requested at least once). For this pair, what are the costs? We need to compute contributions from this pair to total cost. Let's simulate.
We have events only for j (since i never requested). Sequence S only contains j's (say b times). For pair (i,j), we have events: all j's. The merged sequence is just j repeated. The initial state: either i above j or j above i.
Now compute costs using our transition formula.
If initial state: i above j (i on top). Then first event: j. Since s0=i and e1=j (different), cost += w_i. Then top becomes j. Subsequent events: all j's, same as top, so no further cost. Total cost = w_i.
If initial state: j above i. Then first event: j, same as top, cost 0. Top remains j. So total cost = 0.
Thus, for a never-requested i and requested j, the cost is w_i if i is above j, else 0. So to minimize, we would want j above i (i.e., j on top of i) to avoid paying w_i. That means we want the requested book to be above the never-requested book. That aligns with the "first occurrence" rule? For never-requested i, f(i) is infinite (or not defined). For j, f(j) is finite. So sorting by f (with infinite last) would put requested books before never-requested ones. So consistent.
Now what about a pair where both are never requested? Then there are no events. The cost contribution from the pair is always zero regardless of order? Let's check: if neither is ever accessed, then they never affect cost because they are never the accessed book, and when other books are accessed, this pair may contribute if one is above the other? Actually, the contribution from this pair to total cost only occurs when one of them is accessed. Since neither is accessed, the pair never contributes to any lift cost because we never access either. Wait, but could they affect cost when other books are accessed? The contribution of pair (i,j) to total cost is only when i is accessed (then j's weight may be added if j above i) or when j is accessed (then i's weight may be added). If neither is accessed, there is no direct contribution. However, does their relative order affect costs of accesses to other books? No, because the cost when accessing a third book k includes sum of weights of all books above k, which includes i and j if they are above k. So the pair (i,j) themselves interact with other books. Our decomposition into pairwise contributions between i and j only captures contributions when i or j is accessed. But the total cost sum over days of weights of books above the accessed book includes contributions from all books, not just the pair. So we must consider contributions from all pairs (i, j) where i is the accessed book and j is above i. That's exactly sum over accessed books x of sum over y != x, w_y * [y above x]. This can be written as sum over unordered pairs {i,j} of (w_j * [j above i when i accessed] + w_i * [i above j when j accessed]). That's what we used. So it includes only terms where at least one of the two is accessed. So for a pair where neither is accessed, there is no term; thus the order between them does not affect total cost directly. However, their relative order could affect the cost of accessing other books? Actually, consider a third book k accessed. The cost includes sum over all books above k, including i and j. So i and j appear in the sum for k if they are above k. That contribution is captured by pairs (i,k) and (j,k). So the pairwise decomposition we used is per pair (i,j) only for interactions when i or j is accessed. So the interaction between i and j themselves when neither is accessed is not counted, but their positions relative to each other can affect whether they are above k? However, the condition "i above k" is independent of j's position relative to i? Actually, the ordering is linear; i above k is a binary relation. The contribution from i to cost of accessing k is w_i if i above k. That is independent of where j is. So the pairwise contributions we considered (i,j) only involve i and j. The contributions involving i and k are separate. So the decision for ordering i and j does not affect cost involving k except possibly indirectly because changing order of i and j might affect the relative ordering of i and k? Not if we keep the order of i relative to k fixed. But we are looking for a global ordering; the ordering between i and j is part of it, but the cost contributed by i to k depends on whether i is above k, which is a separate pairwise decision. So overall, the total cost can be expressed as sum over all ordered pairs (i,j) (i != j) of w_i * (number of times j is accessed while i is above j). But careful: That's sum over all i of w_i times (total number of accesses to books j where i is above j at that time). That's equivalent to sum over unordered pairs but includes both directions. So each ordered pair (i,j) where i != j contributes w_i times some count that depends on the order of i and j and the request sequence.
Thus, our pairwise decomposition is valid: total cost = Σ_{i≠j} w_i * c_{i,j} where c_{i,j} is number of accesses to j while i is above j. This sum double counts each unordered pair? Actually it's ordered: for each unordered {i,j}, we have term w_i * c_{i,j} + w_j * c_{j,i}. So it's sum over unordered pairs of something. But this decomposition suggests that the cost contributed by a specific pair (i,j) only depends on the relative order of i and j and the request sequence for i and j. However, is there any interaction with a third book that affects when i is above j? The relative order of i and j depends only on accesses to i and j, as argued earlier, because the MTF rule for two items is independent of others: when a third book k is accessed, it moves to top, but does that affect whether i is above j? Let's test: Suppose we have three books i, j, k. Initially order: i, j, k (top to bottom). State: i above j, j above k. Access k: lift books above k (i and j), then move k to top. New order: k, i, j. So after accessing k, the relative order of i and j remains i above j (since they were lifted together and put down without changing order). So accessing a third book does not change the relative order between i and j; it only moves that third book to top, but i and j keep their relative order. More generally, accessing any book other than i or j does not affect the relative order of i and j. Because when we access a book x that is not i or j, we lift all books above x. If i and j are both above x, they are both lifted and then placed back in same order. If one is above x and the other below x, then the relative order might change? Let's examine: Suppose i above j initially, and we access a book x that is between i and j? Actually, ordering from top: i, ..., x, ..., j. When accessing x, we lift all books above x (which includes i but not j because j is below x). So we lift i, remove x, then put down i (keeping order), then put x on top. New order: x, i, ..., j? Wait we need to reconstruct: Initially: (top) i ... x ... j (bottom). To access x: lift all books above x (i and any between i and x). Remove x. Put down lifted books (i and those) in same order. Then put x on top. So new order: x, (i, ...), then the books below x (including j) remain in same order. So i ends up still above j? i is placed after x, and j remains below the original position, but relative order between i and j: i is above j originally, and after process, i is still above j? Let's list explicitly: top: i, A (some books), x, B, j. After access: lift [i, A], remove x, put down [i, A], then put x on top. So new stack: x, i, A, B, j. So i is above j? Yes, i is above B and j. So still i above j. If x was between i and j, and we access x, i remains above j because i is placed back above the books that were below x, which include j. What if x is below both i and j? Then we lift all above x (including i and j). Both are lifted, removed? Actually if x is below both, then both i and j are above x. Then lifting them, remove x, put them down, then x on top. So new order: x, i, j (keeping their relative order). So again i and j relative order unchanged. If x is above both? But then x is above i and j, but we access x, which is top? Actually if x is above both, then i and j are below x. Then we access x which is top, we lift books above x (none), remove x, put down nothing, put x on top. So order becomes x, then original stack minus x? Actually removing top x and putting it back on top leaves order unchanged? Let's see: stack top x, then i, then j. To read x: lift all above x (none), push x out (so remove x), put down lifted (none), put x on top. So final stack: x, i, j (same). So relative order unchanged.
Thus, the relative order of two books i and j only changes when either i or j is accessed. This is a key property of MTF: accesses to other items do not affect the relative order of i and j. Because when you access a third book, you move it to the top, but the relative order of the other two remains the same as they are either both lifted (if they were above the accessed book) or both stay below (if below) or one lifted and one stays? Actually, if one is above the accessed book and the other below, then accessing the third book will lift the one above but not the one below. After the process, the lifted books are placed above the books