Mark and Spaceship
Contest: Codeforces Round 889 (Div. 1)
Difficulty rating: 3500
Tags: brute force, dp

Mark loves to move fast. So he made a spaceship that works in $$$4$$$-dimensional space.

He wants to use the spaceship to complete missions as fast as possible. In each mission, the spaceship starts at $$$(0, 0, 0, 0)$$$ and needs to end up at $$$(a, b, c, d)$$$. To do this, he instructs the spaceship's computer to execute a series of moves, where each move is a unit step in one of the eight cardinal directions: $$$(\pm 1, 0, 0, 0)$$$, $$$(0, \pm 1, 0, 0)$$$, $$$(0, 0, \pm 1, 0)$$$, $$$(0, 0, 0, \pm 1)$$$.

Unfortunately, he also moved fast when building the spaceship, so there is a bug in the spaceship's code. The first move will be executed once, the second move will be executed twice, the third move will be executed thrice, and so on. In general, the $$$i$$$-th move will be executed $$$i$$$ times.

For any four integers $$$a, b, c, d$$$, let $$$f(a, b, c, d)$$$ be the minimum number of moves of a mission that ends up at $$$(a, b, c, d)$$$. Compute the sum of $$$f(a, b, c, d)$$$ over all points (with integer coordinates) such that $$$-A\le a\le A$$$, $$$-B\le b\le B$$$, $$$-C\le c\le C$$$, $$$-D\le d\le D$$$.

Input format:
The only line of the input contains the four integers $$$A, B, C, D$$$ ($$$0\le A,B,C,D\le 1000$$$).

Output format:
Print the sum of $$$f(a, b, c, d)$$$ over the set of points described in the statement.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first sample, one has to compute $$$f(-1, 0, 0, 0)+f(0, 0, 0, 0) + f(1, 0, 0, 0) = 1 + 0 + 1 = 2$$$.

In the second sample, one has to compute the sum of $$$f(a, b, c, d)$$$ over $$$27$$$ different points $$$(a, b, c, d)$$$. Let us describe the value of $$$f(a, b, c, d)$$$ for some of them:

- It holds $$$f(-1, 0, 0, -1)=3$$$ and it may be achieved with the following sequence of moves (an arrow $$$\xrightarrow{\pm i}$$$ denotes that the move is performed on the $$$i$$$-th coordinate): $$$$$$(0, 0, 0, 0) \xrightarrow{-1} (-1, 0, 0, 0) \xrightarrow{+4} (-1, 0, 0, 2) \xrightarrow{-4} (-1, 0, 0, -1).$$$$$$
- It holds $$$f(1, 1, 0, 1) = 5$$$ and it may be achieved with the following sequence of moves: $$$$$$(0, 0, 0, 0) \xrightarrow{+1} (1, 0, 0, 0) \xrightarrow{-2} (1, -2, 0, 0) \xrightarrow{+2} (1, 1, 0, 0) \xrightarrow{-4} (1, 1, 0, -4) \xrightarrow{+4} (1, 1, 0, 1).$$$$$$

In the third sample, one has to compute the sum of $$$f(a, b, c, d)$$$ over $$$7\cdot5\cdot 9\cdot 3$$$ points. One of them is $$$(3, 2, 4, 1)$$$. It holds $$$f(3, 2, 4, 1) = 4$$$ and it may be achieved with the following sequence of moves: $$$$$$(0, 0, 0, 0) \xrightarrow{+4} (0, 0, 0, 1) \xrightarrow{+2} (0, 2, 0, 1) \xrightarrow{+1} (3, 2, 0, 1) \xrightarrow{+3} (3, 2, 4, 1).$$$$$$

Example input:
1 0 0 0

Example output:
2

Example input:
1 1 0 1

Example output:
82

Editorial:
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.
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 < 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|> 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 < 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$$$.
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)