Python for competitive programming
InfoClock is the nickname of the Advanced Algorithms course at the Faculty of Computer Science and Mathematics in Bucharest. Usually, for competitive programming contests like Codeforces, students prefer C++. Being the only allowed language in high-school competitions, students have got used to it. Today, I taught a class on how you could use Python in a contest, showing them:
- basic operations with numbers, strings, lists and dictionaries
- input and output
- why it could be faster to use Python for the first simple problems
- why having big numbers by default helps you avoid overflows
The full repository is available on Github as a nice Jupyter notebook. I’ve also embedded it below.
Python for competitive programming¶
In [1]:
# This is a comment in Python
print("Hello World!")
Numbers¶
In [2]:
2 + 2
Out[2]:
In [3]:
x = 5
In [4]:
x / 2
Out[4]:
In [5]:
x // 2
Out[5]:
In [6]:
2 ** 10
Out[6]:
In [7]:
2 ** 10000
Out[7]:
In [8]:
len(str(2 ** 100000))
Out[8]:
Strings¶
In [9]:
s = "python"
In [10]:
s + s
Out[10]:
In [11]:
s * 3
Out[11]:
In [12]:
s = input() # type infoclock
In [13]:
s[0]
Out[13]:
In [14]:
s[1]
Out[14]:
In [15]:
s[-1]
Out[15]:
In [16]:
s[-2]
Out[16]:
In [17]:
s[1:]
Out[17]:
In [18]:
s[:1]
Out[18]:
In [19]:
s[2:]
Out[19]:
In [20]:
s[:2]
Out[20]:
In [21]:
s[:-1]
Out[21]:
In [22]:
s[:-2]
Out[22]:
In [23]:
s[2 : -2]
Out[23]:
In [24]:
s[2 : -2 : 2]
Out[24]:
Lists¶
In [25]:
l = [2, 3, 5, 7, 11]
In [26]:
l[0] * l[-1]
Out[26]:
In [27]:
l.append(13)
print(l)
In [28]:
l2 = [2, 4, 6, 8]
l + l2
Out[28]:
In [29]:
v = [0] * 10
print(v)
In [30]:
v = [1] * 10
v[0] = 33
print(v)
In [31]:
# s[0] = 'x' # this will fail
In [32]:
s = "python is awesome"
v = s.split()
print(v)
In [33]:
v.append(100)
print(v)
Dictionaries¶
In [34]:
d = {}
d['a'] = 'alex'
d['f'] = 'fmi'
d[3] = 42
print(d)
In [35]:
for key in d:
print ('Key: {0}; Value: {1}'.format(key, d[key]))
In [36]:
d[3] += 1
print(d[3])
Conditionals and loops¶
In [37]:
for x in range(5):
print("I want " + str(x + 1) + " apples.")
In [38]:
this_is_true = True
if this_is_true:
print("the answer to life, the universe and everything is 42")
else:
whatever # change this_is_true to False
In [39]:
x = 0
while x <= 5:
x += 1
if x == 1:
continue
print("I am number", x)
if x == 4:
break
List Comprehension¶
In [40]:
v = [2, 3, 5, 7, 11]
doubles = [x*2 for x in v]
print(doubles)
In [41]:
[x*x for x in range(30) if x % 2 == 1]
Out[41]:
In [42]:
N = 10
[0] * N
Out[42]:
In [43]:
[[0]*N for i in range(N)]
Out[43]:
Sexy stuff¶
In [44]:
# Syntax for importing
from random import randint
v = [randint(1, 100) for i in range(10)]
print(v)
In [45]:
v.sort()
print(v)
In [46]:
line = "1 3 7 13 2\n"
line.strip()
Out[46]:
In [47]:
line.strip().split()
Out[47]:
In [48]:
[int(x) for x in line.strip().split()]
Out[48]:
In [49]:
sorted([int(x) for x in line.strip().split()])
Out[49]:
In [50]:
[alfa, beta, gamma, epsilon, omega] = sorted([int(x) for x in line.strip().split()])
print(alfa, omega)
In [51]:
beta, epsilon = epsilon, beta
print(beta)
Smart stuff¶
In [52]:
# How to count number of appearances
from collections import defaultdict
v = [randint(1, 10) for i in range(100)]
d = defaultdict(int)
for x in v:
d[x] += 1
for key in d:
print(key, d[key])
Combinatorics¶
In [53]:
v = 'ABCD'
from itertools import permutations
for p in permutations(v):
print(" ".join(p))
In [54]:
from itertools import combinations
for c in combinations(v, 2):
print(" ".join(c))
The End¶
In [55]:
import this