340A - The Wall

You are given a range [A, B]. You're asked to compute fast how many numbers in the range are divisible by both x and y. I'll present here an O(log(max(x, y)) solution. We made tests low so other not optimal solutions to pass as well. The solution refers to the original problem, where x, y ≤ 10⁹.

Firstly, we can simplify the problem. Suppose we can calculate how many numbers are divisible in range [1, X] by both x and y. Can this solve our task? The answer is yes. All numbers in range [1, B] divisible by both numbers should be counted, except the numbers lower than A (1, 2, ..., A — 1). But, as you can see, numbers lower than A divisible by both numbers are actually numbers from range [1, A — 1]. So the answer of our task is f(B) — f(A — 1), where f(X) is how many numbers from 1, 2, ..., X are divisible by both x and y.

For calculate in O(log(max(x, y)) the f(X) we need some math. If you don't know about it, please read firstly about least common multiple. Now, what will be the lowest number divisible by both x and y. The answer is least common multiple of x and y. Let's note it by M. The sequence of the numbers divisible by both x and y is M, 2 * M, 3 * M and so on. As a proof, suppose a number z is divisible by both x and y, but it is not in the above sequence. If a number is divisible by both x and y, it will be divisible by M also. If a number is divisible by M, it will be in the above sequence. Hence, the only way a number to be divisible by both x and y is to be in sequence M, 2 * M, 3 * M, ...

The f(X) calculation reduces to finding the number of numbers from sequence M, 2 * M, 3 * M, ... lower or equal than X. It's obvious that if a number h * M is greater than X, so will be (h + 1) * M, (h + 2) * M and so on. We actually need to find the greatest integer number h such as h * M ≤ X. The numbers we're looking for will be 1 * M, 2 * M, ..., h * M (so their count will be h). The number h is actually [X / M], where [number] denotes the integer part of [number]. Take some examples on paper, you'll see why it's true.

The only thing not discussed is how to calculate the number M given 2 number x and y. You can use this formula M = x * y / gcd(x, y). For calculate gcd(x, y) you can use Euclid's algorithm. Its complexity is O(log(max(x, y)), so this is the running time for the entire algorithm.

Official solution: 4383403

340B - Maximal Area Quadrilateral

I want to apologize for not estimating the real difficulty of this task. It turns out that it was more complicated than we thought it might be. Let's start explanation.

Before reading this, you need to know what is signed area of a triangle (also called cross product or ccw function). Without it, this explanation will make no sense.

The first thing we note is that a quadrilateral self intersecting won't have maximum area. I'll show you this by an image made by my "talents" in Paint :) As you can see, if a quadrilateral self intersects, it can be transformed into one with greater area.

Each quadrilateral has 2 diagonals: connecting 1st and 3rd point and connecting 2nd and 4th point. A diagonal divides a plane into 2 subplanes. Suppose diagonal is AB. A point X can be in one of those two subplanes: that making cross product positive and that making cross product negative. A point is in "positive" subplane if ccw(X, A, B) > 0 and in "negative" subplane ccw(X, A, B) < 0. Note that according to the constraints of the task, ccw(X, A, B) will never be 0.

Let's make now the key observation of the task. We have a quadrilateral. Suppose AB is one of diagonals and C and D the other points from quadrilateral different by A and B. If the current quadrilateral could have maximal area, then one of points from C and D needs to be in "positive subplane" of AB and the other one in "negative subplane". What would happen if C and D will be in the same subplane of AB? The quadrilateral will self intersect. If it will self intersect, it won't have maximal area. "A picture is worth a thousand words" — this couldn't fit better in this case :) Note that the quadrilateral from the below image is A-C-B-D-A.

Out task reduces to fix a diagonal (this taking O(N ^ 2) time) and then choose one point from the positive and the negative subplane of the diagonal. I'll say here how to choose the point from the positive subplane. That from negative subplane can be chosen identically. The diagonal and 3rd point chosen form a triangle. As we want quadrilateral to have maximal area, we need to choose 3rd point such as triangle makes the maximal area. As the positive and negative subplanes are disjoint, the choosing 3rd point from each of them can be made independently. Hence we get O(N ^ 3) complexity. A tricky case is when you choose a diagonal but one of the subplanes is empty. In this case you have to disregard the diagonal and move to the next one.

Official solution: 4383413

340C - Tourist Problem

Despite this is a math task, the only math formula we'll use is that number of permutations with n elements is n!. From this one, we can deduce the whole task.

The average formula is sum_of_all_routes / number_of_routes. As each route is a permutation with n elements, number_of_routes is n!. Next suppose you have a permutation of a: p1, p2, …, pn. The sum for it will be p1 + |p2 – p1| + … + |pn – pn-1|. The sum of routes will be the sum for each possible permutation.

We can calculate sum_of_all routes in two steps: first time we calculate sums like “p1” and then we calculate sums like “|p2 – p1| + … + |pn – pn-1|” for every existing permutation.

First step Each element of a₁, a₂, …, a_n can appear on the first position on the routes and needs to be added as much as it appears. Suppose I fixed an element X for the first position. I can fill positions 2, 3, .., n – 1 in (n – 1)! ways. Why? It is equivalent to permuting n – 1 elements (all elements except X). So sum_of_all = a₁ * (n – 1)! + a₂ * (n – 1)! + … * a_n * (n – 1)! = (n – 1)! * (a₁ + a₂ + … + a_n).

Second step For each permutation, for each position j between 1 and n – 1 we need to compute |p_j — p(j + 1)|. Similarly to first step, we observe that only elements from a can appear on consecutive positions. We fix 2 indices i and j. We’re interested in how many permutations do a_i appear before a_j. We fix k such as on a permutation p, a_i appears on position k and a_j appears on a position k + 1. In how many ways can we fix this? n – 1 ways (1, 2, …, n – 1). What’s left? A sequence of (n – 2) elements which can be permuted independently. So the sum of second step is |a_i - a_j| * (n – 1) * (n – 2)!, for each i != j. If I note (a₁ + a₂ + … + a_n) by S1 and |a_i - a_j| for each i != j by S2, the answer is (N – 1)! * S1 + (N – 1)! * S2 / N!. By a simplification, the answer is (S1 + S2) / N.

The only problem remained is how to calculate S2. Simple iteration won’t enter in time limit. Let’s think different. For each element, I need to make sum of differences between it and all smaller elements in the array a. As well, I need to make sum of all different between bigger elements than it and it. I’ll focus on the first part. I sort increasing array a. Suppose I’m at position i. I know that (i – 1) elements are smaller than a_i. The difference is simply (i — 1) * a_i — sum_of_elements_before_position_i. Sum of elements before position i can be computed when iterating i. Let’s call the obtained sum Sleft. I need to calculate now sum of all differences between an element and bigger elements than it. This sum is equal to Sleft. As a proof, for an element a_i, calculating the difference a_j — a_i when a_j > a_i is equivalent to calculating differences between a_j and a smaller element of it (in this case a_i). That’s why Sleft = Sright.

As a conclusion, the answer is (S1 + 2 * Sleft) / N. For make fraction irreducible, you can use Euclid's algorithm. The complexity of the presented algorithm is O(N * logN), necessary due of sorting. Sorting can be implemented by count sort as well, having a complexity of O(maximalValue), but this is not necessary.

Official solution: 4383420

340D - Bubble Sort Graph

A good way to approach this problem is to notice that you can't build the graph. In worst case, the graph will be built in O(N²) complexity, which will time out. Also, notice that "maximal independent set" is a NP-Hard task, so even if you can build the graph you can't continue from there. So, the correct route to start is to think of graph's properties instead of building it. After sketching a little on the paper, you should find this property:

Lemma 1 Suppose we choose 2 indices i and j, such as i < j. We'll have an edge on the graph between vertices a_i and a_j if and only if a_i > a_j. We'll call that i and j form an inversion in the permutation.

Proof We assume we know the proof that bubble sort does sort correctly an array. To proof lemma 1, we need to show two things.

1. Every inversion will be swapped by bubble sort.
2. For each i < j when a_i < a_j, bubble sort will NOT swap this elements.

To proof 1, if bubble sort wouldn't swap an inversion, the sequence wouldn't be sorted. But we know that bubble sort always sorts a sequence, so all inversions will be swapped. Proofing 2 is trivial, just by looking at the code.

So far we've got how the graph G is constructed. Let's apply it in maximal independent set problem.

Lemma 2 A maximal independent set of graph G is a longest increasing sequence for permutation a.

Proof: Suppose we have a set of indices i1 < i2 < ... ik such as a_i1, a_i2, ..., a_ik form an independent set. Then, anyhow we'd choose d and e, there won't exist an edge between a_id and a_ie. According to proof 1, this only happens when a_id < a_ie. Hence, an independent set will be equivalent to an increasing sequence of permutation a. The maximal independent set is simply the maximal increasing sequence of permutation a.

The task reduces to find longest increasing sequence for permutation a. This is a classical problem which can be solved in O(N * logN). Here is an interesting discussion about how to do it.

340E - Iahub and Permutations

In this task, author's intended solution is an O(N ^ 2) dp. However, during testing Gerald fount a solution using principle of inclusion and exclusion. We've thought to keep both solutions. We're sorry if you say the problem was well-known, but for both me and the author of the task, it was first time we saw it.

Dynamic programming solution

After reading the sequence, we can find which elements are deleted. Suppose we have in a set D all deleted elements. I'll define from now on a "free position" a position which has -1 value, so it needs to be completed with a deleted element.

We observe that some elements from D can appear on all free positions of permutation without creating a fixed point. The other elements from D can appear in all free positions except one, that will create the fixed point. It's intuitive that those two "classes" don't influence in the same way the result, so they need to be treated separated.

So from here we can get the dp state. Let dp(n, k) = in how many ways can I fill (n + k) free positions, such as n elements from D can be placed anywhere in the free position and the other k elements can be placed in all free positions except one, which will create the fixed point. As we'll prove by the recurrences, we are not interested of the values from elements of D. Instead, we'll interested in their property: if they can(not) appear in all free positions.

If k = 0, the problem becomes straight-forward. The answer for dp(n, 0) will be n!, as each permutation of (n + 0) = n numbers is valid, because all numbers can appear on all free positions. We can also calculate dp(n, 1). This means we are not allowed to place an element in a position out of (n + 1) free positions. However, we can place it in the other n positions. From now we get n elements which can be placed anywhere in the n free positions left. Hence, dp(n, 1) = n! * n.

We want to calculate dp(n, k) now, k > 1. Our goal is to reduce the number k, until find something we know how to calculate. That is, when k becomes 0 or 1 problem is solved. Otherwise, we want to reduce the problem to a problem when k becomes 0 or 1. I have two cases. In a first case, I take a number from numbers which can be placed anywhere in order to reduce the numbers which can form fixed points. In the second case, I take a number from those which can form fixed points in order to make the same goal as in the first case. Let's analyze them.

Case 1. Suppose X is the first free position, such as in the set of k numbers there exist one which cannot be placed there (because it will make a fixed point). Obviously, this position exist, otherwise k = 0. Also obviously, this position will need to be completed with a term when having a solution. In this case, I complete position X with one of n numbers. This will make number equal to X from the k numbers set to become a number which can be placed anywhere. So I "loose" one number which can be placed anywhere, but I also "gain" one. As well, I loose one number which can form a fixed point.

Hence dp(n, k) += n * dp(n, k — 1).

Case 2. In this case position X will be completed with one number from the k numbers set. All numbers which can form fixed points can appear there, except number having value equal to X. So there are k — 1 of them. I choose an arbitrary number Y from those k — 1 to place on the position X. This time I "loose" two numbers which could form fixed points: X and Y. As well, I "gain" one number which can be placed anywhere: X.

Hence dp(n, k) += (k — 1) * dp(n + 1, k — 2).

TL;DR

dp[N][0]=N!

dp[N][1]=N*dp[N][0]

dp[N][K]=N*dp[N][K-1]+(K-1)*dp[N+1][K-2] for K>=2

This recurrences can be computed by classical dp or by memoization. I'll present DamianS's source, which used memoization. As you can see, it's very short and easy to implement. Link

Inclusion and exclusion principle

I'll present here an alternative to the dynamic programming solution. Let's calculate in tot the number of deleted numbers. Also, let's calculate in fixed the maximal number of fixed points a permutation can have. For calculate fixed, let's iterate with an index i each permutation position. We can have a fixed point on position i if element from position i was deleted (a_i = -1) and element i does not exist in sequence a. With other words, element i was deleted and now I want to add it back on position i to obtain maximal number of fixed points.

We iterate now an index i from fixed to 0. Let sol[i] = the number of possible permutations having exactly i fixed points. Obviously, sol[0] is the answer to our problem. Let's introduce a combination representing in how many ways I can choose k objects out of n. I have list of positions which can be transformed into fix points (they are fixed positions). I need to choose i of them. According to the above definition, I get sol[i] = . Next, I have to fill tot - i positions with remained elements. We'll consider for this moment valid each permutation of not used values. So, sol[i] = . Where is the problem to this formula?

The problem is that it's possible, when permuting (tot — i) remained elements to be added, one (or more) elements to form more (new) fixed points. But if somehow I can exclude (subtract) the wrong choices from sol[i], sol[i] will be calculated correctly. I iterate another index j from i + 1 to fixed. For each j, I'll calculate how many permutations I considered in sol[i] having i fixed points but actually they have j. I'll subtract from sol[i] this value calculated for each j. If I do this, obviously sol[i] will be calculated correctly.

Suppose we fixed a j. We know that exactly sol[j] permutations have j fixed points (as j > i, this value is calculated correctly). Suppose now I fix a permutation having j fixed points. For get the full result, I need to calculate for all sol[j] permutations. Happily, I can multiply result obtained for a single permutation with sol[j] and obtain the result for all permutations having j fixed points. So you have a permutation having j fixed points. The problem reduces to choosing i objects from a total of j. Why? Those i objects chosen are actually the positions considered in sol[i] to be ones having exactly i fixed points. But permutation has j fixed points. Quoting for above, "For each j, I'll calculate how many permutations I considered in sol[i] having i fixed points but actually they have j" . This is exactly what algorithm does.

To sum up in a "LaTeX" way,

We can compute binomial coefficients using Pascal's triangle. Using inclusion and exclusion principle, we get O(N²). Please note that there exist an O(N) solution for this task, using inclusion and exclusion principle, but it's not necessary to get AC. I'll upload Gerald's source here.

341D - Iahub and Xors

The motivation of the problem is that x ^ x = 0. x ^ x ^ x… ^ x (even times) = 0

Update per range, query per element

When dealing with complicated problems, it's sometimes a good idea to try solving easier versions of them. Suppose you can query only one element each time (x0 = x1, y0 = y1).

To update a submatrix (x0, y0, x1, y1), I’ll do following operations. A[x0][y0] ^= val. A[x0][y1 + 1] ^= val. A[x1 + 1][y0] ^= val. A[x1 + 1][y1 + 1] ^= val.

To query about an element (X, Y), that element’s value will be the xor sum of submatrix A(1, 1, X, Y). Let’s take an example. I have a 6x6 matrix and I want to xor all elements from submatrix (2, 2, 3, 4) with a value. The below image should be explanatory how the method works:

Next, by (1, 1, X, Y) I’ll denote xor sum for this submatrix.

“White” cells are not influenced by (2, 2, 3, 4) matrix, as matrix (1, 1, X, Y) with (X, Y) a white cell will never intersect it. “Red” cells are from the submatrix, the ones that need to be xor-ed. Note that for a red cell, (1, 1, X, Y) will contain the value we need to xor (as it will contain (2, 2)). Next, “blue” cells. For this ones (1, 1, X, Y) will contain the value we xor with, despite they shouldn’t have it. This is why both (2, 5) and (4, 2) will be xor-ed again by that value, to cancel the xor of (2, 2). Now it’s okay, every “blue” cell do not contain the xor value in their (1, 1, X, Y). Finally, the “green” cells. These ones are intersection between the 2 blue rectangles. This means, in their (1, 1, X, Y) the value we xor with appears 3 times (this means it is contained 1 time). For cancel this, we xor (4, 5) with the value. Now for every green cell (1, 1, X, Y) contains 4 equal values, which cancel each other.

You need a data structure do to the following 2 operations:

• Update an element (X, Y) (xor it with a value).
• Query about xor sum of (1, 1, X, Y).

Both operations can be supported by a Fenwick tree 2D. If you don't know this data structure, learn it and come back to this problem after you do this.

Coming back to our problem

Now, instead of finding an element, I want xor sum of a submatrix. You can note that xor sum of (x0, y0, x1, y1) is (1, 1, x1, y1) ^ (1, 1, x0 – 1, y1) ^ (1, 1, x1, y0 – 1) ^ (1, 1, x0 – 1, y0 – 1). This is a classical problem, the answer is (1, 1, x1, y1) from which I exclude what is not in the matrix: (1, 1, x0 – 1, y1) and (1, 1, x1, y0 – 1). Right now I excluded (1, 1, x0 – 1, y0 – 1) 2 times, so I need to add it one more time.

How to get the xor sum of submatrix (1, 1, X, Y)? In brute force approach, I’d take all elements (x, y) with 1 <= x <= X and 1 <= y <= Y and xor their values. Recall the definition of the previous problem, each element (x, y) is the xor sum of A(1, 1, x, y). So the answer is xor sum of all xor sums of A(1, 1, x, y), with 1 <= x <= X and 1 <= y <= Y.

We can rewrite that long xor sum. A number A[x][y] appears in exactly (X – x + 1) * (Y – y + 1) terms of xor sum. If (X – x + 1) * (Y – y + 1) is odd, then the value A[x][y] should be xor-ed to the final result exactly once. If (X — x + 1) * (Y — y + 1) is even, it should be ignored.

Below, you'll find 4 pictures. They are matrixes with X lines and Y columns. Each picture represents a case: (X odd, Y odd) (X even, Y even) (X even Y odd) (X odd Y even). Can you observe a nice pattern? Elements colored represent those for which (X – x + 1) * (Y – y + 1) is odd.

Yep, that's right! There are 4 cases, diving the matrix into 4 disjoint areas. When having a query of form (1, 1, X, Y) you only need specific elements sharing same parity with X and Y. This method works in O(4 * logN * logN) for each operation and is the indented solution. We keep 4 Fenwick trees 2D. We made tests such as solutions having complexity greater than O(4 * logN * logN) per operation to fail.

Here is our official solution: 4383473

341E - Candies Game

Key observation Suppose you have 3 boxes containing A, B, C candies (A, B, C all greater than 0). Then, there will be always possible to empty one of boxes using some moves.

Proof We can suppose that A <= B <= C. We need some moves such as the minimum from A, B, C will be zero. If we always keep the numbers in order A <= B <= C, it’s enough some moves such as A = 0. I’ll call this notation (A, B, C).

How can we prove that always exist such moves? We can use reductio ad absurdum to prove it. Let’s suppose, starting from (A, B, C) we can go to a state (A2, B2, C2). We suppose A2 (A2 > 0) is minimal from every state we can obtain. Since A2 is minimal number of coins that can be obtained and A2 is not zero, the statement is equivalent with we can’t empty one chest from configuration (A, B, C). Then, we can prove that from (A2, B2, C2) we can go to a state (A3, B3, C3), where A3 < A2. Obviously, this contradicts our assumption that A2 is minimal of every possible states. If A2 would be minimal, then there won’t be any series of moves to empty one chest. But A2 isn’t minimal, hence there always exist some moves to empty one chest.

Our algorithm so far:

void emptyOneBox(int A, int B, int C) {

if A is 0, then exit function.

Make some moves such as to find another state (A2, B2, C2) with A2 < A.

emptyOneBox (A2, B2, C2);

}

The only problem which needs to be proven now is: given a configuration (A, B, C) with A > 0, can we find another one (A2, B2, C2) such as A2 < A? The answer is always yes, below I’ll prove why.

Firstly, let’s imagine we want to constantly move candies into a box. It doesn't matter yet from where come the candies, what matters is candies arrive into the box. The box has initially X candies. After 1 move, it will have 2 * X candies. After 2 moves, it will have 2 * (2 * X) candies = 4 * X candies. Generally, after K moves, the box will contain 2^K * X candies.

We have A < B < C (if 2 numbers are equal, we can make a move and empty 1 box). If we divide B by A, we get from math that B = A * q + r. (obviously, always r < A). What if we can move exactly A * q candies from B to A? Then, our new state would be (r, B2, C2). We have now a number A2 = r, such as A2 < A.

How can we move exactly A * q coins? Let’s write q in base 2. Making that, q will be written as a sum of powers of 2. Suppose lim is the maximum number such as 2 ^ lim <= q. We get every number k from 0 to lim. For each k, I push into the first box (the box containing initially A candies) a certain number of candies. As proven before, I'll need to push (2 ^ k) * A candies. Let's take a look at the k-th bit from binary representation of q. If k-th bit is 1, B will be written as following: B = A * (2 ^ k + 2 ^ (other_power_1) + 2 ^ (other_power_2) + ...) + r. Hence, I'll be able to move A * (2 ^ k) candies from "B box" to "A box". Otherwise, I'll move from "C box" to "A box". It will be always possible to do this move, as C > B and I could do that move from B, too.

The proposed algorithm may look abstract, so let's take an example.

Suppose A = 3, B = 905 and C = 1024. Can we get less than 3 for this state?

B = 3 * 301 + 2. B = 3 * (100101101)2 + 2.

K = 0: we need to move (2^0) * 3 coins into A. 0th bit of q is 1, so we can move from B to A.

A = 6, B = 3 * (100101100)2 + 2 C = 1024

K = 1: we need to move (2 ^ 1) * 3 coins into A. Since 1th bit of q is already 0, we have to move from C.

A = 12, B = 3 * (100101100)2 + 2 C = 1018

K = 2: we need to move (2 ^ 2) * 3 coins into A. 2nd bit of q is 1, so we can move from B.

A = 24, B = 3 * (100101000)2 + 2 C = 1018

K = 3: we need to move (2 ^ 3) * 3 coins into A. 3nd bit of q is 1, so we can move from B.

A = 48, B = 3 * (100100000)2 + 2 C = 1018

K = 4. we need to move (2 ^ 4) * 3 coins into A. 4th bit of q is 0, we need to move from C.

A = 96, B = 3 * (100100000)2 + 2 C = 970

K = 5. we need to move (2 ^ 5) * 3 coins into A. 5th bit of q is 1, so we need to move from B.

A = 192, B = 3 * (100000000)2 + 2 C = 970

K = 6 we need to move (2 ^ 6) * 3 coins into A. We mve them from C.

A = 384 B = 3 * (100000000)2 + 2 C = 778

K = 7 we need to move (2 ^ 7) * 3 coins into A. We move them from C

A = 768 B = 3 * (100000000)2 + 2 C = 394

K=8 Finally, we can move our last 1 bit from B to A.

A = 1536 B = 3 * (000000000)2 + 2 C = 394

A = 1536 B = (3 * 0 + 2) C = 394

In the example, from (3, 905, 1024) we can arrive to (2, 394, 1536). Then, with same logic, we can go from (2, 394, 1536) to (0, X, Y), because 394 = 2 * 197 + 0.

This is how you could write emptyOneBox() procedure. The remained problem is straight-forward: if initially there are zero or one boxes having candies, the answer is "-1". Otherwise, until there are more than 2 boxes having candies, pick 3 boxes arbitrary and apply emptyOneBox().

Here is a source implementing the algorithm. 4383485

BONUS

Instead of a conclusion, I'll post here related problems to the ones used in the round. :) Please note that some of them might be more easier / complicated than level of difficulty used in the round. Feel free to think of them / ask help / discuss them in the comment section :)

Div2 A Suppose x, y, A, B ≤ 10⁹. Instead of being asked how many bricks are colored with both red and pink in range [A, B], you're asked how many bricks are colored with at least one color. After you solve this one, solve the same problem, but instead of having 2 persons painting, you have k persons (k ≤ 20). Solution by Enchom

Div2 B Given a very long list of special points, can you find quickly a convex special quadrilateral? Can you find very very quickly? :) Also, can you find maximal area of a special convex quadrilateral in time better than O(N⁴)? Solutions for first problem and second problem provided by Xellos and Enchom

Div2 D / Div1 B Suppose the reverse problem. You are given a bubble sort graph having N vertices and M edges. Find its independent maximal set. Can you achieve O(N²) to do this? Does a solution in O((N + M) + N * logN) exist? Solution by CountZero

Div2 E / Div1 C Find a solution running in liniar time. Solution (dynamic programming) by ivan100sic . Solution (inclusion exclusion principle) by eduardische

Div1 D Suppose the 3D version of this problem. You have a 3D matrix and you perform same QUERY/UPDATE operations, but using 6 parameters (a submatrix is defined now all elements a[i][j][k] for which x0 <= i <= x1, y0 <= j <= y1, z0 <= k <= z1). Can you get a solution using O(log³ * N) per query, having constant 8? But for d dimensions, does an O(2^d * (log^d)n) algorithm per query exist? :) Solution by Dwylkz.

Div1 E In our algorithm, we pick arbitrary 3 boxes. Can you find some heuristics of picking 3 boxes to reduce number of moves?