Transcript Document

Introduction to HKOI
Gary Wong
Ice Breaking
and bond forming…
Rules
• Level 1
• Form a big circle
• The person holding the deck of cards will start the
game, by introducing himself, and then passes the
deck of cards to his left.
• In each preceding turn, the person holding the deck
of cards will repeat what the previous person has
said, and then introduces himself. After that, he will
passes the deck to his left.
• The game ends when the deck of cards return to the
first person.
Rules
• Level 2
• Form a big circle
• The person holding the deck of cards will start the game, by
introducing himself and drawing a card from the deck. After
that, he will pass the deck of cards to the kth person on his left,
where k is the number written on the card he draw.
• In each preceding turn, the person holding the deck of cards
will repeat what the previous person has said, and then
introduces himself. After that, he will draw a card from the
deck and pass the deck of cards to the kth person on his left,
where k is the number written on the card he draw.
• The game ends when the deck runs out of cards.
Why OI?
•
•
•
•
•
Get medals?
Love solving problems?
Learn more?
Make friends?
…
• OI could be a thing to give you all these
Agenda
•
•
•
•
•
Algorithms, Data Structures
Complexity
OI Style Programming
Training Sessions
Upcoming Challenges
Algorithms, Data Structures
the best couple…
Algorithms
• “Informally, an algorithm is any well-defined
computational procedure that takes some
value, or set of values, as input and produces
some value, or set of values, as output. An
algorithm is thus a sequence of computational
steps that transform the input into the output.”
[CLRS]
• N.B.: CLRS = a book called “Introduction to
algorithms”
Algorithms
• In other words, a series of procedures to solve
a problem
• Example:
– Bubble Sort, Merge Sort, Quick Sort
– Dijkstra’s Algorithm, Bellman Ford’s Algorithm
• Common misconceptions:
– Algorithm = Program
– Confusion between “algorithms” and “methods to
design algorithms”
Data Structures
• Briefly speaking, the way to organize data
• Examples:
– Binary Search Tree
– Hash Table
– Segment Tree
• Different data structures have different
properties
• Different algorithms use different data
structures
Don’t worry!
• All the above-mentioned technical jargons will
be taught later 
• So, come to attend training! 
Complexity
a performance indicator…
Complexity
• We want to know how well an algorithm
“scales” in terms of amount of data
– In BOTH time and space
• Only consider the proportionality to number
of basic operations performed
– A reasonable implementation can pass
– Minor improvements usually cannot help
3000
2400
1800
1200
600
0
0
5
f(n)=10n
10
f(n)=30n
15
f(n)=30n log n
20
f(n)=n^2
25
30
f(n)=n^3
35
f(n)=2^n
40
f(n)=3^n
45
f(n)=n!
Complexity
• Big-O notation
• Definition
We say that
f(x) is in O(g(x))
if and only if
there exist numbers x0 and M such that
|f(x)| ≤ M |g(x)| for x > x0
• You do not need to know this 
Complexity
• Example: Bubble Sort
• For i := 1 to n do
For j := 2 to i do
if a[j] > a[j-1] then swap(a[j], a[j-1]);
• Worst case number of swaps = n(n-1)/2
• Time Complexity = O(n2)
• Total space needed = size of array + space of
variables
• Space Complexity = 32*n +32*3 = O(n) +O(1) = O(n)
Complexity
• Another example: Binary search
• While a<=b do
m=(a+b)/2
If a[m]=key, Then return m
If a[m]<key, Then a=m+1
If a[m]>key, Then b=m-1
•
•
•
•
Worst case number of iterations = lg n [lg means log2]
Time Complexity = O(log n)
Total space needed = size of array + space of variables
Space Complexity = O(n)
What if…
• An algorithm involving both bubble sort and
binary search?
• O(f) + O(g) = max(O(f), O(g))
• Take the “maximum” one only, ignore the
“smaller” one
• Answer: O(n2)
Complexity
• Points to note:
– Speed of algorithm is machine-dependent
– Use suitable algorithms to solve problems
• E.g., if n=1000 and runtime limit is 1s, would you use:
– O(n2)?
– O(n!)?
– O(n3)?
– Constant hidden by Big-O notation
– Testing is required!
OI-Style Programming
from abstract theory
to (dirty) tricks…
OI-Style Programming
• Objective of Competition…
• The winner is determined by:
– Fastest Program?
– Amount of time used in coding?
– Number of Tasks Solved?
– Use of the most difficult algorithm?
– Highest Score
• Rule of thumb: ALWAYS aim to get as many scores as
you can
OI-Style Programming
• Scoring:
–
–
–
–
–
A “black box” judging system
Test data is fed into the program
Output is checked for correctness
No source code is manually inspected
How to take advantage (without cheating of
course!) of the system?
OI-Style Programming
• Steps for solving problems in OI:
1. Reading the problems
2. Choosing a problem
3. Reading the problem
4. Thinking
5. Coding
6. Testing
7. Finalizing the program
Reading the problems
• Problems in OI:
–
–
–
–
–
–
Title
Problem Description
Constraints
Input/Output Specification
Sample Input/Output
Scoring
Reading the problems
• Constraints
– Range of variables
– Execution Time
• NEVER make assumptions yourself
– Ask whenever you are not sure
– (Do not be afraid to ask questions!)
• Read every word carefully
• Make sure you understand before going on
Thinking
•
•
•
•
Classify the problem into certain type(s)
Rough works
Special cases, boundary cases
No idea? Give up first, do it later. Spend time
for other problems.
Thinking
• Make sure you know what you are doing
before coding
• Points to note:
– Complexity (BOTH time and space)
– Coding difficulties
• What is the rule of thumb mentioned?
Coding
• Short variable names
– Use i, j, m, n instead of no_of_schools,
name_of_students, etc.
• No comments needed
• As long as YOU understand YOUR code, okay to
ignore all “appropriate“ coding practices
• NEVER use 16 bit integers (unless memory is limited)
– 16 bit integer may be slower! (PC’s are usually 32bit, even 64 bit architectures should be
somewhat-optimized for 32 bit)
Coding
• Use goto, break, etc in the appropriate
situations
– Never mind what Dijkstra has to say 
• Avoid using floating point variables if possible
(eg. real, double, etc)
• Do not do small (aka useless) “optimizations”
to your code
• Save and compile frequently
Testing
• Sample Input/Output
“A problem has sample output for two reasons:
1. To make you understand what the correct output format is
2. To make you believe that your incorrect solution has
solved the problem correctly ”
• Manual Test Data
• Program-generated Test Data (if time allows)
• Boundary Cases (0, 1, other smallest cases)
• Large Cases (to check for TLE, overflows, etc)
• Tricky Cases
• Test by self-written program (again, if time allows)
Debugging
• Debugging – find out the bug, and remove it
• Easiest method: writeln/printf/cout
– It is so-called “Debug message”
• Use of debuggers:
– FreePascal IDE debugger
– gdb debugger
Finalizing
• Check output format
– Any trailing spaces? Missing end-of-lines? (for printf users,
this is quite common)
– better test once more with sample output
– Remember to clear those debug messages
• Check I/O – filename? stdio?
• Check exe/source file name
• Is the executable updated?
• Method of submission?
• Try to allocate ~5 mins at the end of competition for finalizing
OI-Style Programming
• 2nd time to ask: What is the rule of thumb?
• Tricks might be needed (Without violating
rules, of course)
Tricks
• Solve for simple cases
–
–
–
–
50% (e.g. slower solution, brute force)
Special cases (smallest, largest, etc)
Incorrect greedy algorithms
Very often, slow and correct solutions get higher scores
than fast but wrong solutions
• Hard Code
–
–
–
–
“No solution”
Stupid Hardcode: begin writeln(random(100)); end.
Naïve hardcode: “if input is x, output hc(x)”
More “intelligent” hardcode (sometimes not possible):
pre-compute the values, and only save some of them
Pitfalls
•
•
•
•
•
Misunderstanding the problem
Not familiar with competition environment
Output format
Using complex algorithms unnecessarily
Choosing the hardest problem first
Training Sessions
a moment for inspiration…
Training Sessions
• Intermediate and Advanced
• ALL topics are open to ALL trainees
• Tips: Pre-requisites are often needed for
advanced topics
Training Sessions
• On Saturday
• Room 123, Ho Sin-Hang Engineering Building,
Chinese University of Hong Kong
• AM session: 10:00-12:30
• Lunch
• PM session: 13:30-16:00
• http://www.hkoi.org for more details,
including latest training schedule and notes
Training Sessions
• A gross overview of topics covered:
– Algorithms and Data Structures
– Linux
• Free, popular and powerful
• Competition environment
– C++
• Advantage of Stardard Template Library (STL)
Upcoming Challenges
go for it!!!
Upcoming Challenges
• Asia-Pacific Informatics Olympiad (7 May 2011)
• Team Formation Test / TFT (28 May 2011)
• Provided that you can get through TFT,
– International Olympiad in Informatics
– National Olympiad in Informatics
– ACM Local
Upcoming Challenges
• How can I prepare for these challenges?
–
–
–
–
–
Attend trainings
Participate into mini-competitions
Search for learning materials in Internet
Read books
Practice, practice, practice
• PERFECT practice makes perfect
– HKOI Online Judge: http://judge.hkoi.org
– Other online judges (UVa, POJ, etc.)
Hard sell…
• Intermediate Topic: “Searching and Sorting”
(10:00-12:30, 22 Jan 2011) by Gary Wong

Thank you
for your tolerance =P
Reference
• PowerPoint for HKOI 2010 Training
Session 1
– “Introduction to HKOI”
– “Algorithms, OI Style Programming”