622A - Бесконечная последовательность

Let's decrease n by one. Now let's determine the block with the n-th number. To do that let's at first subtract 1 from n, then subtract 2, then subtract 3 and so on until we got negative n. The number of subtractions will be the number of the block and the position in the block will be the last nonnegative number we will get.

С++ solution

Complexity: .

622D - Оптимальное расположение чисел

Let's build the answer with the sum equal to zero. Let n be even. Let's place odd numbers in the first half of the array: the number 1 in the positions 1 and n, the number 3 in the positions 2 and n - 1 and so on. Similarly let's place even numbers in the second half: the number 2 in the position n + 1 and 2n - 1, the number 4 in the positions n + 2 and 2n - 2 and so on. We can place the number n in the leftover positions. We can build the answer for odd n in a similar way.

Easy to see that our construction will give zero sum.

C++ solution

Complexity: O(n).