MINANDMAX - 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 \min(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:

The array is considered circular, so each of its elements can ‘contribute’ to f(A) at most twice.
Here, we say A_i contributes to f(A) if either A_i = \min(A_i, A_{i+1}) or A_i = \min(A_i, A_{i-1}) hold (meaning A_i will appear in the sum at least once).

Our objective is to minimize f(A).
So, ideally, we’d like it if smaller values contribute as much as possible (i.e twice), while larger values contribute as little as possible (i.e not at all).

Since each element can only contribute twice, and there are N elements in the summation, at the very least we need \left\lceil \frac{N}{2} \right\rceil distinct elements to contribute - clearly, it’s best to choose 1, 2, 3, \ldots, \left\lceil \frac{N}{2} \right\rceil.
Finally, we also want to ensure that greater values don’t contribute; meaning no two of them should be adjacent to each other.

With all this in mind, there’s a fairly natural construction:

A = [1, N, 2, N-1, 3, N-2, 4, \ldots, ]

That is, quite simply, alternate ‘small’ values with ‘large’ ones; hence ensuring that each ‘small’ number contributes twice and each ‘large’ one doesn’t at all.

Of course, N can be quite large, so it’s not possible to first create this array then compute its f(A) value.
Let’s see if f(A) for such an array can be found without having to create it first.

  • Suppose N is even, i.e, N = 2k.
    Then, the created array is [1, 2k, 2, 2k-1, 3, \ldots, k+2, k, k+1].
    The f(A) for this array will be (2\cdot 1 + 2\cdot 2 + 2\cdot 3 + \ldots + 2\cdot k) = 2\cdot \frac{k\cdot (k+1)}{2} = k\cdot (k+1).
  • Suppose N is odd, i.e, N = 2k+1.
    Then, the created array is [1, 2k+1, 2, 2k, 3, \ldots, k, k+2, k+1].
    For this array f(A) = (2\cdot 1 + 2\cdot 2 + \ldots + 2\cdot k + (k+1)), which simplifies to k\cdot (k+1) + (k+1) = (k+1)^2.

This way, the answer can be found in constant time, without explicitly having to construct A.

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 = 2 * (n / 2) * (n / 2 + 1) / 2;
    if (n % 2) ans += (n + 1) / 2;

    cout << ans << "\n";
    // n * 2 + .... + 2 
    // 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())
    k = n//2
    ans = k*(k+1)
    if n%2 == 1: ans += k+1
    print(ans)