Giving an positive integer $$$n$$$ and another positive integer $$$d$$$ .
You need to create an array that its length is $$$2 \times n$$$ ,and it must meet these conditions:
1, All the numbers between $$$1$$$ to $$$n$$$ must exist $$$2$$$ times.
2, For the number $$$i$$$,if $$$i$$$ is odd ,then the two position of $$$i$$$'s difference value must be more than $$$d$$$.
3, For the number $$$i$$$,if $$$i$$$ is even ,then the two position of $$$i$$$'s difference value must not be more than $$$d$$$.
if it has no solution,print -1. Else,print the array you create as your answer.
It uses Special Judge ,so you can answer any array meet these conditions.
$$$1 \leq n \leq 10^6$$$. $$$1 \leq d \leq 5 \times 10^5$$$.
Auto comment: topic has been updated by Summer_Sheep (previous revision, new revision, compare).
I claim that there exists a valid arrangement if and only if $$$d < \lceil n / 2 \rceil + 2\lfloor n / 2 \rfloor$$$.
Proof:
Consider a valid arrangement that satisfies the constraint. Consider an odd number $$$i$$$ with the smallest gap. Because this is the smallest gap, there cannot be two same odd numbers placed in between the two $$$i$$$. So there can be at most $$$\lceil n / 2 \rceil - 1$$$ other odd numbers placed in between the two $$$i$$$s. On the other hand, there are a total of $$$2\lfloor n / 2 \rfloor$$$ even numbers, which means there can be at most $$$\lceil n / 2 \rceil - 1 + 2\lfloor n / 2 \rfloor$$$ numbers placed in between the two $$$i$$$s. This proves that it is necessary for $$$d < \lceil n / 2 \rceil + 2\lfloor n / 2 \rfloor$$$ for a valid arrangement to exist.
Conversely, if $$$d < \lceil n / 2 \rceil + 2\lfloor n / 2 \rfloor$$$, we can construct a valid arrangement as follows:
Case 1) $$$n$$$ even
$$$1, 3, 5, ..., n - 1, 2, 2, 4, 4, ..., n, n, 1, 3, 5, ..., n - 1$$$
Case 2) $$$n$$$ odd
$$$1, 3, 5, ..., n, 2, 2, 4, 4, ..., n - 1, n - 1, 1, 3, 5, ..., n$$$
It is easy to verify that these are valid arrangement satisfying the constraint.
There may be some off by one errors in the argument, but the general idea should hold.
thanks! Good explanation.