Competitive_Programming_2010_Halim.pdf

(5193 KB) Pobierz
Contents
Acknowledgements & Copyright
Foreword
Preface
Authors’ Profiles
Convention
Abbreviations
List of Tables
List of Figures
1 Introduction
1.1 Competitive Programming . . . . . . . . . . . .
1.2 Tips to be Competitive . . . . . . . . . . . . .
1.2.1 Tip 1: Quickly Identify Problem Types
1.2.2 Tip 2: Do Algorithm Analysis . . . . . .
1.2.3 Tip 3: Master Programming Languages
1.2.4 Tip 4: Master the Art of Testing Code .
1.2.5 Tip 5: Practice and More Practice . . .
1.3 Getting Started: Ad Hoc Problems . . . . . . .
1.4 Chapter Notes . . . . . . . . . . . . . . . . . .
v
vi
vii
viii
ix
x
xi
xii
1
1
2
4
5
7
9
10
11
13
14
14
15
15
16
18
18
19
22
25
26
26
27
29
32
32
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 Data Structures and Libraries
2.1 Data Structures . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Data Structures with Built-in Libraries
. . . . . . . . .
2.2.1 Linear Data Structures . . . . . . . . . . . . . . .
2.2.2 Non-Linear Data Structures (IOI syllabus excludes
2.3 Data Structures with Our-Own Libraries
. . . . . . . .
2.3.1 Graph . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Union-Find Disjoint Sets . . . . . . . . . . . . . .
2.3.3 Segment Tree . . . . . . . . . . . . . . . . . . . . .
2.4 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . .
3 Problem Solving Paradigms
3.1 Complete Search
. . . . .
3.1.1 Examples . . . . . .
3.1.2 Tips . . . . . . . . .
3.2 Divide and Conquer
. . .
3.2.1 Interesting Usages of
. . .
. . .
. . .
Hash
. . .
. . .
. . .
. . .
. . .
. . . .
. . . .
. . . .
Table)
. . . .
. . . .
. . . .
. . . .
. . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
Binary Search
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ii
CONTENTS
3.3
c Steven & Felix, NUS
3.4
3.5
Greedy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Classical Example . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2 Non Classical Example . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.3 Remarks About Greedy Algorithm in Programming Contests . . .
Dynamic Programming
. . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1 DP Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.2 Several Classical DP Examples . . . . . . . . . . . . . . . . . . . .
3.4.3 Non Classical Examples . . . . . . . . . . . . . . . . . . . . . . . .
3.4.4 Remarks About Dynamic Programming in Programming Contests
Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
35
35
35
37
40
40
45
49
54
57
58
58
58
67
70
74
75
77
81
85
86
87
89
92
93
93
94
94
94
98
98
99
100
101
101
102
102
103
105
105
106
107
108
108
108
4 Graph
4.1 Overview and Motivation . . . . . . . . . . . . . .
4.2 Depth First Search . . . . . . . . . . . . . . . . . .
4.3 Breadth First Search . . . . . . . . . . . . . . . . .
4.4 Kruskal’s . . . . . . . . . . . . . . . . . . . . . . .
4.5 Dijkstra’s . . . . . . . . . . . . . . . . . . . . . . .
4.6 Bellman Ford’s . . . . . . . . . . . . . . . . . . . .
4.7 Floyd Warshall’s . . . . . . . . . . . . . . . . . . .
4.8 Edmonds Karp’s (excluded in IOI syllabus) . . . .
4.9 Special Graphs . . . . . . . . . . . . . . . . . . . .
4.9.1 Tree . . . . . . . . . . . . . . . . . . . . . .
4.9.2 Directed Acyclic Graph . . . . . . . . . . .
4.9.3 Bipartite Graph (excluded in IOI syllabus)
4.10 Chapter Notes . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5 Mathematics
5.1 Overview and Motivation . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Ad Hoc Mathematics Problems . . . . . . . . . . . . . . . . . . . . .
5.3 Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1 Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.2 Greatest Common Divisor (GCD) & Least Common Multiple
5.3.3 Euler’s Totient (Phi) Function . . . . . . . . . . . . . . . . .
5.3.4 Extended Euclid: Solving Linear Diophantine Equation . . .
5.3.5 Modulo Arithmetic . . . . . . . . . . . . . . . . . . . . . . . .
5.3.6 Fibonacci Numbers . . . . . . . . . . . . . . . . . . . . . . . .
5.3.7 Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Java BigInteger Class . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1 Basic Features . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.2 Bonus Features . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Miscellaneous Mathematics Problems . . . . . . . . . . . . . . . . . .
5.5.1 Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.2 Cycle-Finding . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.3 Existing (or Fictional) Sequences and Number Systems . . .
5.5.4 Probability Theory (excluded in IOI syllabus) . . . . . . . . .
5.5.5 Linear Algebra (excluded in IOI syllabus) . . . . . . . . . . .
5.6 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 String Processing
6.1 Overview and Motivation . . . . . . . . . . . .
6.2 Ad Hoc String Processing Problems . . . . . .
6.3 String Processing with Dynamic Programming
6.3.1 String Alignment (Edit Distance) . . . .
6.3.2 Longest Common Subsequence . . . . .
iii
. . . . .
. . . . .
. . . . .
. . . . .
(LCM)
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
110
. 110
. 110
. 112
. 112
. 113
CONTENTS
c Steven & Felix, NUS
6.4
6.5
6.3.3 Palindrome . . . . . . . . .
Suffix Tree and Suffix Array . . . .
6.4.1 Suffix Tree: Basic Ideas . .
6.4.2 Applications of Suffix Tree
6.4.3 Suffix Array: Basic Ideas .
Chapter Notes . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
113
114
114
115
116
119
7 (Computational) Geometry
7.1 Overview and Motivation . .
7.2 Geometry Basics . . . . . . .
7.3 Graham’s Scan . . . . . . . .
7.4 Intersection Problems . . . .
7.5 Divide and Conquer Revisited
7.6 Chapter Notes . . . . . . . .
A Problem Credits
B We Want Your Feedbacks
Bibliography
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
120
. 120
. 121
. 128
. 130
. 131
. 132
133
134
135
iv
CONTENTS
c Steven & Felix, NUS
Acknowledgements
.
Steven wants to thank:
•
God, Jesus Christ, Holy Spirit, for giving talent and passion in this competitive programming.
•
My lovely wife, Grace Suryani, for allowing me to spend our precious time for this project.
•
My younger brother and co-author, Felix Halim, for sharing many data structures, algorithms,
and programming tricks to improve the writing of this book.
•
My father Lin Tjie Fong and mother Tan Hoey Lan for raising us and encouraging us to do
well in our study and work.
•
School of Computing, National University of Singapore, for employing me and allowing me
to teach CS3233 - ‘Competitive Programming’ module from which this book is born.
•
NUS/ex-NUS professors/lecturers who have shaped my competitive programming and coach-
ing skills: Prof Andrew Lim Leong Chye, Dr Tan Sun Teck, Aaron Tan Tuck Choy, Dr Sung
Wing Kin, Ken, Dr Alan Cheng Holun.
•
Fellow Teaching Assistants of CS3233 and ACM ICPC Trainers @ NUS: Su Zhan, Ngo Minh
Duc, Melvin Zhang Zhiyong, Bramandia Ramadhana.
•
My CS3233 students in Sem2 AY2008/2009 who inspired me to come up with the lecture
notes and CS3233 students in Sem2 AY2009/2010 who help me verify the content of this
book plus the Live Archive contribution.
•
My friend Ilham Winata Kurnia for proof reading the manuscript.
Copyright
This book is written mostly during National University of Singapore (NUS) office hours as part
of the ‘lecture notes’ for a module titled CS3233 - Competitive Programming. Hundreds of hours
have been devoted to write this book.
Therefore, no part of this book may be reproduced or transmitted in any form or by any means,
electronically or mechanically, including photocopying, scanning, uploading to any information
storage and retrieval system.
v
CONTENTS
c Steven & Felix, NUS
Foreword
Long time ago (exactly the Tuesday November 11th 2003 at 3:55:57 UTC), I received an e-mail
with the following sentence: I should say in a simple word that with the UVa Site, you have given
birth to a new CIVILIZATION and with the books you write (he meant “Programming Challenges:
The Programming Contest Training Manual” [23], coauthored with Steven Skiena), you inspire the
soldiers to carry on marching. May you live long to serve the humanity by producing super-human
programmers.
Although it’s clear that was an exaggeration, to tell the truth I started thinking a bit about and
I had a dream: to create a community around the project I had started as a part of my teaching
job at UVa, with persons from everywhere around the world to work together after that ideal. Just
by searching in Internet I immediately found a lot of people who was already creating a web-ring
of sites with excellent tools to cover the many lacks of the UVa site.
The more impressive to me was the ’Methods to Solve’ from Steven Halim, a very young
student from Indonesia and I started to believe that the dream would become real a day, because
the contents of the site were the result of a hard work of a genius of algorithms and informatics.
Moreover his declared objectives matched the main part of my dream: to serve the humanity. And
the best of the best, he has a brother with similar interest and capabilities, Felix Halim.
It’s a pity it takes so many time to start a real collaboration, but the life is as it is. Fortunately,
all of us have continued working in a parallel way and the book that you have in your hands is the
best proof.
I can’t imagine a better complement for the UVa Online Judge site, as it uses lots of examples
from there carefully selected and categorized both by problem type and solving techniques, an
incredible useful help for the users of the site. By mastering and practicing most programming
exercises in this book, reader can easily go to 500 problems solved in UVa online judge, which will
place them in top 400-500 within
≈100000
UVa OJ users.
Then it’s clear that the book “Competitive Programming: Increasing the Lower Bound of
Programming Contests” is suitable for programmers who wants to improve their ranks in upcoming
ICPC regionals and IOIs. The two authors have gone through these contests (ICPC and IOI)
themselves as contestants and now as coaches. But it’s also an essential colleague for the newcomers,
because as Steven and Felix say in the introduction ‘the book is not meant to be read once, but
several times’.
Moreover it contains practical C++ source codes to implement the given algorithms. Because
understand the problems is a thing, knowing the algorithms is another, and implementing them
well in short and efficient code is tricky. After you read this extraordinary book three times you
will realize that you are a much better programmer and, more important, a more happy person.
Miguel A. Revilla
UVa Online Judge site creator
ACM-ICPC International Steering Committee Member and Problem Archivist
University of Valladolid
http://uva.onlinejudge.org
http://acmicpc-live-archive.uva.es
vi

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin