Codeforces 50A: Domino Piling Solution & 1-Line Math Trick (C++)

by

Welcome to Episode 4 of our Competitive Programming for Beginners Challenge! Today, we are looking at a problem that perfectly illustrates why you should always stop and think about the math before you start typing code.

We are solving Domino Piling (Codeforces 50A). At first glance, this looks like a complex spatial puzzle requiring 2D matrices and nested loops. In reality, it can be solved with a single line of basic arithmetic. Let’s break down the logic.

The Problem Statement

You are given a rectangular board of M x N squares. You also have an unlimited number of standard domino pieces of 2 X 1 squares. You are allowed to rotate the pieces.

You need to place as many dominoes as possible on the board so that no two dominoes overlap and no domino crosses the edges of the board.

Input:

A single line containing two integers M and N — the sizes of the board in squares.

(Constraints: 1 <= M, N <= 16)

Output: Print a single integer — the maximum number of dominoes that can be placed.

The Logic & Theory Breakdown (The Beginner Trap)

The biggest trap beginners fall into is trying to simulate the board. They create a 2D array (e.g., board[M][N]) and try to write loops to check for empty spaces. This is overcomplicating the problem!

Let’s look at the pure math:

  1. The Area: A board of size M X N has exactly M X N total squares. (e.g., A 3 X 3 board has 9 total squares).
  2. The Domino: Every single domino, whether placed horizontally or vertically, takes up exactly 2 squares.
  3. The Solution: To find the maximum number of dominoes that can fit, we just divide the total number of squares by 2!
    • Maximum Dominoes = (M * N) / 2

What about boards with an odd number of squares?

If we have a 3 X 3 board, the total area is 9.

9 / 2 = 4.5

We can’t place half a domino. But because we are using integer division in C++, the decimal is automatically truncated (dropped). The calculation 9 / 2 evaluates perfectly to 4, leaving the 1 remaining square empty just as the problem requires.

C++ Code Implementation

Here is the incredibly short and optimized C++ solution for the Domino Piling problem.

#include <iostream>

using namespace std;

int main() {
    // Fast I/O for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int m, n;
    cin >> m >> n; // Read board dimensions

    // Calculate total squares and divide by 2
    int max_dominoes = (m * n) / 2;

    cout << max_dominoes << "\n";

    return 0;
}

Complexity Analysis

  • Time Complexity: O(1) constant time. We are performing a single mathematical multiplication and division, regardless of how large the board gets.
  • Space Complexity: O(1) auxiliary space. We only store two integer variables (m and n), so the memory footprint is practically zero.

Key Takeaways

  • Don’t Rush to Simulate: If a problem asks for a “maximum number” or a “count,” look for a mathematical formula before trying to simulate the actual physical process with arrays.
  • Integer Division is Powerful: In C++, dividing two integers automatically drops the remainder. This is a feature, not a bug, and is incredibly useful for finding pairs!

Conclusion

Congratulations! You’ve learned how to bypass complex data structures by finding the mathematical root of a problem. If you want to see exactly how this spatial logic looks on the whiteboard, watch the full video tutorial below!

https://www.youtube.com/watch?v=MUlhy3IQt0c

Hit the “Join” button on our YouTube channel to become a Snippet Supporter! You’ll get instant access to our downloadable ad-free Master Notes, featuring the complete code and step-by-step logic breakdown so you can confidently review before your placement drives. Link to join our Youtube Channel Simple Snippets : https://www.youtube.com/channel/UCRIWTSgd7hGtZhx4RYoASEg/join

Leave a Comment