Problem A - 4

Question

With (n) horizontal lines and (m) vertical lines drawn on a plane, how many axis-aligned rectangles are formed that contain no interior lines?

Solution

Consider each dimension independent.

Along any straight line, (n) distinct points partition the line into (n - 1) segments. These segments serve as the edges of our rectangles.

The total number of rectangles equals the product of segments in each direction:

[ (n - 1) \times (m - 1) ]

Extension 1: If counting all possible rectangles regardless of interior lines, the formula becomes:

[ \binom{n}{2} \times \binom{m}{2} ]

Extension 2: Computing the sum of areas of all rectangles involves the classic distance sum problem:

[ \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} (x_j - x_i) \times \sum_{i = 1}^{n} \sum_{j = i + 1}^{m} (y_j - y_i) ]

These two factors are independent and can each be computed in (O(n)) time using combinatorial transformations.

Problem B - "xx...x" (String Reduction)

Question

Given a string (s) with (|s| \geq 3), output a new string composed of: the first character, followed by (|s| - 2) as a number, followed by the last character.

Solution

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    if (cin >> s) {
        cout << s.front() << (s.length() - 2) << s.back() << '\n';
    }
    return 0;
}

The logic is straightforward: extract the boundaries and display the middle count.

Problem C - Grid Comprsesion

Question

Given a sequence of (N) positive integers, can they be rearranged such that for every adjacent pair (a_i, a_{i+1}), the product is divisible by 4?

Solution

Define three categories based on divisibility by powers of 2:

For a product to be divisible by 4, each adjacent pair must satisfy one of: at least one element is type (\mathbb{4}), or both elements are type (\mathbb{2}).

Case 1: When (cnt(\mathbb{2}) = 0)

Arrange as (\mathbb{1}\mathbb{4}\mathbb{1}\mathbb{4}\cdots). This requires:

[ cnt(\mathbb{4}) \geq cnt(\mathbb{1}) - 1 ]

Case 2: When (cnt(\mathbb{2}) > 0)

Place (\mathbb{2})s in the middle, with (\mathbb{4})s flanking each (\mathbb{1}). This requires:

[ cnt(\mathbb{4}) \geq cnt(\mathbb{1}) ]

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    if (!(cin >> n)) return 0;
    
    int odd = 0, half = 0, quarter = 0;
    
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        if (val % 4 == 0) {
            ++quarter;
        } else if (val % 2 == 0) {
            ++half;
        } else {
            ++odd;
        }
    }
    
    bool feasible = false;
    
    if (half == 0) {
        feasible = (quarter >= odd - 1);
    } else {
        feasible = (quarter >= odd);
    }
    
    cout << (feasible ? "Yes" : "No") << '\n';
    return 0;
}

Problem D - Coloring

Question

Fill an (H \times W) matrix with (N) colors (color (i) occupies (a_i) cells), such that cells of the same color form 4-connected components.

Solution

A snake (zigzag) fill pattern guarantees that consecutive cells of each color remain connected.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int H, W, N;
    cin >> H >> W >> N;
    
    vector<vector<int>> grid(H, vector<int>(W, 0));
    
    int row = 0, col = 0;
    int dir = 1;
    
    for (int color = 1; color <= N; ++color) {
        int count;
        cin >> count;
        
        for (int k = 0; k < count; ++k) {
            grid[row][col] = color;
            col += dir;
            
            if (col < 0 || col >= W) {
                ++row;
                dir = -dir;
                col += dir;
            }
        }
    }
    
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cout << grid[i][j] << (j == W - 1 ? '\n' : ' ');
        }
    }
    
    return 0;
}

The snake patttern naturally connects adjacent cells horizontally while switching rows, ensuring each color's cells form a single contiguous component.