To construct an n×n matrix where no two adjacent elements differ by exactly 1, we can implement a column-based shifting approach. For odd-numbered columns, shift all elements upward by one position, moving the overflow element to the bottom. This construction works for all cases except n=1, where no solution exists.

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

void constructMatrix() {
    int dimension;
    cin >> dimension;
    
    vector<vector<int>> grid(dimension + 1, vector<int>(dimension + 1));
    
    // Initialize matrix with sequential values
    for (int row = 1; row <= dimension; row++) {
        for (int col = 1; col <= dimension; col++) {
            grid[row][col] = (row - 1) * dimension + col;
        }
    }
    
    // Apply upward shift to odd columns
    for (int col = 1; col <= dimension; col++) {
        if (col % 2 == 1) {
            int temp = grid[1][col];
            for (int row = 2; row <= dimension; row++) {
                grid[row - 1][col] = grid[row][col];
            }
            grid[dimension][col] = temp;
        }
    }
    
    // Validate the construction
    for (int row = 1; row <= dimension; row++) {
        for (int col = 1; col < dimension; col++) {
            if (abs(grid[row][col] - grid[row][col + 1]) == 1) {
                cout << -1 << '\n';
                return;
            }
        }
    }
    
    // Output the result
    for (int row = 1; row <= dimension; row++) {
        for (int col = 1; col <= dimension; col++) {
            cout << grid[row][col] << (col == dimension ? '\n' : ' ');
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        constructMatrix();
    }
    return 0;
}

Modular Sum Pairs Counting

To count pairs (x,y) where (x+y) ≡ 0 (mod 5), we analyze the complementary remainders of x and y modulo 5. For each value of x, we need to find y such that their remainders sum to 5 or 0.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int rows, cols;
    cin >> rows >> cols;
    
    int remainderCount[5] = {0};
    for (int j = 1; j <= cols; j++) {
        remainderCount[j % 5]++;
    }
    
    int64 totalPairs = 0;
    for (int i = 1; i <= rows; i++) {
        int neededRemainder = (5 - (i % 5)) % 5;
        totalPairs += remainderCount[neededRemainder];
    }
    
    cout << totalPairs << '\n';
    return 0;
}

Index-Sum Product Pairs

We need to find pairs (i,j) where a[i] × a[j] = i + j. By sorting the array elements with their original indices and using a two-pointer approach with early termination, we achieve O(n log n) complexity. The inner loop breaks when the product exceeds 2n.

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

void findPleasantPairs() {
    int size;
    cin >> size;
    
    vector<pair<int64, int>> elements(size + 1);
    for (int i = 1; i <= size; i++) {
        int64 value;
        cin >> value;
        elements[i] = {value, i};
    }
    
    sort(elements.begin() + 1, elements.end());
    
    int64 result = 0;
    for (int i = 1; i <= size; i++) {
        auto [currentValue, currentIndex] = elements[i];
        for (int j = 1; j < i; j++) {
            auto [prevValue, prevIndex] = elements[j];
            if (currentValue * prevValue > 2 * size) break;
            if (currentValue * prevValue == currentIndex + prevIndex) {
                result++;
            }
        }
    }
    
    cout << result << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        findPleasantPairs();
    }
    return 0;
}

Friendship Interval Queries

Using a sliding window approach with a multiset to track forbidden positions, we can efficiently count valid intervals. For each left pointer, we extend the right pointer as far as possible while maintaining the constraint that no friendship pair exists within the current window.

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

void processIntervals() {
    int vertices, edges;
    cin >> vertices >> edges;
    
    vector<vector<int>> adjacency(vertices + 1);
    for (int i = 0; i < edges; i++) {
        int u, v;
        cin >> u >> v;
        if (u > v) swap(u, v);
        adjacency[u].push_back(v);
    }
    
    int64 totalIntervals = 0;
    multiset<int> restrictions;
    
    for (int left = 1, right = 0; left <= vertices; left++) {
        while (right + 1 <= vertices && !restrictions.count(right + 1)) {
            right++;
            for (int neighbor : adjacency[right]) {
                restrictions.insert(neighbor);
            }
        }
        
        int64 windowSize = right - left + 1;
        totalIntervals += windowSize;
        
        for (int neighbor : adjacency[left]) {
            restrictions.erase(restrictions.lower_bound(neighbor));
        }
    }
    
    cout << totalIntervals << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        processIntervals();
    }
    return 0;
}

Binary Matrix Equalization

To make all rows have the same number of 1s, we first check if the total number of 1s is divisible by n. If possible, we greedi transfer excess 1s from rows above the average to deficient rows below the average, minimizing operations by processing column by column.

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

void equalizeBinaryMatrix() {
    int rows, cols;
    cin >> rows >> cols;
    
    vector<vector<int>> matrix(rows, vector<int>(cols));
    vector<int> oneCount(rows, 0);
    int totalOnes = 0;
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            cin >> matrix[i][j];
            oneCount[i] += matrix[i][j];
        }
        totalOnes += oneCount[i];
    }
    
    if (totalOnes % rows != 0) {
        cout << -1 << '\n';
        return;
    }
    
    int target = totalOnes / rows;
    vector<array<int, 3>> operations;
    
    for (int j = 0; j < cols; j++) {
        vector<int> surplus, deficit;
        
        for (int i = 0; i < rows; i++) {
            if (oneCount[i] > target && matrix[i][j] == 1) {
                surplus.push_back(i);
            } else if (oneCount[i] < target && matrix[i][j] == 0) {
                deficit.push_back(i);
            }
        }
        
        while (!surplus.empty() && !deficit.empty()) {
            int from = surplus.back();
            int to = deficit.back();
            operations.push_back({from + 1, to + 1, j + 1});
            oneCount[from]--;
            oneCount[to]++;
            surplus.pop_back();
            deficit.pop_back();
        }
    }
    
    cout << operations.size() << '\n';
    for (auto [from, to, col] : operations) {
        cout << from << ' ' << to << ' ' << col << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        equalizeBinaryMatrix();
    }
    return 0;
}

Song Shuffling with State DP

This problem requires finding the minimum number of songs to remove sothat the remaining songs form a valid playlist. Using bitmask DP combined with Union-Find to ensure connectivity, we check all possible subsets of songs and find the minimal removals that allow a Hamiltonian path through the remaining graph.

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

class UnionFind {
private:
    vector<int> parent, componentSize;
public:
    UnionFind(int n = 0) {
        if (n > 0) init(n);
    }
    
    void init(int n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        componentSize.assign(n, 1);
    }
    
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        componentSize[x] += componentSize[y];
        parent[y] = x;
        return true;
    }
    
    int size(int x) {
        return componentSize[find(x)];
    }
};

void solveShuffling() {
    int songCount;
    cin >> songCount;
    
    unordered_map<string, int> genreMap;
    int genreCounter = 0;
    vector<pair<int, int>> songs;
    
    for (int i = 0; i < songCount; i++) {
        string genre1, genre2;
        cin >> genre1 >> genre2;
        
        if (!genreMap.count(genre1)) {
            genreMap[genre1] = genreCounter++;
        }
        if (!genreMap.count(genre2)) {
            genreMap[genre2] = genreCounter++;
        }
        
        songs.emplace_back(genreMap[genre1], genreMap[genre2]);
    }
    
    vector<vector<int>> compatible(songCount, vector<int>(songCount));
    for (int i = 0; i < songCount; i++) {
        for (int j = 0; j < i; j++) {
            if (songs[i].first == songs[j].first || 
                songs[i].second == songs[j].second) {
                compatible[i][j] = compatible[j][i] = 1;
            }
        }
    }
    
    int minRemovals = songCount - 1;
    
    for (int mask = 0; mask < (1 << songCount); mask++) {
        int removedCount = __builtin_popcount(mask);
        if (removedCount >= minRemovals) continue;
        
        vector<int> remainingSongs;
        for (int i = 0; i < songCount; i++) {
            if (!(mask >> i & 1)) {
                remainingSongs.push_back(i);
            }
        }
        
        int remaining = songCount - removedCount;
        vector<vector<int>> graph(remaining);
        UnionFind uf(remaining);
        
        for (int i = 0; i < remaining; i++) {
            for (int j = 0; j < remaining; j++) {
                if (compatible[remainingSongs[i]][remainingSongs[j]]) {
                    graph[i].push_back(j);
                    uf.unite(i, j);
                }
            }
        }
        
        if (uf.size(0) != remaining) continue;
        
        const int INF = 1e9;
        vector<vector<int>> dp(1 << remaining, vector<int>(remaining, INF));
        
        for (int i = 0; i < remaining; i++) {
            dp[1 << i][i] = 1;
        }
        
        bool found = false;
        for (int state = 1; state < (1 << remaining) && !found; state++) {
            for (int last = 0; last < remaining && !found; last++) {
                if (!(state >> last & 1)) continue;
                if (dp[state][last] == INF) continue;
                
                for (int next : graph[last]) {
                    if (state >> next & 1) continue;
                    
                    int newState = state | (1 << next);
                    dp[newState][next] = min(dp[newState][next], dp[state][last] + 1);
                    
                    if (newState == (1 << remaining) - 1 && dp[newState][next] == remaining) {
                        minRemovals = removedCount;
                        found = true;
                        break;
                    }
                }
            }
        }
    }
    
    cout << minRemovals << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        solveShuffling();
    }
    return 0;
}