Tile Pattern

Problem: We have a 10^9×10^9 grid where each cell's color is determined by (i%n, j%n). We're given an n×n character matrix and need to answer q queries about the number of black cells in specified rectangular regions.

Solution: We use a 2D prefix sum approach to efficiently count black cells in any rectangle.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const int MAX_SIZE = 1024;
int gridSize;
ll prefixSum[MAX_SIZE][MAX_SIZE];

ll countBlackCells(int x, int y) {
    ll completeBlocks = (x / gridSize) * (y / gridSize) * prefixSum[gridSize][gridSize];
    ll partialBottomRight = prefixSum[x % gridSize][y % gridSize];
    ll partialBottomLeft = prefixSum[x % gridSize][gridSize] * (y / gridSize);
    ll partialTopRight = prefixSum[gridSize][y % gridSize] * (x / gridSize);
    
    return completeBlocks + partialBottomRight + partialBottomLeft + partialTopRight;
}

int main() {
    int queries;
    cin >> gridSize >> queries;
    
    vector<vector>> pattern(gridSize + 1, vector<char>(gridSize + 1));
    
    for (int i = 1; i <= gridSize; i++) {
        for (int j = 1; j <= gridSize; j++) {
            cin >> pattern[i][j];
            prefixSum[i][j] = (pattern[i][j] == 'B') + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
        }
    }
    
    while (queries--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x2++; y2++;
        
        ll result = countBlackCells(x2, y2) - countBlackCells(x1, y2) - countBlackCells(x2, y1) + countBlackCells(x1, y1);
        cout << result << '\n';
    }
}
</char></vector></vector></iostream>

Matrix Transformation Puzzle

Problem: Given two h×w matrices, determine if we can transform the first into the second using adjacent row and column swaps. If possible, find the minimum number of swaps required.

Solution: We genearte all possible row and column permutations of the second matrix and check if any matches the first matrix. The minimum number of swaps is determined by counting inversions in the permutation sequences.

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

int originalMatrix[6][6], targetMatrix[6][6];
int rowPermutations[250][6], colPermutations[250][6];
int rows, cols, totalRowPerms, totalColPerms;
bool visited[10];
int tempPermutation[10];

void generateRowPermutations(int current) {
    if (current > rows) {
        memcpy(rowPermutations[++totalRowPerms], tempPermutation, sizeof(tempPermutation));
        return;
    }
    
    for (int i = 1; i <= rows; i++) {
        if (!visited[i]) {
            visited[i] = true;
            tempPermutation[current] = i;
            generateRowPermutations(current + 1);
            visited[i] = false;
        }
    }
}

void generateColPermutations(int current) {
    if (current > cols) {
        memcpy(colPermutations[++totalColPerms], tempPermutation, sizeof(tempPermutation));
        return;
    }
    
    for (int i = 1; i <= cols; i++) {
        if (!visited[i]) {
            visited[i] = true;
            tempPermutation[current] = i;
            generateColPermutations(current + 1);
            visited[i] = false;
        }
    }
}

bool isValidPermutation(int rowPermIdx, int colPermIdx) {
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            if (originalMatrix[rowPermutations[rowPermIdx][i]][colPermutations[colPermIdx][j]] != targetMatrix[i][j]) {
                return false;
            }
        }
    }
    return true;
}

int countInversions(int permutation[], int size) {
    int inversions = 0;
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (permutation[i] > permutation[j]) {
                inversions++;
            }
        }
    }
    return inversions;
}

int main() {
    cin >> rows >> cols;
    
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            cin >> originalMatrix[i][j];
        }
    }
    
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            cin >> targetMatrix[i][j];
        }
    }
    
    // Check if matrices are already identical
    bool identical = true;
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            if (originalMatrix[i][j] != targetMatrix[i][j]) {
                identical = false;
                break;
            }
        }
        if (!identical) break;
    }
    
    if (identical) {
        cout << 0 << endl;
        return 0;
    }
    
    // Generate all row and column permutations
    memset(visited, false, sizeof(visited));
    generateRowPermutations(1);
    memset(visited, false, sizeof(visited));
    generateColPermutations(1);
    
    int minSwaps = 1e8;
    
    for (int i = 1; i <= totalRowPerms; i++) {
        for (int j = 1; j <= totalColPerms; j++) {
            if (isValidPermutation(i, j)) {
                int totalSwaps = countInversions(rowPermutations[i], rows) + countInversions(colPermutations[j], cols);
                if (totalSwaps < minSwaps) {
                    minSwaps = totalSwaps;
                }
            }
        }
    }
    
    if (minSwaps != 1e8) {
        cout << minSwaps << endl;
    } else {
        cout << -1 << endl;
    }
}
</algorithm></cstring></vector></iostream>

Socks Pairing Problem

Problem: We have n pairs of socks, each pair having the same color (color i for pair i). After losing k socks, we want to pair the remaining socks to minimize the sum of absolute differences between paired socks' colors.

Solution: We use a greedy approach with prefix sums. To odd k, we need to cnosider which sock to exclude to minimize the total strangeness.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int sockColors[300000];
ll minStrangeness;

int main() {
    int n, k;
    cin >> n >> k;
    
    for (int i = 0; i < k; i++) {
        cin >> sockColors[i];
    }
    
    sort(sockColors, sockColors + k);
    
    if (k % 2 == 0) {
        // Even number of lost socks - straightforward pairing
        minStrangeness = 0;
        for (int i = 1; i < k; i += 2) {
            minStrangeness += sockColors[i] - sockColors[i-1];
        }
    } else {
        // Odd number of lost socks - need to decide which sock to exclude
        vector<ll> prefixSum(k);
        
        // Calculate prefix sums for odd indices
        for (int i = 1; i < k; i += 2) {
            prefixSum[i+1] = sockColors[i] - sockColors[i-1];
            if (i > 1) {
                prefixSum[i+1] += prefixSum[i-1];
            }
        }
        
        // Initialize with the case where the last sock is excluded
        minStrangeness = prefixSum[k-1];
        
        ll currentSum = 0;
        // Try excluding each sock at odd positions
        for (int i = k-2; i >= 0; i -= 2) {
            currentSum += sockColors[i+1] - sockColors[i];
            ll candidate = currentSum + (i > 0 ? prefixSum[i-1] : 0);
            if (candidate < minStrangeness) {
                minStrangeness = candidate;
            }
        }
    }
    
    cout << minStrangeness << endl;
}
</ll></algorithm></vector></iostream>