Problem Link

Approach:

For this problem, we need to calculate the perimeter of a shape formed by moving right and up. The perimeter can be determined using the formula: ((steps_up + width) + (steps_right + width)) * 2. This accounts for the outer boundaries of the shape.

Solution Code:

#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 2000005;

void solve() {
    int size, width;
    cin >> size >> width;
    
    ll total_x = width;
    ll total_y = width;
    
    for (int i = 1; i < size; i++) {
        int x, y;
        cin >> x >> y;
        total_x += x;
        total_y += y;
    }
    
    cout << 2 * (total_x + total_y) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases = 1;
    cin >> test_cases;
    while (test_cases--) {
        solve();
    }
    
    return 0;
}
</iostream>

B. Find the Permutation

Problem Link

Approach:

The task is to construct a permutation based on a given adjacency matrix. The sorting rule is: if two elements are connected (adjacency matrix value is 1), the smaller element comes first; if not connected, the larger element comes first.

Soltuion Code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 5005;

int adjacency[MAXN][MAXN];

void solve() {
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            char c;
            cin >> c;
            adjacency[i][j] = c - '0';
        }
    }
    
    vector<int> result(n);
    for (int i = 0; i < n; i++) {
        result[i] = i + 1;
    }
    
    sort(result.begin(), result.end(), [&](int a, int b) {
        if (adjacency[a][b] == 1) {
            return a < b;
        }
        return a > b;
    });
    
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases = 1;
    cin >> test_cases;
    while (test_cases--) {
        solve();
    }
    
    return 0;
}
</int></algorithm></vector></iostream>

C. Palindromic Subsequences

Problem Link

Approach:

This is a construction problem where we need to create a sequence with a specific property regarding palindromic subsequences. The general approach is to construct a sequence like [1, 2, 3, ..., 1, 2], but we need a special case when n = 6.

Solution Code:

#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 2000005;

void solve() {
    int n;
    cin >> n;
    
    if (n == 6) {
        cout << "1 1 2 3 1 2" << endl;
        return;
    }
    
    for (int i = 1; i <= n - 2; i++) {
        cout << i << " ";
    }
    cout << "1 2" << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases = 1;
    cin >> test_cases;
    while (test_cases--) {
        solve();
    }
    
    return 0;
}
</iostream>