SUMPERM - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Testers: wuhudsm, satyam_343
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given N, find a permutation of \{1, 2, 3, \ldots, N\} such that P_1 + P_2 + \ldots + P_i is not divisible of i for every 1 \lt i \leq N.

EXPLANATION:

First, note that when N is odd, no valid permutation exists.

Why?

Let N = 2k+1.

No matter what permutation is, the prefix of length N will have the same sum; since it’s the sum of the first N natural numbers.
This sum is 1 + 2 + \ldots + N = \frac{N(N+1)}{2} = \frac{N\cdot (2k+2)}{2} = N\cdot (k+1), which is a multiple of N.

When N is even, there is in fact a rather simple construction, which you might notice by solving for small even values of N:
[2, 1, 4, 3, 6, 5, \ldots, N, N-1].

Why does this work?

Let’s look at even and odd indices separately.

For an even index, say 2i, the corresponding sum is 1 + 2 + \ldots + 2i = \frac{2i(2i+1)}{2} = i(2i+1). This is not divisible by 2i.

For an odd index, say 2i+1, the corresponding sum is 1 + 2 + \ldots + (2i-1) + 2i + (2i+2) = i(2i+1) + (2i+2).
This can be further simplified into (2i+1)(i+1) + 1, which isn’t divisible by (2i+1) (since it leaves a remainder of 1 when divided by 2i+1).

This way, both the odd and the even indices are satisfied, so we’re done.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    if n%2 == 1: print(-1)
    else:
        for i in range(1, n+1, 2): print(i+1, i, end = ' ')
        print()
1 Like