Constructive Algorithm Techniques

1
#include <bits/stdc++.h>
2
using namespace std;
3
// Construct a permutation of 1..n such that |p[i] - p[i-1]| != 1 for all adjacent pairs.
4
// Strategy: place all even numbers first, then all odd numbers.
5
// This avoids adjacent difference 1 because consecutive numbers in the sequence differ by at least 2.
6
// Edge cases: n = 1 is trivial; n = 2 or 3 is impossible.
7
8
int main() {
9
    ios::sync_with_stdio(false);
10
    cin.tie(nullptr);
11
12
    long long n;
13
    if (!(cin >> n)) return 0;
14
15
    if (n == 1) {
16
        cout << 1 << "\n";
17
        return 0;
18
    }
19
    if (n == 2 || n == 3) {
20
        cout << "NO SOLUTION\n"; // Known impossibility
21
        return 0;
22
    }
23
24
    vector<int> ans;
25
    ans.reserve(n);
26
27
    // Place evens: 2, 4, 6, ...
28
    for (int x = 2; x <= n; x += 2) ans.push_back(x);
29
    // Place odds: 1, 3, 5, ...
30
    for (int x = 1; x <= n; x += 2) ans.push_back(x);
31
32
    // Output the permutation
33
    for (int i = 0; i < (int)ans.size(); ++i) {
34
        if (i) cout << ' ';
35
        cout << ans[i];
36
    }
37
    cout << '\n';
38
39
    return 0;
40
}
41

1
#include <bits/stdc++.h>
2
using namespace std;
3
/*
4
Given 2n integers, either split them into n pairs so that each pair sums to the same S, or report impossibility.
5
Approach:
6
1) Sort the array. The largest element must be paired with some other element; try pairing it with each candidate from the rest.
7
2) For a chosen S = a[max] + a[i], simulate pairing:
8
   - Maintain a multiset (ordered map of counts) of remaining numbers.
9
   - Repeatedly take the current largest x; its pair must be y = S - x.
10
   - If y does not exist, this S fails. Otherwise, remove x and y and record the pair.
11
3) If any attempt succeeds, output YES, S, and the pairs.
12
This maintains the invariant: all removed numbers form valid pairs summing to S; the multiset contains exactly the unused numbers.
13
*/
14
15
int main() {
16
    ios::sync_with_stdio(false);
17
    cin.tie(nullptr);
18
19
    int T; // number of test cases
20
    if (!(cin >> T)) return 0;
21
    while (T--) {
22
        int n; // we will read 2n numbers
23
        cin >> n;
24
        vector<long long> a(2 * n);
25
        for (auto &x : a) cin >> x;
26
        sort(a.begin(), a.end());
27
28
        bool found = false;
29
        long long finalS = 0;
30
        vector<pair<long long,long long>> answerPairs;
31
32
        // Try pairing the largest with each other element as the initial pair
33
        for (int i = 0; i < 2 * n - 1 && !found; ++i) {
34
            long long S = a.back() + a[i];
35
36
            // Multiset as value->count (ordered for easy access to current largest)
37
            map<long long, int> cnt;
38
            for (auto x : a) cnt[x]++;
39
40
            vector<pair<long long,long long>> pairs; pairs.reserve(n);
41
42
            auto erase_one = [&](long long v) {
43
                auto it = cnt.find(v);
44
                if (it == cnt.end()) return false;
45
                if (--(it->second) == 0) cnt.erase(it);
46
                return true;
47
            };
48
49
            // First remove the initial pair (a.back(), a[i])
50
            if (!erase_one(a.back()) || !erase_one(a[i])) continue;
51
            pairs.push_back({a.back(), a[i]});
52
53
            long long currentS = S;
54
            bool ok = true;
55
            // While elements remain, always take the current largest x and find y = currentS - x
56
            while (!cnt.empty()) {
57
                long long x = cnt.rbegin()->first; // largest remaining
58
                if (!erase_one(x)) { ok = false; break; }
59
                long long y = currentS - x;
60
                if (!erase_one(y)) { ok = false; break; }
61
                pairs.push_back({x, y});
62
            }
63
64
            if (ok) {
65
                found = true;
66
                finalS = S;
67
                answerPairs = move(pairs);
68
            }
69
        }
70
71
        if (!found) {
72
            cout << "NO\n";
73
        } else {
74
            cout << "YES\n";
75
            cout << finalS << '\n';
76
            for (auto &pr : answerPairs) {
77
                cout << pr.first << ' ' << pr.second << '\n';
78
            }
79
        }
80
    }
81
82
    return 0;
83
}
84

1
#include <bits/stdc++.h>
2
using namespace std;
3
// Output a permutation p of 1..n such that p[i] != i for all i (1-indexed positions).
4
// Construction:
5
// - If n == 1: impossible.
6
// - If n is even: swap each adjacent pair: (2,1), (4,3), ...
7
// - If n is odd and n >= 3: swap pairs up to n-3, then rotate the last three positions [n-2, n-1, n] -> [n-1, n, n-2].
8
9
int main() {
10
    ios::sync_with_stdio(false);
11
    cin.tie(nullptr);
12
13
    int T; if (!(cin >> T)) return 0;
14
    while (T--) {
15
        int n; cin >> n;
16
        if (n == 1) {
17
            cout << -1 << '\n'; // signal impossibility
18
            continue;
19
        }
20
        vector<int> p(n+1); // 1-indexed
21
        for (int i = 1; i <= n; ++i) p[i] = i;
22
23
        if (n % 2 == 0) {
24
            for (int i = 1; i <= n; i += 2) swap(p[i], p[i+1]);
25
        } else {
26
            // Swap pairs up to n-3
27
            for (int i = 1; i <= n-3; i += 2) swap(p[i], p[i+1]);
28
            // Rotate the last three: positions n-2, n-1, n receive values (n-1, n, n-2)
29
            int a = p[n-2], b = p[n-1], c = p[n];
30
            p[n-2] = b; p[n-1] = c; p[n] = a;
31
        }
32
33
        // Output permutation excluding index 0
34
        for (int i = 1; i <= n; ++i) {
35
            if (i > 1) cout << ' ';
36
            cout << p[i];
37
        }
38
        cout << '\n';
39
40
        // Optional sanity check in debug: ensure p[i] != i
41
        // for (int i = 1; i <= n; ++i) assert(p[i] != i);
42
    }
43
    return 0;
44
}
45