AVGPERM Editorial

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.

\sum_{i=1}^{N-2} \frac{P_i + P_{i+1} + P_{i+2}}{3}

is minimized.

If multiple permutations are possible, print any of them.

EXPLANATION:

We are given the following sum to compute

\sum_{i=1}^{N-2} \frac{P_i + P_{i+1} + P_{i+2}}{3}

This can be simplified as:

\frac{P_1 + 2 \times P_2 + 3 \times (P_3 + P_4.....P_{n-2}) + 2 \times P_{n-1} + P_n}{3}

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:

N,N-2,1,2,3.....N-3,N-1

TIME COMPLEXITY:

O(N), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

sorry, i misunderstood the statement for a while,

what if we want to minimize the maximum of (P_i + P_{i+1} + P_{i+2})/3

how to solve this problem ? or if use binary search for max value then how do we check it validity ?

1 Like

any idea why this sequence is wrong:
N, 1, 2, N-1, 3, 4, N-3, 5, 6, N-4, 7, 8…
I thought this will minimize the Pi + Pi+1 + Pi+2

1 Like