AVGPERM Editorial

editorial
, ,
1

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

2

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
3

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
4

don’t understand this question properly.
“such that sum of averages of all consecutive triplets is minimized, i.e.”. Even if we consider 1, 2 ,3,4
in all the cases the sum of averages would be (1 + 2 + 3 + 2 + 3 + 4) / 3. So can’t we just print [ 1 2 3 4] here?

As if we change the numbers the sum would always be same even if we do [3 2 4 1] right?

Can you please explain?

5

Im not sure if im right in the sequence must be like N, 2, 1, N-1, 4, 3, N-2, N, 6, 5, N-3…

6

in this question if you think about it the sum of all the total consecutive sequences but it asks us about a specific permutation in which they all individually would also be minimum with respect to all the other cases of the permutations