What's the most efficient way to make the sad students happy?

In most cases, you can make $$$2$$$ sad students happy in $$$1$$$ move.

Let $$$s$$$ be the number of sad students at the beginning. The answer is $$$\lceil \frac{s}{2} \rceil$$$.

In one move, you can make at most $$$2$$$ sad students happy (because you can change the position of at most two students), so you need at least $$$\lceil \frac{s}{2} \rceil$$$ moves.

In fact, you can make everyone happy in exactly $$$\lceil \frac{s}{2} \rceil$$$ moves:

• while there are at least $$$2$$$ sad students, you can swap them and both of them will be happy;
• if there is exactly $$$1$$$ sad student left, you can swap it with any other student.

Complexity: $$$O(n)$$$

What's the answer if $$$n$$$ is odd?

Try to generalize Hint 1.

What's the answer if $$$n$$$ is not a multiple of $$$3$$$?

If the answer is not a multiple of $$$x$$$, the answer is $$$ \lt x$$$. If the answer is a multiple of $$$1, \dots, x$$$, the answer is $$$\geq x$$$.

Suppose you find a valid interval $$$[l, r]$$$. Note that the interval $$$[l, r]$$$ contains at least one multiple of $$$x$$$ for each $$$1 \leq x \leq r-l+1$$$ (you can find it out by looking at the values in $$$[l, r]$$$ modulo $$$x$$$). Then, the interval $$$[1, r-l+1]$$$ is also valid and has the same length.

So, it's enough to check intervals with $$$l = 1$$$, i.e., find the smallest $$$x$$$ that does not divide $$$n$$$. The answer is $$$x-1$$$.

Complexity: $$$O(\log(\max n))$$$

There are several solutions to the easy version. In any case, how to get $$$a_i \leq a_{i+1}$$$?

For example, you can try making $$$a_{i+1}$$$ bigger using a positive element.

What to do if all the elements are negative?

If all the elements are negative, you can win in $$$n-1$$$ moves.

If there is a positive element, you can try to make $$$a_1 \leq a_2$$$, then $$$a_2 \leq a_3$$$, etc.

Make a big positive element using moves $$$(i, i)$$$, then make $$$a_2$$$ bigger.

If all the elements are negative, you can make suffix sums (they are nondecreasing) with moves $$$(n-1, n), (n-2, n-1), \dots$$$

If there is at least one positive element $$$a_x$$$,

• make $$$a_x \gt 20$$$ using $$$5$$$ moves $$$(x, x)$$$;
• make $$$a_2$$$ the biggest element using $$$2$$$ moves $$$(2, x)$$$;
• make $$$a_3$$$ the biggest element using $$$2$$$ moves $$$(3, 2)$$$;
• ...

This strategy requires $$$5 + 2(n-1) \leq 43$$$ moves.

Complexity: $$$O(n)$$$

You can win in $$$n-1$$$ moves if all the elements are negative, but also if all the elements are positive.

Again, make a big positive / negative element, then use it to make everything positive / negative.

In how many moves can you either make everything positive or make everything negative?

Assume the positive elements are at least as many as the negative elements. Can you win in $$$34$$$ moves?

The bottleneck is making the big positive element. Is it always necessary? Can you find a better bound on the "best" number of moves?

If you either make everything positive or make everything negative, you can win in $$$n-1 \leq 19$$$ moves by making prefix sums or suffix sums, respectively. So, you have to reach one of these configurations in $$$12$$$ moves.

How to make everything positive? First, you create a big element with the maximum absolute value (this requires $$$x_1$$$ moves), then you add it to every negative element (this requires $$$x_2$$$ moves). $$$y_1$$$ and $$$y_2$$$ are defined similarly in the negative case.

So,

• one of $$$x_1$$$ and $$$y_1$$$ is $$$0$$$ (because the element with the maximum absolute value at the beginning is either positive or negative), and the other one is $$$\leq 5$$$ (because you can make $$$|a_i| \geq 32$$$ in $$$5$$$ moves);
• $$$x_2$$$ is the number of negative elements, $$$y_2$$$ is the number of positive elements. So, $$$x_2 + y_2 \leq n \leq 20$$$.

Therefore, you need additional $$$\min(x_1 + x_2, y_1 + y_2)$$$ moves. Since $$$x_1 + x_2 + y_1 + y_2 \leq 25$$$, $$$\min(x_1 + x_2, y_1 + y_2) \leq \lfloor \frac{25}{2} \rfloor = 12$$$, as we wanted. Now you can simulate the process in both cases (positive and negative), and choose one that requires $$$\leq 31$$$ moves in total.

Complexity: $$$O(n)$$$

The order of used cards doesn't matter. So, you can assume you always use the card on the top.

Suppose that you unlock $$$x$$$ cards in total. How many points can you get?

If you unlock $$$x$$$ cards, it means you end up making moves with the first $$$x$$$ cards. So, you know the total number of (cards + points) that you get.

If you unlock $$$x$$$ cards, the number of points is uniquely determined. It's convenient to assume that $$$x \leq 2n$$$ and the cards $$$n+1, \dots, 2n$$$ have value $$$0$$$.

Now you have to determine the unlockable prefixes of cards (i.e., the values of $$$x$$$ you can reach). It looks similar to knapsack.

You can optimize the solution using a bitset. Be careful not to use locked cards.

First, note that the order of used cards doesn't matter. If you use at least once a card that is not on the top on the deck, you can prove that using the cards in order (from the top) would give the same number of victory points.

Let's add $$$n$$$ cards with value $$$0$$$ at the end of the deck. Then, it's optimal to unlock $$$x \leq 2n$$$ cards, and use cards $$$1, \dots, x$$$, getting $$$a_1 + \dots + a_x - x + 1$$$ points.

Let's find the reachable $$$x$$$. Let $$$dp_i$$$ be a bitset that stores the reachable $$$x$$$ after using the first $$$i$$$ cards.

• Base case: $$$dp_{0,1} = 1$$$.

• Transitions: first, $$$dp_{i}$$$ |= $$$dp_{i-1}$$$ << $$$a_i$$$. If $$$dp_{i,i} = 1$$$, you can update the answer with $$$a_1 + \dots + a_i - i + 1$$$, but you can't unlock any other card, so you have to set $$$dp_{i,i} = 0$$$ before transitioning to $$$i+1$$$.

Complexity: $$$O(n^2/w)$$$

Consider $$$n$$$ blocks in positions $$$S_1, S_2, \dots, S_n$$$. After how much time does block $$$x$$$ disappear? It may be convenient to put a fake "static" block in position $$$m+1$$$.

Block $$$x$$$ disappears when it reaches block $$$x+1$$$. But what if block $$$x+1$$$ disappears before block $$$x$$$?

From the perspective of block $$$x$$$, it's convenient to assume that block $$$x+1$$$ never disappears: when it touches another block $$$y$$$, it's $$$y$$$ that disappears.

When you consider the pair of blocks $$$x, x+1$$$, the other blocks don't really matter, and you can use linearity of expectation to calculate the contribution of each pair independently.

A reasonable interpretation is given by considering an $$$(n+1) \times (m+1)$$$ grid, where the $$$i$$$-th row initially contains a block in column $$$S_i$$$. Then, you are calculating the expected time required for the blocks $$$1, \dots, m$$$ to have another block immediately below them (in the same column).

Blocks $$$x, x+1$$$ both move with probability $$$1/2$$$, unless block $$$x+1$$$ has reached position $$$m+1$$$.

$$$dp_{i,j} =$$$ expected number of moves of block $$$x$$$ before it disappears, if the block $$$x$$$ is in position $$$i$$$ and the block $$$x+1$$$ is in position $$$j$$$.

Consider an $$$(n+1) \times (m+1)$$$ grid, where the $$$i$$$-th row initially contains a block in column $$$S_i$$$, and row $$$n+1$$$ contains a block in column $$$m+1$$$.

• The set is empty if all the blocks are in column $$$m+1$$$; i.e., if every block has reached the block in the following row.
• Every "connected component" of blocks (except the last one) represents an element in the set. These components move equiprobably.

Let's calculate the expected time required for the block in row $$$x$$$ to "reach" the block in row $$$x+1$$$. If you consider a single pair of blocks, every block moves with probability $$$1/2$$$, unless block $$$x+1$$$ is in column $$$m+1$$$.

So, you can calculate $$$dp_{i,j} =$$$ expected number of moves of the block $$$x$$$ before it reaches the block $$$x+1$$$, if the block $$$x$$$ is in position $$$i$$$ and the block $$$x+1$$$ is in position $$$j$$$.

The base cases are $$$dp_{i,m+1} = (m+1)-i$$$ (because only the block $$$x$$$ can move) and $$$dp_{i,i} = 0$$$ (because block $$$x$$$ has already reached block $$$x+1$$$). In the other cases, $$$dp_{i,j} = ((dp_{i+1,j} + 1) + dp_{i,j+1})/2$$$.

By linearity of expectation, the answer is the sum of $$$dp_{S_i, S_{i+1}}$$$.

Complexity: $$$O(m^2)$$$

You can find any $$$a_i$$$ in $$$9$$$ queries.

Find the nodes in the cycle in the component with node $$$1$$$. What happens if you know the whole cycle?

Suppose you already know some nodes in the cycle. Can you find other nodes faster?

Can you "double" the number of nodes in the cycle?

The component with node $$$1$$$ contains a cycle. If you know the whole cycle (of length $$$x$$$), you can win in $$$n-x$$$ queries by asking for each node if it ends up in the cycle after $$$n$$$ moves.

You can get a node in the cycle in $$$9$$$ queries, doing a binary search on the $$$n$$$-th successor of node $$$1$$$.

How to find the rest of the cycle?

• First, find $$$k$$$ nodes in the cycle, doing a binary search on the successor of the last node found. These nodes make a set $$$C$$$.
• Then, check for each node if it's "sufficiently close" to $$$C$$$, by asking $$$(i, k, C)$$$. Now, you know either $$$2k$$$ nodes in the cycle, or the whole cycle.
• Repeat until you get the whole cycle.

If you choose $$$k = 63$$$, you spend at most $$$9 \cdot 63 + (500 - 63) + (500 - 126) + (500 - 252) + (500 - 252) = 1874$$$ queries.

Go for a randomized approach.

Many ones are useful.

Either you go for a greedy or for a backpack.

We describe a randomized solution that solves the problem for $$$m$$$ up to $$$10^{11}$$$ (and, with some additional care, may be able to solve also $$$m$$$ up to $$$10^{12}$$$). We decided to give the problem with the smaller constraint $$$m\le 10^{10}$$$ to make the problem more accessible and because there may be some rare cases below $$$10^{11}$$$ for which our solution is too slow (even though we could not find any). We don't know any provably correct solution, if you have one we would be curious to see it. We expect to see many different solutions for this problem.

Main idea: Choose suitably the values $$$a_1, a_2, \dots, a_h$$$ that belong to $$$[1,29]$$$ and then find $$$a_{h+1}, a_{h+2},\dots,a_k$$$ in $$$[31,60]$$$ by solving a backpack-like problem.

Let us describe more precisely the main idea. Assume that $$$a_1, a_2, \dots, a_h\le 30$$$ are fixed and they satisfy $$$a_1+a_2+\cdots+a_h \lt 60$$$. For any $$$s=0,1,2,\dots,29$$$, let $$$f(s)$$$ be the number of subsets $$$I\subseteq{1,2,\dots,h}$$$ so that $$$\sum_{i\in I}a_i=s$$$. If we can find some values $$$0\le s_1,s_2,\dots,s_{k-h}\le 29$$$ so that $$$f(s_1)+f(s_2)+\cdots+f(s_{k-h})=s$$$, then by setting $$$a_{h+i} = 60-s_i$$$ for $$$i=1,2,\dots, k-h$$$ we have found a valid solution to the problem.

There are two main difficulties:

• How can we find $$$s_1, s_2,\dots, s_{k-h}$$$?
• How should we choose $$$a_1, a_2,\dots, a_h$$$?

Since it is important to get a good intuitive understanding of the computational complexity of the algorithm, let us say now that we will choose $$$h\le 44$$$ and (accordingly) $$$k-h=16$$$. These values are flexible (the solution would still work with $$$h\le 45$$$ and $$$k-h=45$$$ for example). We will say something more about the choice of these values when we will describe how $$$a_1,a_2,\dots, a_h$$$ shall be chosen.

The backpack problem to find $$$s_1, s_2,\dots, s_{k-h}$$$.

The naive way to find $$$s_1,\dots, s_{k-h}$$$ would be to try all of them. There are $$$\binom{k-h + 29}{29}$$$ possible ways (up to order, which does not matter). Since $$$k-h=16$$$ this number is $$$\approx 2\cdot 10^{11}$$$ which is too much to fit in the time limit.

To speed up the process, we will do as follows. Partition randomly $$$A\cup B={0,1,\dots, 29}$$$ into two sets of size $$$15$$$. We iterate over all possible $$$s_1, s_2, \dots, s_{(k-h)/2}\in A$$$ and over all possible $$$s_{(k-h)/2+1},\dots, s_{k-h}\in B$$$ and check whether the sum of one choice from the first group and one choice from the second group yields the result. This is a standard optimization for the subset sum problem. What is its complexity? It can be implemented in linear time in the size of the two groups we have to iterate over, which have size $$$\binom{(k-h)/2+15}{15}\approx 5\cdot 10^5$$$. Notice that in this faster way we will not visit all the $$$\binom{k-h+29}{29}$$$ possible choices $$$s_1,s_2,\dots, s_{k-h}$$$ because we are assuming that exactly half of them belong to $$$A$$$ and exactly half of them belong to $$$B$$$. This is not a big deal because with sufficiently high probability we will find a solution in any case.

The choice of $$$a_1, a_2,\dots, a_{h}$$$.

It remains to decide how we should select $$$a_1, a_2, \dots, a_{h}$$$. The following choice works:

• Approximately the first $$$\log_2(m)$$$ values are set equal to $$$1$$$.
• Five additional values are chosen randomly from $$$[1, 6]$$$ so that the total sum stays below $$$60$$$.

One should repeat the whole process until a solution is found.

Some intuition on the construction. The choice of $$$a_1, \dots, a_{h}$$$ may seem arbitrary; let us try to justify it. The goal is to generate a set of values $$$f(0), f(1),\dots, f(29)$$$ that are simultaneously ``random enough'' and with size smaller but comparable to $$$m$$$. These two conditions are necessary to expect that the backpacking problem finds a solution with high enough probability.

If $$$a_1=a_2=\cdots=a_{h}=1$$$, then $$$f(s) = \binom{k-h}{s}$$$ and these numbers have size comparable to $$$m$$$ if $$$2^{h}$$$ is comparable to $$$m$$$. This observation explains why we start with approximately $$$\log_2(m)$$$ ones. The issue is that we need some flexibility in the process as we may need to repeat it many times, this flexibility is provided by the addition of some additional random elements which don't change the magnitude of the values $$$f(0), f(1), \dots, f(29)$$$ but that modify them as much as possible (if we added a large number it would not affect many $$$f(s)$$$ and thus it would not be very useful).

Solve the 2d version first.

The 4d version is not too different from the 2d one.

Find all the points such that the expected number of necessary moves is wrong.

The $$$2$$$-dimensional case.

Let us begin by cpnsidering the $$$2$$$-dimensional version of the problem. The solution to this simpler version provides the idea of the approach for the $$$4$$$-dimensional version.

We want to reach $$$(a, b)$$$. Can we do it with exactly $$$k$$$ moves? Two simple necessary conditions are:

• $$$|a|+|b|\le 1 + 2 + \cdots + k$$$,
• $$$a+b$$$ and $$$1 + 2 + \cdots + k$$$ shall have the same parity.

It turns out that this two conditions are also sufficient! One can prove it by induction on $$$k$$$ as follows. If $$$k=0$$$ or $$$k=1$$$ or $$$k=2$$$ the statement is simple, thus we may assume $$$k\ge 3$$$.

Without loss of generality we may assume $$$0\le a\le b$$$. If $$$|a|+|b-k| \le 1 + 2 + \cdots + k-1$$$, then the statement follows by inductive hypothesis. Assume by contradiction that such inequality is false. If $$$b\ge k$$$ then we have a contradiction because $$$|a|+|b-k| = |a|+|b|-k \le (1 + 2 + \cdots + k) - k$$$. Otherwise $$$b \lt k$$$ and the contradiction is $$$|a|+|b-k| = a + k-b \le k \le 1 + 2 + \cdots + k-1$$$.

Hence, we have shown:

Lemma 1: The point $$$(a, b)$$$ is reachable with exactly $$$k$$$ moves if and only if $$$|a|+|b| \le 1 + 2 + \cdots + k$$$ and $$$a+b$$$ has the same parity of $$$1+2+\cdots + k$$$.

The $$$4$$$-dimensional case.

One may expect statement analogous to the one of Lemma 1 to hold also when there are $$$4$$$ coordinates. It does not, but it almost does and this is the crucial idea of the solution. More precisely, the number of counter examples to such statement is rather small and we can find all of them. This is the intuition behind the following definition.

Definition: For $$$k\ge 0$$$, let $$$A_k$$$ be the set of points $$$(a, b, c, d)$$$ such that $$$|a|+|b|+|c|+|d|\le 1 + 2 + \cdots + k$$$ and $$$a+b+c+d$$$ has the same parity of $$$1 + 2 + \cdots + k$$$ but $$$(a, b, c, d)$$$ is not reachable with exactly $$$k$$$ moves.

As an immediate consequence of the definition, we have

Observation: The point $$$(a, b, c, d)$$$ is reachable with exactly $$$k$$$ moves if and only if $$$|a|+|b|+|c|+|d| \le 1 + 2 + \dots + k$$$ and $$$a+b+c+d$$$ has the same parity of $$$1+2+\cdots + k$$$ and $$$(a, b, c, d)\not\in A_k$$$.

Thanks to this observation, if one is able to efficiently find $$$A_k$$$ for all interesting values of $$$k$$$, then solving the problem is (comparatively) easy. The following lemma is our main tool for this purpose.

Lemma 2: Assume that $$$(a, b, c, d) \in A_k$$$ with $$$0\le a\le b\le c\le d$$$. Then, either $$$k\le 6$$$ or $$$(a, b, c, d - k) \in A_{k-1}$$$.

Proof: The strategy is the same adopted to show Lemma 1. In some sense, we are saying that the inductive step works also in dimension $$$4$$$, but the base cases don't.

If $$$|a|+|b|+|c|+|d-k|\le 1 + 2 + \cdots + k-1$$$, then it must be $$$(a, b, c, d-k)\in A_{k-1}$$$ because if $$$(a, b, c, d-k$$$ were reachable with $$$k-1$$$ moves then $$$(a, b, c, d)$$$ were reachable with $$$k$$$ and we know that this is not true.

Assume by contradiction that $$$|a|+|b|+|c|+|d-k| \gt 1 + 2 + \cdots + k-1$$$. If $$$d\ge k$$$ then we reach the contradiction $$$|a|+|b|+|c|+|d-k| = a+b+c+d-k \le (1 + 2 + \dots + k) - k$$$. Otherwise, $$$d \lt k$$$ and thus we reach the contradiction $$$|a|+|b|+|c|+|d-k| = a+b+c+k-d\le a+b+k\le 3k-2\le 1 + 2 + \dots + k-1$$$ (for $$$k\ge 7$$$).

We can now describe the solution. Assume that we know $$$A_{k-1}$$$. First of all, notice that it is then possible to determine in $$$O(1)$$$ whether a point belongs to $$$A_k$$$ or not. To generate a list of candidate elements for $$$A_k$$$ we proceed as follows:

• If $$$k\le 6$$$, we simply iterate over all points with $$$|a|+|b|+|c|+|d|\le 1 + 2 + \cdots + k$$$.
• Otherwise, we iterate over the points in $$$A_{k-1}$$$ and we consider as candidate elements for $$$A_k$$$ the points that can be obtained by changing the value of one coordinate by $$$k$$$.

Thanks to Lemma 2, we know that this process finds all the elements in $$$A_k$$$. Once $$$A_0, A_1, A_2, A_3,\dots$$$ are known, the problem boils down to a (relatively) simple counting argument that we skip.

One can verify that to handle correctly all points with coordinates up to $$$1000$$$ it is necessary to compute $$$A_k$$$ for $$$0\le k \le 62$$$.

One additional cheap trick is required to make $$$A_k$$$ sufficiently small and get a sufficiently fast solution. Given $$$(a, b, c, d)$$$, the instance of the problem is equivalent if we change the signs of the coordinates or we change the order of the coordinates. Hence we shall always ``normalize'' the point so that $$$0\le a \le b\le c\le d$$$. If we do this consistently everywhere in the process, the solution becomes an order of magnitude faster. In particular, this trick guarantees $$$|A_k|\le 5000$$$ for all $$$0\le k\le 62$$$.

Bonus question: Find an explicit closed form for the elements in $$$A_k$$$ for any $$$k$$$. (in this way one can solve the problem also with larger constraints on $$$A, B, C, D$$$; but it is tedious)