Tag: contest

Categories
Best Practices Programming Tutorial

Best Practices Part 1: Understand the Basics

Best Practices for STEM Loyola Programming Challenges

Contents:

Overview

This is a multi-part tutorial on participating in the STEM Loyola Programming Challenges. The objective of this series of tutorials is to equip you with the necessary tools to become competitive as you participate in future challenges.

“Give me six hours to chop down a tree and I will spend the first four sharpening the axe“

Abraham Lincoln

This series will highlight the tools that you will need such as programming languages, data structures, algorithms, and other principles/tricks. In this part, we will provide an overview of the automatic challenges grader and a good method of approaching solving the problems.

Understand the Automatic Challenges Grader

Since all programming challenges are automatically graded, it matters to understand the system. The grader works by accepting the source code you upload (e.g. file.cpp, file.java, file.c), compile the source code, execute the program, supply it with inputs, and observe if the program produces the correct output.

Suppose a problem requires you to input two positive integers less than a million and compute the sum of the two numbers. One of the correct ways to solve this problem is shown in the C++ source code below.

#include <iostream>
<iostream>using namespace std;

int main(){
    int A, B;
    cin >> A >> B;

    cout << A + B << endl;

    return 0;
}</iostream>Code language: PHP (php)

Note the following from the above source code:

  1. When inputting the two number into the program, we did not have to request the compiler to input the two numbers like cout << Enter the two numbers: ";
    This is because the compiler will automatically know to supply the two numbers and more importantly, anything you display on the standard output will be treated as your answer (resulting in the grader marking your program output as wrong).
  2. Similarly, when outputting the sum of the two numbers, we only displayed the sum without additional words like cout << "Sum is: " which will cause the grader to mark your answer as wrong. Because if the two numbers are 5 and 6, their sum is “11” and not “Sum is: 11“
  3. The program ends with return 0;. Your program should run only once and return zero at the end. Ending your program with return main(); will result in time-limit error.
  4. Since the problem states that the two numbers are positive and less than a million, we chose int because we are sure a million can fit in the int data type. If the two numbers were bigger (say 5 billion), then we would have to select a bigger data type like long long int. Refer to our Programming and Data Structures in C++ guideline for an in-depth treatise of data structure.

Think of Problem’s Special Cases

Your submitted solution will be tested against five or more different test cases. Different test cases are used to ensure that your program has covered different special cases.

For instance, suppose the problem is to input two numbers and find the quotient when the first number is divided by the second. A basic solution can look like the source code below.

#include<iostream>

using namespace std;

int main(){
    float A, B;
    cin >> A >> B;

    cout << A / B << endl;

    return 0;
}
Code language: PHP (php)

However, the above program will crash when the second number is zero. This is due to the fact that in Mathematics, dividing a number by zero is undefined. What will happen exactly during your program’s execution depends on the compiler that was used, some compilers have protection against such cases and will produce inf as the answer. Some compilers will just result in run-time error and your program crashing.

To become a better programmer is to always think of such special cases that may crash your program and write your code defensively. A better solution for the above problem is as follows.

#include<iostream>
#include<cmath>

using namespace std;

int main(){
    const float INFINITESIMAL = 0.000001;
    float A, B;

    cin >> A >> B;

    if( abs(B) < INFINITESIMAL ){
        cout << "Cannot divide by zero!" << endl;
    } else {
        cout << A / B << endl;
    }

    return 0;
}Code language: PHP (php)

Note the following from the above solution:

  1. Since the numbers are assumed to be decimal numbers, line 12 does not check if the second number is zero using if( B == 0 ) because that works reliably with whole numbers (e.g. int, long, short, etc.) and not with decimal numbers (e.g. float and double). To check if a decimal number is zero, you select your precision (the smallest number that anything less than that will be assumed to be practically zero). Then compare if the magnitude of your number is less than that.
  2. In line 13, during an actual challenge, only write “Cannot divide by zero!” if the problem has requested you to do so.

Can I Do Better?

After crafting your solution, you should always ask yourself, “can I do better?“

With the data structures that you have thought of using, can you do better? Is there a better data structure that you can use to make implementing the solution easier, faster, or use less memory? Do you really need to store all those numbers? Can you do better?

With the algorithm you have selected, is there a better one? Do you need to do something else (e.g. reverse the list, sort the list, find the binary representation of a number, etc.) before applying my algorithm? Can you do better?

You will be amazed by how much you can improve your solutions if you keep asking yourself this question and put in the effort to improve your solutions.

Part 2 “Speed Up Testing and Uploading” is now available.