### Summer_Sheep's blog

By Summer_Sheep, history, 3 days ago,

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$.

• 0

 » 3 days ago, # |   0 Auto comment: topic has been updated by Summer_Sheep (previous revision, new revision, compare).
 » 3 days ago, # |   +1 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.
•  » » 3 days ago, # ^ |   0 thanks! Good explanation.