P
T H I N K
F A ST
Competitive Programming
From Problem 2 Solution in O(1)
Elementary Math
Introduction
Mostafa Saad Ibrahim
PhD Student @ Simon Fraser University
Mathematics and CS
Directly
Indirectly
Many CS components need math
Discrete Mathematics is critical area (E.g. Graph Theory)
Machine Learning needs Algebra, Calculus, Probability..
3-D motion and graphics...Robot Trajectory...etc
Builds logical/critical thinking skills
Thinking abstractly and concretely
Problem solving skills
Commercial apps?
Most of them dont need math.
Mathematics and CP
In competitive programming (CP), Math is an
important topic.
Many problems needs basic high school skills
Others may focus on Discrete Mathematics
Graph theory is the most important field
Number theory & Combinatorics are nice frequent topics
Little Geometry, Probability and Game Theory
Problem Setters may avoid geometry and
probability problems, due to output precision
problems
#include<cmath> in C++
C++ offers for us some ready-made functions
Trigonometric, Hyperbolic, Exponential ,
Logarithmic, Power, Rounding, Remainder
Please, play with Majority of these functions
At least: floor, ceil, round, fabs, sqrt, exp, log, log2,
log10, pow, cos, cosh, acosh, isnan
We will explore some of them
Other languages should also have similar
functions
Machine Arithmetic
+ - * / are the usual arithmetic operations
32 bit numbers are suitable most of time
64 bit numbers can cover much wider range
9,223,372,036,854,775,808 (9 * 10^18)
This is tooo big and fit most of time for your purpose
But slower (8 bytes vs 4), so use it only if needed
Still we can face over/underflow
-2147483648 to 2147483647
Short fact: You have up to 2 billions
In intermediate computations or final results
doubles range: 1.7E +/- 308 (15 digits)
Real Numbers
Rational Numbers: can be represented as fraction: ,
7/2, 9/3, 5/1. Irrational: Pi = 3.1415926, sqrt(2)
Decimal expansion of fraction, to write it
1/16 = 0.0625, = 0.5
1/12 = 0.08333333333 .. 3 repeats for ever
5/7 = 0.714285714285714285. 714285 repeat forever
= 0.1(6), 1/12 = 0.08(3). 5/7 = 0.(71428), = 0.5(0)
How to know # of digits before cycle of n/d?
Programming? mark reminders of long division
Mathematically? See
Double Comparison
Operations can result in double value
Internal value can be shifted with +/- EPS
EPS is a very small amount (e.g. 1e-10)
e.g. x = 4.7 may be internally 4.7000001 or 4.69999999
so if(x == 4.7) fails! Although printing shows 4.7
Printing zero is tricky (-0.00 problem)
Compare x first with zero. If zero, then x = 0
Big Integers
Sometimes computations are too big
1775! is 4999 digits
Java/C# implement BigInteger library to
handle such big computations
In C++, you may implement it by yourself.
Exercise: Try to represent/add/multiply big numbers
I wrote this code when was young. Use freely (not in TC)
Main idea: Think in number as reversed array
In competitions, nowadays problem setters
avoid such problems most of time
Big Integers: Factorial
Create a big array. Initialize it to 1
Think in it as reversed array. Arr[0] first digit
From i = 2 to N
e.g. 120 represented as 021 (arr[0] = 0)
Multiply i in every cell
For every cell, if its value > 9 handle its carry
v => (v%10, v/10)
For last cell, check if it has carry (typically will have), and
put it in next cell, AS LONG AS there is a carry
See code example in previous page link
Big Integers: Factorial
Rounding Values
Rounding is replacing value with another
approximate value...many types and styles
In C++, we have 4 rounding functions
round: nearest integer to x [halfway cases away from 0]
floor: round down
ceil: round up
trunc: rounds toward zero (remove fraction)
In integers, x/y is floor of results
ceil(x, y) = (x+y-1)/y
round(x, y) = (x+y/2)/y [if x > 0] and (x-y/2)/y [x < 0]
Rounding Values: Examples
Be careful from -ve and 0.5
round(x) == x < 0 ? ceil(x-0.5) : floor(x+0.5);
To round to multiple of a specified amount
round(x, m) = round(x / m) * m
round(48.2 seconds, 15) = 45 seconds
round(2.1784 dollars, 0.01 (1 cent) ) = 2.18 dollars
Exponential function
If we have 2 jackets, 2 jeans & 2 shoes, I can
have 2x2x2 = 23 = 8 different clothing styles
Exponential function: y = bx
b (base), x (exponent): real,integer,+ve,-ve
Popular values: 2, 10, e [e is Euler's number ~= 2.7]
a 64 bit integer stores 264 numbers a very big number
2-x = ()x = 0.5x and 2x = ()-x = 0.5-x
In C++: pow(2, 3) = 23 = 8
Exponential indicates growing fast
Exponential function: Graphs
Logarithm
It is the inverse operation to exponentiation
y = bx ==> logby = x
b=[10, e, 2] => (common, natural, binary) log
log101000 = how many 10 multiplications = 1000? 3
log216 = how many 2 multiplications = 16? 4
log100.001 = how many 10 divisions = 1/1000? -3
Math notations: lg(x), ln(x), lb(x)
In c++: log10(x), log(x), log2(x)
log is strictly increasing for b > 1
log is strictly decreasing for 0 < b < 1
Logarithm: Graphs
log is strictly increasing function. Strictly [nothing equal], increasing, go up.
1 2 5 5 7 9 [Increasing]
1 2 5 6 7 9 [strictly Increasing]
9 7 5 5 2 1[decreasing]
9 7 6 5 2 1 [strictly decreasing]
Logarithm Operations
logbb = 1, logb1 = 0, logb0 = -oo, log1x = undefined
blogb(x) = x => take logb for the equation to get x
xby => blogb(x) + y
Logarithm and # of digits
base 10 can be used to know # of digits
Generally, # of digits in base b.
# digits = 1 + floor(log10(x))
log10(1000) = 3 => 4 digits
log10(1430) = 3.15 => 4 digits
log10(9999) = 3.99 => 4 digits
log10(10000) = 4 => 4 digits
So from 1000 to 10000-1, we have log10(x) = 3.xyz..
log2(16) = 4 => 5 bits. [16 in base 10 = 10000 in base 2]
Homework: # of digits of factorial n?
Math Materials
Knowledge of interest here
Mathematics part in
Other Math Books
Programming Challenge
Competitive Programming
Algorithms Books (e.g. CLR)
Concrete Mathematics
Discrete Mathematics and Its Applications
Mathematics for Computer Science (2013)
Solving...Solving...Solving
if cant solve..see editorial/solution...take notes
Time To Solve
There are some ad-hoc problems in the video
There also some problems on Big Integers
This type of problems usually dont appear nowadays
Why?: problem setters avoid languages advantages
Warmup by solving some of them :)
Also read this cheat sheet
