If you are preparing for USACO or any other competitive programming, Codeforces is a good place to practice your programing. This article contains my Python and C++ solutions for the Brick Wall problem 1918A, a part of Codeforces Round 922 (Div 2).
Brick Wall problem
Please read the Brick Wall problem on Codeforces first. Make sure you understand the problem. Write the algorithm on paper before coding anything. For your algorithm, you can write either pseudocode or a diagrammatical flowchart.
Test cases
You can download this test case input and the expected output:
- brick_wall_1.in input file
- brick_wall_2.out output file
Programming Solution Logic
The first line of input is t, the number of moves.
The next t lines contain values for n and m.
The dimensions of the wall are n x m and the dimensions of each brick is 1 x 2.
If we stack the bricks horizontally, we can stack n bricks one on top of another. Now, think of this as a Tetris game where blocks of size 1 x 2 are falling down and you need to stack them. This is a modified version of Tetris where the all blocks are size 1 x 2.
The height of the wall is n. The height of the brick is 1. So, to stack enough bricks horizontally, we would need n * 1 bricks.
The width of the wall is m. The width of the brick is k, which is at least 2, from the problem description. If m is even, the number of bricks to be aligned horizontally will be m / 2. If m is odd, the number of bricks will be m / 2 and we will use only the integer part. In Python, we can use floor division and in C++, we use the std::floor() function.
The maximum stability of the wall is n * integer part of m / 2.
We will look at all five test cases in the the input file brick_wall_1.in
First Test Case
2 2
You can stack two bricks horizontally, each of size 1 x 2. The maximum stability is 2 * 2 / 2 = 2
Second Test Case
7 8
You can stack 28 bricks horizontally. The maximum stability is 7 * 8 / 2 = 28
Third Test Case
16 9
You can stack 64 bricks horizontally. The maximum stability is 16 * (9 // 2) = 16 * 4 = 64
Fourth Test Case
3 5
You can stack 6 bricks horizontally. The maximum stability is 3 * (5 // 2) = 3 * 2 = 6
Fifth Test Case
10000 10000
You can stack 50000000 bricks horizontally. The maximum stability is 10000 * (10000/2) = 10000 * 5000 = 50000000
Install Python or C++
If you do not have Python or C++, you should first install it. Codeforces uses Python 3.8 for evaluating your code. If you are using C++, they have versions 17 and 20.
My Python solution
This is my Python solution:
def num_of_bricks(n, m):
return n * (m // 2)
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
print(num_of_bricks(n, m))
In the Python code, we wrote a function num_of_bricks(n, m) which returns the maximum stability. You really do not even need a function for this, but I created it just to maintain a pattern. Localizing code inside functions also adds to the efficiency of the code.
Running the Python code
Run the Python code from your Terminal. I am using macOS, but you can use any Linux-based OS as well.
Here, I am running the program, which reads the input file with 5 test cases. Later, I also viewed the contents of the output file to compare the results.
$ cat brick_wall_1.in | python brick_wall.py
2
28
64
6
50000000
$ cat brick_wall_1.out
2
28
64
6
50000000
My C++ solution
This is my C++ solution:
#include <cmath>
#include <iostream>
using namespace std;
int num_of_bricks(int n, int m) {
return n * (floor(m / 2));
}
int main() {
int t;
int n, m;
cin >> t;
for (int i=0; i < t; i++) {
cin >> n >> m;
cout << num_of_bricks(n, m) << "\n";
}
}
In the C++ code, we used the same logic. We wrote a function num_of_bricks(int n, int m) which returns the maximum stability.
We read the variables in the input file using cin and print the output of num_of_bricks(n, m) using cout.
We can compare the printed output with the correct output in the .out file.
Point to note: The floor() function requires the cmath module. This is included because the std::floor() function cannot run on its own. And, because we declared using namespace std;, we can just call floor() instead of std::floor().
error: 'floor' has not been declared
If you get an error like this, it means that you have to include the cmath library.
Can't compile file:
program.cpp: In function 'int num_of_bricks(int, int)':
program.cpp:6:19: error: 'floor' has not been declared
6 | return n * (floor(m / 2));
| ^~~~~
SOLUTION:
Add this code:
#include <cmath>
Assuming you already have included using namespace std, using floor() should work.
For example,
floor(3/2)
should return:
1
Running the C++ code
Compile the C++ code from your Terminal. This command creates a.out.
$ g++ brick_wall.cpp
Now, run the test cases against a.out.
$ cat brick_wall_1.in | ./a.out
2
28
64
6
50000000
$ cat brick_wall_1.out
2
28
64
6
50000000
Submit your code
Submit your Python code and C++ code to Codeforces. When your code successfully passes all test cases, you will get a green "Accepted" message with the time taken.
Which is faster?
In the Codeforces submission page, these were the results:
Python 3 -- Time taken: 109 ms GNU C++20 (64) -- Time taken: 46 ms
I believe these programs took much longer because there was a lot of activity and submissions on Codeforces on that day.
What about software design, conventions and standards?
This is competitive programming. The goal is to complete the program with minimum effort and maximum efficiency. Using single character variables and ugly formatted code are okay, as long as the program runs and runs well within the scope. In the C++ code, we also shamelessly exited the program. That is fine, as long as your program works and you are able to submit it.
Later in life, when you start working in a professional environment, please beautify your ugly code, follow conventions, add comments and make your code readable. Readability and maintainability is key if you want to be a successful software engineer.
Conclusion
If there is anything you would like me to add to this article, feel free to comment below or contact me. Thanks.
Related Posts
If you have any questions, please contact me at arulbOsutkNiqlzziyties@gNqmaizl.bkcom. You can also post questions in our Facebook group. Thank you.