If you are preparing for USACO or any other competitive programming, Codeforces is a good place to practice your programming. This article contains my Python and C++ solutions for the Make it White problem 1927A, a part of Codeforces Round 923 (Div. 3). This was posted on February 6, 2024.
Make it White problem
Please read the Make it White problem on Codeforces first. Make sure you understand the problem fully. 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:
- make_it_white_1.in input file
- make_it_white_1.out output file
Programming Solution Logic
The first line of input is t, the number of test cases.
The first line of each test case contains n, the length of the strip.
The second line of each test case contains s, the string.
We will look at all five test cases in the the input file make_it_white_1.in and compare the answers to the ones in the output file
For each string, we have to find the minimum length of continuous segment of cells. Looking at it in a logical way, if we find the first occurrence of B in the strong and last occurrence of B, we can paint those two segments and all segments in between. That gives the minimum length of continuous segment of cells.
First Test Case
The string is:
WBBWBW
The minimum set of segment of cells is highlighted here: WBBWBW and we can see that it is 4 cells. By painting these 4 cells, all n cells will become white.
Second Test Case
B
There is only 1 cell here and it is a B. By painting this one cell, the whole group of 1 cell will become white.
Third Test Case
WB
The minimum set of segment of cells is: WB and we can see that it is 1 cell. By painting this 1 cell, all n cells will become white.
Eighth Test Case
WBWBWWWBW
The minimum set of segment of cells is: WBWBWWWBW and we can see that it is 7 cells. By painting these 7 cell, all n cells will become white.
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 solutions
I have two Python solutions here, the first one using the for loop the traditional way and the second program using Python's find() and rfind() string methods.
Python code using for loops
def num_painted_segments(s):
lt = 0
rt = len(s)
for x in s:
if x == 'B':
break
lt += 1
for x in s[::-1]:
if x == 'B':
break
rt -= 1
return rt - lt
# Main function
t = int(input())
for _ in range(t):
n = int(input())
s = input()
print(num_painted_segments(s))
In this Python code, we wrote a function num_painted_segments(s) which accepts the string and returns the minimum number of continuous cell segments. This function performs two loops, one to find the first occurrence and index of B and the second to find the last occurrence and index of B. It then returns the difference between these two indices.
Faster Python code
def num_painted_segments(s):
return s.rfind('B') - s.find('B') + 1
# Main function
t = int(input())
for _ in range(t):
n = int(input())
s = input()
print(num_painted_segments(s))
In this Python code, we wrote a function num_painted_segments(s) which accepts the string and returns the minimum number of continuous cell segments. This function is much shorter and uses the find() string method to find the index of the first occurrence of B and rfind() to find the index of the last occurrence of B. The difference between these two numbers + 1 will give the number of cell segments.
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 make_it_white_1.in | python make_it_white.py
4
1
1
2
4
6
4
7
$ cat make_it_white_1.out
4
1
1
2
4
6
4
7
My C++ solution
This is my C++ solution:
#include <iostream>
#include <string>
using namespace std;
unsigned int num_painted_segments(string s) {
return s.rfind('B') - s.find('B') + 1;
}
int main() {
int t;
int n;
string s;
cin >> t;
for (int i=0; i < t; i++) {
cin >> n >> s;
cout << num_painted_segments(s) << "\n";
}
}
In the C++ code, we used the same logic. We wrote a function num_painted_segments(string s) which returns the minimum number of segments. In this function, we use the string methods find() and rfind() to find the first and last occurrences of B. We then return the difference + 1. That is our answer.
We read the variables in the input file using cin and print the output of num_painted_segments(s) using cout.
We can compare the printed output with the correct output in the .out file.
The string methods find() and rfind() are in the string library, so we import it at the top.
#include <string>
Running the C++ code
Compile the C++ code from your Terminal. This command creates a.out.
$ g++ make_it_white.cpp
Now, run the test cases against a.out.
$ cat make_it_white_1.in | ./a.out
4
1
1
2
4
6
4
7
$ cat make_it_white_1.out
4
1
1
2
4
6
4
7
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: 93 ms GNU C++20 (64) -- Time taken: 46 ms
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.