Summer_Sheep's blog

By Summer_Sheep, history, 3 days ago, In English

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

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Summer_Sheep (previous revision, new revision, compare).

»
3 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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.