Monash Algorithms & Problem Solving (MAPS)

Before you can begin coding, it is important to install an IDE and your language.
Visual Studio Code (VS Code) is the most popular IDE.

Python is the suggested programming language for beginners. This link is a quick guide to using Python in VS Code.

The main advantages of Python are:

|index| advantage
______|_________________________
| 0   |easier to learn
|_____|_________________________
| 1   |readable
|_____|_________________________
| 2   |integers are unbounded
|_____|_________________________

C++ is generally the most popular option for competitive programming due to its speed and versatility. Using C++ requires a compiler. Instructions for using C++ with VS Code can be found here.

The main advantages of C++ are:

|index| advantage
______|_________________________
| 0   |significantly faster
|_____|_________________________
| 1   |ubiquitous
|_____|_________________________
| 2   |less verbose than java
|_____|_________________________

As int in C++ is 32-bit, long long int will sometimes be required if C++ is used.

Java is another option for competitive programming.

Before you can develop your algorithm, you must know how to handle the input and output correctly. Depending on the competition format, your program will have to manage different types of I/O.

You may be required to use the console, read from a file, or return a function.

In MAPS workshops and contests, I/O is handled with the console.

In Python, input() is used for reading from console and print() is used for writing to console.

input() returns a string, so int() must be used for numerical input.

To read a line of integers, use {variable} = list(map(int, input().split())) to return a list of integers.

This line uses several functions to convert a line into a list of integers.

|function | explanation
__________|________________________________
| split() | This function separates a
|         | string into a list, creating
|         | a new element when a space
|         | appears in the string.
|_________|________________________________
| map()   | This function processes
|         | every element of the second
|         | argument through the
|         | function given as the first
|         | argument.
|_________|________________________________
| list()  | This converts the iterator
|         | returned by map() into a list.
|_________|________________________________

To read multiple lines containing one integer, [int(input()) for _ in range({number of lines})] can be used. This approach uses list comprehensions to succinctly call input() multiple times.

To output an integer, simply use print(). To print a list of values on one line, " ".join([str i for i in {your list}]) can be used.

in C++, cin >> {variable}; and cout << {variable}; are used to read and write from console. remember to have #include <iostream> so you have access to the console objects. C++ automatically separates input by whitespace, so using a for loop with cin >> {variable} is usually sufficient.

cin >> {variable-a} >> {variable-b} >> {variable-c} ...; can be used to read and assign multiple variables in one line.

Whilst using namespace std; is discouraged in conventional programming, it is used in competitive programming as it reduces the amount of characters typed.

ios_base::sync_with_stdio(false); and cin.tie(0); can be used to reduce the time taken by reading and writing to console.

Here is a sample template for C++ users:

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

}

Once you have finished reading the input, you need to design an algorithm that solves the problem.

When designing an algorithm, it is important to ensure that it is always correct for the input space and that it is efficient.

Factors to consider include:

1. Are the any edge cases in the problem?
2. Will the algorithm be efficient for large inputs?
3. Does the algorithm work for small inputs?
4. What data structures should you use in your algorithm?

Once you have designed your algorithm, the sample cases can be used to test it for bugs and errors. However, even if the algorithm passes all sample cases, there is no guarantee that you will recieve an AC (all correct) from the judge. If the judge returns a negative result, the result flag indicates how your algorithm failed, whether if it was too slow (TLE), it encountered an error (RE), or if it used too much memory (MLE).

It is important to consider the constraints of your problem. If your algorithm is ineffecient, then it will exceed the time or memory limits.

If you recieve a Time Limit Exceeded (TLE) code upon submitting your program, it is likely that your program has a poor time complexity. reducing the time complexity of a program will likely require a fundamental redesign of your algorithm.

judge.monashaps.com is where we host programming competitions and past problems can be found.

Here are some beginner topics:

|index| link
______|_____________________________
| 0   |greedy algorithms
|_____|_____________________________
| 1   |dynamic programming
|_____|_____________________________
| 2   |recursion
|_____|_____________________________
| 3   |binary search
|_____|_____________________________
| 4   |bfs & dfs
|_____|_____________________________

There are multiple secret test cases; in classic rules, failing on any of them causes WA, so you will have to spot the bug by yourself.

Your program breached the time limit, meaning that either the time complexity is too great or its efficency is poor.

Your program tried to use more memory than the judge allows. Try redesigning your variables to reduce memory usage.

Your program failed during the execution (segmentation fault, floating point exception…). The exact cause is not reported to the user to avoid hacking.

Reading from standard input (stdin) means reading data which you are typing on your keyboard, and outputting to standard output (stdout) means printing data to your console. This means it’s not necessary to create files. Use functions which read and write to the console.