MONASH COMPETITIVE PROGRAMMING

## PRACTICES

We typically run training session once a week. You can join us to track upcoming events.

## WANT TO GET STARTED?!

If you want to jump in and try a few problems on your own, here are a couple websites that host some problems. If you have any questions or problems, please contact me and I will help you out in any way that I can!

### 1. Input/Output

Being familiar with IO is the first step, there are some common patterns on dealing with IO.

• Input/output: py, cpp

Python3
1
2
3
4
5
a, b = map(int, input().strip().split())

# read a list of ints
arr = list(map(int, input().strip().split()))

• Input/output: cpp only

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
scanf("%d%d", &a, &b);

// or
cin >> a >> b

// read a series of ints
while (scanf("%d", &a) != EOF) {
// do some thing
}

// or
while (cin >> a) {
// do some thing
}


Pay attention to Time limit, Memory limit constraints in your problem statement when you get Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE) verticts.

C++ can nearly run $10^8$ basic operations (e.g. +, -) in 1 second; while Python can nearly run $10^6$ basic operations in 1 second. You can estimate your program running time based on these info and your complexity analysis to avoid TLE and MLE.

### 3. Try some algorithmic problems

It’s time to be involved in some problem-solving skill

• Looping and binary-searching

Binary search
1
2
3
4
5
6
7
8
9
10
11
# my favorite pattern
best = None
while l <= r:         # search space is [l, r]
m = (l + r) // 2    # choose middle
if check(m) :       # is m >=
# invariant: all v in [l, r] >=
l = m + 1         # shrink search space
best = m          # best so far
else:
r = m - 1         # shrink search space
return best