MINANDMAX2 - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: algomaniacjuee
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

For an array A of length N, define f(A) = \sum_{i=1}^N \max(A_i, A_{i+1}) (where A_{N+1} := A_1, meaning the array is circular).

Find the minimum possible value of f(A) across all permutations A of [1, N].

EXPLANATION:

This time (unlike in MINANDMAX), we’re dealing with the maximum of two adjacent elements; though we still want to minimize the overall sum.

Let’s try to place elements from N to 1.

  • No matter which permutation is chosen, N will always contribute twice to the sum (since it’s greater than both its neighbors).
  • Next, we want to place N-1.
    If N-1 is not adjacent to N, it’ll contribute twice to the sum (since it’s larger than everything else).
    If it is adjacent to N, it’ll contribute only once.
    Our aim is to minimize the overall sum, so the latter option seems better - for now, let’s place N-1 adjacent to N.
  • Next, look at N-2.
    Similar reasoning shows that intuitively, we’d like N-2 to be placed next to either N or N-1 (otherwise it’ll contribute twice to the sum).
  • More generally, for any x, it seems like a good idea to ensure that x is placed next to one element larger than it.

This reasoning tells us that choosing A = [1, 2, 3, \ldots, N] is one optimal permutation.
And it turns out that yes, this is indeed optimal!

Proof

Let P be any permutation.
Since it’s circular, rotate it so that P_N = N.
Now, we’ll show that P can be converted to [1, 2, 3, \ldots, N] without ever increasing f(P), which will show that f([1, 2, \ldots, N]) is minimal.

If P is already in the required form, nothing needs to be done.
Otherwise, let i be the rightmost index such that P_i \neq i.
In particular, 1 \lt i \lt N will hold (recall that we ensured P_N = N at the start), and element i will be somewhere to the left of index i.

Let the current value of P_i be x, and the current position of i be y.
Consider what happens when we swap the values at positions i and y (that is, place i at position i and x at position y).
Notice that the only changes to f(P) will come from pairs of indices that include indices i and/or y.

Case 1: y < i-1

The relevant pairs of adjacent maximums are (y-1, y), (y, y+1), (i-1, i), (i, i+1).
In the initial permutation P, their values were \max(i, P_{y-1}), i, \max(x, P_{i-1}), i+1 respectively.
After the swap, their values will be \max(x, P_{y-1}), \max(x, P_{y+1}), i, i+1 respectively.

It can be shown that the sum (i+i+i+1 + \max(x, P_{i-1})) is never smaller than the sum (i+i+1+\max(x, P_{y-1}) + \max(x, P_{y+1})), using the facts that:

  • \max(x, P_{i-1}) \lt i, since the positions of i and everything \gt i are accounted for.
  • \max(x, P_{y-1}) + \max(x, P_{y+1}) can be at most i-1+i-2.
  • The only possible exception is when y = 1, in which case \max(i, P_{y-1}) = \max(x, P_{y-1}) = N
Case 2: y = i-1

This is even simpler: we only have to look at the pairs (i-2, i-1), (i-1, i), (i, i+1).
Before the swap, the values are \max(i, P_{i-2}), i, i+1.
After the swap, the values are \max(x, P_{i-2}, i, i+1.
Since x \lt i the second option is clearly never smaller than the first, so swapping is good.

So, performing this swap doesn’t increase f(P), yet it increases the length of the ‘good’ suffix.
Repeatedly perform this operation and you’ll end up at [1, 2, 3, \ldots, N], as desired.

Computing f(A) for this array is quite simple: it equals

2 + 3 + 4 + \ldots + N-1 + N + N = \frac{N\cdot (N+1)}{2} + N - 1

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n; cin >> n;

    // 1 + 1 + 2 + 2 + 3 + 3 + .... 
    int ans = n * (n + 1) / 2;
    ans += n - 1;
    cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    print((n+1)*(n+2)//2 - 2)