Codeforces osu!mania Problem in Python and C++

If you are preparing for USACO, ACSL or any other competitive programming, Codeforces is a good place to practice your programing. This article contains my Python and C++ solutions for the osu!mania problem 2009B, a part of Codeforces Round 971 (Div. 4).

osu!mania problem

Please read the osu!mania 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 draw a flowchart.

Test cases

You can download this test case input and the expected output:

• osu_mania_1.in input file
• osu_mania_1.out output file

Programming Solution Logic

The first line of input is t, the number of test cases.

For each test case, the first line is n, and the next n subsequent number of lines contain a 4-character string with '.' or '#'. For all these n test cases corresponding to a single test, the output is a single line containing n integers with position of the the character '#'.

The algorithm we can come up will be something like this:

1. Read the number of test cases t.
2. Start a loop for each test case.
3. The first line of each test case is n.
4. Create an empty list notes.
5. Read the next n lines and store each line as a string in notes.
6. Reverse the list notes because we have to display the count from last to first.
7. Create an empty list ans.
8. Read each string in notes and store the position of '#' in ans.
9. Print all the values of ans separating each value with a single space.

We will look at the test cases in the the input file osu_mania_1.in and compare the answers to the ones in the output file osu_mania_1.out .

First Test Case

4
#...
.#..
..#.
...#

Here, n = 4. We capture the 4 subsequent strings in each line and store them in list variable notes.

We reverse the list notes. This is how notes looks like now:

The output will be:

4 3 2 1

Second Test Case

2
.#..
.#..

Here, n = 2. We capture the 2 subsequent strings and store them in list variable notes.

After reversing notes, we get this:

The output will be:

2 2

Third Test Case

1
...#

The third test case has only one line. After reversing notes (we don't, but that's in our algorithm anyway), we get this:

The output will be:

4

For all the three test cases, our algorithm will give the correct expected output.

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

osu_mania.py

# Codeforces Round 971 (Div. 4)
# https://codeforces.com/contest/2009/problem/B
# https://aruljohn.com/blog/osu-mania-problem/

t = int(input())
for _ in range(t):
    n = int(input())
    notes = []
    for _ in range(n):
        notes.append(input())
    notes.reverse()
    ans = []
    for note in notes:
        ans.append(note.find('#') + 1)
    print(*ans)

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 4 test cases. Later, I also viewed the contents of the output file to compare the results.

$ cat osu_mania_1.in | python osu_mania.py 
4 3 2 1 
2 2 
4 


$ cat maximum_multiple_sum_1.out 
4 3 2 1 
2 2 
4 

My C++ solution

osu_mania.cpp

This is my C++ solution:

#include <iostream>
#include <vector>

using namespace std;

// Main function
int main() {
    int t;
    cin >> t;

    for (int i=0; i < t; i++) {
        int n;
        string note;
        cin >> n;
        vector<string> notes;
        for (int j=0; j < n; j++) {
            cin >> note;
            notes.push_back(note);
        }
        reverse(notes.begin(), notes.end());
        for (int j=0; j < n; j++) {
            int notepos = notes[j].find('#');
            cout << notepos + 1 << " ";
        }
        cout << "\n";
    }
}

In the C++ code, we used the same logic.

Running the C++ code

Compile the C++ code from your Terminal. This command creates a.out.

$ g++ osu_mania.cpp

Now, run the test cases against a.out.

$ cat osu_mania_1.in | ./a.out 
4 3 2 1 
2 2 
4 

$ cat maximum_multiple_sum_1.out 
4 3 2 1 
2 2 
4 

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: 62 ms
GNU C++20 (64)  -- Time taken: 46 ms

The C++ program was 16 ms faster. This may vary on your submissions because this depends on how busy the server was at the time of submission.

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. 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.