# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Shanu Singroha

Tester: Nishank Suresh, Utkarsh Gupta

Editorialist: Pratiyush Mishra

# DIFFICULTY:

1401

# PREREQUISITES:

None

# PROBLEM:

You are given an integer N.

Find a permutation P = [P_1, P_2, \ldots, P_N] of the integers \{1, 2, \ldots, N\} such that sum of averages of all consecutive triplets is minimized, i.e.

is minimized.

If multiple permutations are possible, print any of them.

# EXPLANATION:

We are given the following sum to compute

This can be simplified as:

Since P_1 and P_n is not repeated and P_{n-1} and P_2 is repeated twice so it makes sense to assign maximum values to P_1 and P_n, followed by the next largest values to P_{n-1} and P_2. Rest of the values we can assign randomly since rest all of them are in multiples of 3. Thus we can have one of the possible permutations as follows:

# TIME COMPLEXITY:

O(N), for each test case.

# SOLUTION:

Editorialistâ€™s Solution

Setterâ€™s Solution

Tester1â€™s Solution

Tester2â€™s Solution