Alpacas

Written by Omar Abdelkafi Ykrelef.

Problem Statement

• English
• French
• Arabic

Solution

The problem naturally divides into two parts: minimum moves and maximum moves.

---

Minimum number of moves

We want all alpacas to fit inside a consecutive block of length . If a block already contains alpacas, then the number of moves needed is:

So we need to maximize .

---

Key idea

Each alpaca can act as a boundary of the block:

• If is the left endpoint, the block is:

• If is the right endpoint, the block is:

---

Algorithm

Step 1: Sorting

First, sort the alpaca positions:

Now is in increasing order. This makes it possible to use binary search.

---

Step 2: Binary search

To count how many alpacas lie inside :

• lower_bound(a.begin(), a.end(), L) → gives the first index where .

• upper_bound(a.begin(), a.end(), R) → gives the first index after the last alpaca . → subtract 1 to get the last index where .

Now the alpacas inside are exactly from to .

So the count is:

---

Step 3: Applying it to our problem

For each alpaca , we consider two ranges:

1. Treat as the left endpoint:

Count how many alpacas are inside .

2. Treat as the right endpoint:

Count how many alpacas are inside .

We do this with binary search for each alpaca, and keep the maximum count.

Finally:

---

Special case

If the formula gives 1 and the single empty position is at one end (either before the first alpaca or after the last alpaca), then the answer should be 2 (since you cannot solve it in a single move).

---

Maximum number of moves

At first glance, you might think to count all free spots. However, alpacas cannot be moved all the way to the extreme ends.

Define:

(all empty spots between the first and last alpaca).

Then the maximum number of moves is:

---

Time complexity

• Finding minimum moves:
• Finding maximum moves:

Total time complexity:

Implementation

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n+1);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end()); // sort alpaca positions

    int MIN = INT_MAX;

    // Try each alpaca as both left and right endpoint
    for (int i = 1; i <= n; i++) {
        int down = a[i] - n + 1; // block of length n ending at a[i]
        int up   = a[i] + n - 1; // block of length n starting at a[i]

        // d1 = index of first alpaca >= down
        int d1 = distance(a.begin(), lower_bound(a.begin(), a.end(), down));
        // d2 = index of last alpaca <= up
        int d2 = distance(a.begin(), upper_bound(a.begin(), a.end(), up)) - 1;

        // number of alpacas covered if we use "down" block
        int ans1 = n - (abs(i - d1) + 1);
        // number of alpacas covered if we use "up" block
        int ans2 = n - (abs(i - d2) + 1);

        // special case: if result = 1 and the empty spot is at the side → needs 2
        if (a[d1] != down && ans1 == 1) {
            ans1++;
        }
        if (a[d2] != up && ans2 == 1) {
            ans2++;
        }

        MIN = min(MIN, min(ans1, ans2));
    }
    int sum = (a[n] - a[1] + 1) - n; // total free spaces

    // maximum moves = max(total_free - first_gap, total_free - last_gap)
    int MAX = max(sum - (a[n] - a[n - 1] - 1) , sum - (a[2] - a[1] - 1));
    
    cout << MIN << '\n' << MAX << '\n';
}