To solve this problem efficiently, consider how elements are positioned in the matrix and how to avoid double-counting.

The problem requires us to identify and sum specific elements in an n × n matrix where n is odd. The elements to be considered are:

• Elements of the main diagonal: These are the elements where the row index equals the column index, i.e., (i, i).
• Elements of the secondary diagonal: These are the elements where the sum of the row index and column index equals n − 1, i.e., (i, n − 1 − i).
• Elements of the middle row: This is the row that has exactly ((n − 1) / 2) rows above and below it.
• Elements of the middle column: This is the column that has exactly (n − 1) / 2 columns to the left and right of it.

n = int(input())  
matrix = []  
for _ in range(n):  
    inp = [int(i) for i in input().split()]  
    matrix.append(inp)  

visited = set()  
mid_row = mid_col = n // 2  
ans = 0  

for i in range(n):  
    # Main diagonal  
    if (i, i) not in visited:  
        ans += matrix[i][i]  
        visited.add((i, i))  

    # Secondary diagonal  
    if (i, n - 1 - i) not in visited:  
        ans += matrix[i][n - 1 - i]  
        visited.add((i, n - 1 - i))  

    # Middle row  
    if (mid_row, i) not in visited:  
        ans += matrix[mid_row][i]  
        visited.add((mid_row, i))  

    # Middle column  
    if (i, mid_col) not in visited:  
        ans += matrix[i][mid_col]  
        visited.add((i, mid_col))  

print(ans)

Time Complexity = O(n)

'''
Basic Properties
 <> i == j --> main diagonal
 <> i + j == ( n - 1)  --> secondary diagonal
 <> i == n//2  -->  middle row
 <> j == n//2  --> middle column
'''
def solve():
    matrix = []
    n = int(input())
    for i in range(n):
        row = list(map(int , input().split()))
        matrix.append(row)

    ans = 0
    for i in range(n):
        for j in range(n):
            if i == j or i == n//2  or j == n//2 or i + j == n - 1 :
                ans += matrix[i][j]
             
    print(ans)
                
    


solve()

Time Complexity = O(n * n)

We need to split the string $$$s$$$ into two non-empty parts $$$a$$$ and $$$b$$$ such that the sum of distinct characters in both parts is maximized. The key observation here is that we can efficiently track the distinct characters in both parts as we move through the string. We can solve this problem by iterating over each character of the string and keeping track of two sets:

• One set for characters in the left part (which means for $$$a$$$).
• One set for characters in the right part (which means for $$$b$$$).

• Start by putting all characters in the right part of the string.
• Iterate through each character in the string, shifting one character at a time from the right part to the left part, and updating the distinct character counts for both parts.
• At each step, compute the sum of distinct characters in both parts and keep track of the maximum sum observed.

from collections import Counter

def max_distinct_split(s):
    right_counter = Counter(s)  # Tracks character counts in the right part
    left_counter = Counter()    # Tracks character counts in the left part
    max_distinct_sum = 0        # Stores the maximum sum of distinct characters

    for char in s:
        # Move character from right part to left part
        left_counter[char] += 1
        right_counter[char] -= 1

        # If a character count in the right part becomes zero, remove it
        if right_counter[char] == 0:
            del right_counter[char]

        # Calculate the sum of distinct characters in both parts
        distinct_sum = len(left_counter) + len(right_counter)
        max_distinct_sum = max(max_distinct_sum, distinct_sum)

    return max_distinct_sum


t = int(input())

for _ in range(t):
    n = int(input())
    s = input()
    print(max_distinct_split(s))

Let's rotate the grid by 0∘, 90∘, 180∘, and 270∘, and mark all cells that map to each other under these rotations. For example, for 4×4 and 5×5 grids, the grid must have the following patterns, the same letters denoting equal values:

In general, we can rotate the grid by 0∘, 90∘, 180∘, and 270∘ and see which cells need to have equal values by seeing the positions which each cell maps to.

Now to solve the problem, we consider each equal value (each of the letters a, b, c, ... in the above figures) independently, and consider the minimum number of moves to make them all 0 or all 1. The answer is the total across all values.

The time complexity is O($$$ n^2 $$$). And the space complexity is O($$$ 1 $$$).

Let's consider the upper triangular quarter of the grid. If we are at $$$(i, j)$$$, after rotating it by 0∘, 90∘, 180∘, and 270∘, the bit at this position is replaced by the one at $$$(j, n - i - 1)$$$, $$$(n - i - 1, n - j - 1)$$$, $$$(n - j - 1, i)$$$ respectively. From these four positions we count the numbers of zeros and ones and take the minimum. We sum those minimums for all positions in the upper triangular quarter of the grid.

t = int(input())
for _ in range(t):

    n = int(input())
    
    grid = []
    for i in range(n):
        grid.append(input())
    

    min_ops = 0

    for row in range(n//2):
        for col in range(row, n - row - 1):
            
            zero_one_count = [0, 0]

            zero_one_count[int(grid[row][col])] += 1
            zero_one_count[int(grid[col][n - row - 1])] += 1
            zero_one_count[int(grid[n - row - 1][n - col - 1])] += 1
            zero_one_count[int(grid[n - col - 1][row])] += 1

            min_ops += min(zero_one_count)

    print(min_ops)