Codeforces Maximum Multiple Sum 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 Maximum Multiple Sum problem 1985B, a part of Codeforces Round 952 (Div. 4).

Maximum Multiple Sum problem

Please read the Maximum Multiple Sum 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:

• maximum_multiple_sum_1.in input file
• maximum_multiple_sum_1.out output file

Programming Solution Logic

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

The remaining t lines contain a single integer, n. Your program should find an integer x which can be anywhere from 2 up to n, inclusive, so that the sum of multiples of x are maximized. The value of the highest multiple should be less than or equal to n.

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

1. Write a function with input parameters (n, x), which finds the multiples of x and returns the sum of these multiples.
2. Define two variables, optimal, which holds the optimal value of x (the answer for this test case) and optimal_sum, which contains the maximum sum for this value of x. Initialize the values of both to 0.
3. Start a loop cycling with values from 2 through n; let x be the iterator.
4. In this loop, get the sum of the multiples by calling the function written in (1) and passing the values of x and n.
5. If this sum is greater than the value in optimal_sum, then update optimal_sum with the new sum. Also update optimal with the value of x.
6. End the loop started in (5).
7. Print the value of optimal. That is the answer for each test case.

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

First Test Case

When n = 3, the answer is 3.

We will find the sum when x = 2 and x = 3.

1. When x = 2, the multiples of x greater or equal to n are 2. So, the sum is 2.
2. When x = 3, the multiples of x greater or equal to n are 3. So, the sum is 3.

The greatest (greater) sum is 3, so the value of x corresponding to it is 3. Answer = 3.

Second Test Case

When n = 15, the answer is 2.

We will find the sum when x = 2, x = 3, and so on until x = 15.

The greatest sum is 56, so the optimal value of x is 2. Answer is 2.

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

maximum_multiple_sum.py

# https://codeforces.com/problemset/problem/1985/B

# line 1    : t = number of test cases
# line 2    : n

# Return sum of multiples of x that are <= n
def sum_multiples_of(x, n):
    sum_multiples = 0
    i = 1
    while x * i <= n:
        sum_multiples += x * i
        i += 1
    return sum_multiples

# Main function
t = int(input())
for _ in range(t):
    n = int(input())
    x = 2
    optimal = x
    optimal_sum = 0
    while x <= n:
        sum_multiples = sum_multiples_of(x, n)
        if sum_multiples > optimal_sum:
            optimal = x
            optimal_sum = sum_multiples
        x += 1
    print(optimal)

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 maximum_multiple_sum_1.in | python maximum_multiple_sum.py 
3
2

$ cat maximum_multiple_sum_1.out 
3
2

My C++ solution

maximum_multiple_sum.cpp

This is my C++ solution:

#include <iostream>

using namespace std;

// Return sum of multiples of x that are <= n
int sum_multiples_of(int x, int n) {
    int sum_multiples = 0;
    int i = 1;
    while (x * i <= n) {
        sum_multiples += x * i;
        i += 1;
    }
    return sum_multiples;
}

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

    for (int i=0; i < t; i++) {
        int n;
        cin >> n;
        int x = 2;
        int optimal = x;
        int optimal_sum = 0;
        while (x <= n) {
            int sum_multiples = sum_multiples_of(x, n);
            if (sum_multiples > optimal_sum) {
                optimal = x;
                optimal_sum = sum_multiples;
            }
            x ++;
        }
        cout << optimal << endl;
    }
}

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++ maximum_multiple_sum.cpp

Now, run the test cases against a.out.

$ cat maximum_multiple_sum_1.in | ./a.out 
3
2

$ cat maximum_multiple_sum_1.out 
3
2

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. But this may vary depending 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.