Coding/q2.cpp at main · nishantlamba29/Coding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;
#define ll long long

/*
matrix de rkha h NxN
N <= 18
operation take i and j, first swap ith column and jth column and then ith row and jth row
after a finite number of operation,
you have to minimise and maximise the sum of lower triangular matrix

*/

const ll inf = 1e8;

vector<ll> solve(int N, vector<vector<int>> B) {

    int MASK = 1 << N;
    vector<vector<ll>> add(N, vector<ll>(MASK, 0));

    for(int x=0;x<N;x++){
        for(int mask=1; mask<MASK; ++mask){
            int lb = mask & -mask;
            int bit = __builtin_ctz(lb);
            add[x][mask] = add[x][mask ^ lb] + B[x][bit];
        }
    }
    // optimisation of this below thing is upar wala code
    // for(int mask =1; mask < MASK; mask++) {
    //     for(int i=0;i<N;i++) {
    //         for(int j=0;j<N;j++) {
    //             if(mask >> j & 1) {
    //                 add[i][mask] += B[i][j];
    //             }
    //         }
    //     }
    // }

    vector<ll> dp_max(MASK, -inf);
    vector<ll> dp_min(MASK, inf);
    dp_max[0] = dp_min[0] = 0;

    for(int mask=0; mask<MASK; ++mask){
        for(int x=0;x<N;++x){
            if(mask & (1<<x)) continue;
            int nm = mask | (1<<x);
            ll val = add[x][mask];
            dp_max[nm] = max(dp_max[nm], dp_max[mask] + val);
            dp_min[nm] = min(dp_min[nm], dp_min[mask] + val);
        }
    }

    return {dp_max[MASK - 1], dp_min[MASK - 1]};

}

vector<long long> brute_perm(int n, vector<vector<int>>& B) {
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    long long best = LLONG_MIN, worst = LLONG_MAX;
    do {
        long long sum = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < i; ++j)
                sum += B[p[i]][p[j]];
        best = max(best, sum);
        worst = min(worst, sum);
    } while (next_permutation(p.begin(), p.end()));
    return {best, worst};
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if(!(cin >> T)) return 0;
    while(T--){
        int n; cin >> n;
        vector<vector<int>> B(n, vector<int>(n));
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin >> B[i][j];
            }
        }
        // vector<int> dp_max(1 << n);
        // vector<int> dp_min(1 << n, inf);
        // dp_min[0] = 0;
        // for (int mask=0; mask < (1<<n); ++mask) {
        //     for (int x=0; x<n; ++x) if (!(mask&(1<<x))) {
        //         int val = 0;
        //         for (int b = 0; b < n; ++b) if (mask & (1<<b)) val += B[x][b];
        //         dp_max[mask | (1<<x)] = max(dp_max[mask | (1<<x)], dp_max[mask] + val);
        //         dp_min[mask | (1<<x)] = min(dp_min[mask | (1<<x)], dp_min[mask] + val);
        //     }
        // }
        // cout << dp_max[(1 << n) - 1] << ' ';
        // cout << dp_min[(1 << n) - 1] << '\n';
        // vector<ll> ans = solve(n, B);
        vector<ll> ans = brute_perm(n, B);
        cout << ans[0] << " " << ans[1] << "\n";

    }
    return 0;
}