Competitive Programming 3 PDF
Competitive Programming 3 PDF
Foreword vi
Preface viii
List of Abbreviations xx
1 Introduction 1
1.1 Competitive Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Tips to be Competitive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Tip 1: Type Code Faster! . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Tip 2: Quickly Identify Problem Types . . . . . . . . . . . . . . . . . 4
1.2.3 Tip 3: Do Algorithm Analysis . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Tip 4: Master Programming Languages . . . . . . . . . . . . . . . . . 10
1.2.5 Tip 5: Master the Art of Testing Code . . . . . . . . . . . . . . . . . 13
1.2.6 Tip 6: Practice and More Practice . . . . . . . . . . . . . . . . . . . 15
1.2.7 Tip 7: Team Work (for ICPC) . . . . . . . . . . . . . . . . . . . . . . 16
1.3 Getting Started: The Easy Problems . . . . . . . . . . . . . . . . . . . . . . 16
1.3.1 Anatomy of a Programming Contest Problem . . . . . . . . . . . . . 16
1.3.2 Typical Input/Output Routines . . . . . . . . . . . . . . . . . . . . . 17
1.3.3 Time to Start the Journey . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4 The Ad Hoc Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.5 Solutions to Non-Starred Exercises . . . . . . . . . . . . . . . . . . . . . . . 27
1.6 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
i
CONTENTS
c Steven & Felix
4 Graph 121
4.1 Overview and Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.2 Graph Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
4.2.1 Depth First Search (DFS) . . . . . . . . . . . . . . . . . . . . . . . . 122
4.2.2 Breadth First Search (BFS) . . . . . . . . . . . . . . . . . . . . . . . 123
4.2.3 Finding Connected Components (Undirected Graph) . . . . . . . . . 125
4.2.4 Flood Fill - Labeling/Coloring the Connected Components . . . . . . 125
4.2.5 Topological Sort (Directed Acyclic Graph) . . . . . . . . . . . . . . . 126
4.2.6 Bipartite Graph Check . . . . . . . . . . . . . . . . . . . . . . . . . . 128
4.2.7 Graph Edges Property Check via DFS Spanning Tree . . . . . . . . . 128
4.2.8 Finding Articulation Points and Bridges (Undirected Graph) . . . . . 130
4.2.9 Finding Strongly Connected Components (Directed Graph) . . . . . . 133
4.3 Minimum Spanning Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.3.1 Overview and Motivation . . . . . . . . . . . . . . . . . . . . . . . . 138
4.3.2 Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.3.3 Prim’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.3.4 Other Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.4 Single-Source Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
4.4.1 Overview and Motivation . . . . . . . . . . . . . . . . . . . . . . . . 146
4.4.2 SSSP on Unweighted Graph . . . . . . . . . . . . . . . . . . . . . . . 146
4.4.3 SSSP on Weighted Graph . . . . . . . . . . . . . . . . . . . . . . . . 148
4.4.4 SSSP on Graph with Negative Weight Cycle . . . . . . . . . . . . . . 151
4.5 All-Pairs Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
4.5.1 Overview and Motivation . . . . . . . . . . . . . . . . . . . . . . . . 155
4.5.2 Explanation of Floyd Warshall’s DP Solution . . . . . . . . . . . . . 156
4.5.3 Other Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
4.6 Network Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.6.1 Overview and Motivation . . . . . . . . . . . . . . . . . . . . . . . . 163
4.6.2 Ford Fulkerson’s Method . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.6.3 Edmonds Karp’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . 164
4.6.4 Flow Graph Modeling - Part 1 . . . . . . . . . . . . . . . . . . . . . . 166
4.6.5 Other Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
4.6.6 Flow Graph Modeling - Part 2 . . . . . . . . . . . . . . . . . . . . . . 168
ii
CONTENTS
c Steven & Felix
5 Mathematics 191
5.1 Overview and Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
5.2 Ad Hoc Mathematics Problems . . . . . . . . . . . . . . . . . . . . . . . . . 192
5.3 Java BigInteger Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
5.3.1 Basic Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
5.3.2 Bonus Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
5.4 Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
5.4.1 Fibonacci Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
5.4.2 Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
5.4.3 Catalan Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
5.4.4 Remarks about Combinatorics in Programming Contests . . . . . . . 206
5.5 Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
5.5.1 Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
5.5.2 Greatest Common Divisor & Least Common Multiple . . . . . . . . . 211
5.5.3 Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
5.5.4 Finding Prime Factors with Optimized Trial Divisions . . . . . . . . . 212
5.5.5 Working with Prime Factors . . . . . . . . . . . . . . . . . . . . . . . 213
5.5.6 Functions Involving Prime Factors . . . . . . . . . . . . . . . . . . . 214
5.5.7 Modified Sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
5.5.8 Modulo Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
5.5.9 Extended Euclid: Solving Linear Diophantine Equation . . . . . . . . 217
5.5.10 Remarks about Number Theory in Programming Contests . . . . . . 217
5.6 Probability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
5.7 Cycle-Finding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
5.7.1 Solution(s) using Efficient Data Structure . . . . . . . . . . . . . . . 223
5.7.2 Floyd’s Cycle-Finding Algorithm . . . . . . . . . . . . . . . . . . . . 223
5.8 Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
5.8.1 Decision Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
5.8.2 Mathematical Insights to Speed-up the Solution . . . . . . . . . . . . 227
5.8.3 Nim Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
5.9 Solution to Non-Starred Exercises . . . . . . . . . . . . . . . . . . . . . . . . 229
5.10 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
iii
CONTENTS
c Steven & Felix
iv
CONTENTS
c Steven & Felix
A uHunt 393
B Credits 396
Bibliography 398
v
CONTENTS
c Steven & Felix
Foreword
A long time ago (on the 11th of November in 2003, Tuesday, 3:55:57 UTC), I received an
e-mail with the following message:
“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” [60], 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 that was clearly an exaggeration, it did cause me to think. I had a dream: to
create a community around the project I had started as a part of my teaching job at UVa,
with people from all around the world working together towards the same ideal. With a
little searching, I quickly found a whole online community running a web-ring of sites with
excellent tools that cover and provide whatever the UVa site lacked.
To me, ‘Methods to Solve’ by Steven Halim, a very young student from Indonesia, was
one of the more impressive websites. I was inspired to believe that the dream would become
real one day, because in this website lay the result of the hard work of a genius of algorithms
and informatics. Moreover, his declared objectives matched the core of my dream: to serve
humanity. Even better, he has a brother with similar interests and capabilities, Felix Halim.
It’s a pity that it takes so much time to start a real collaboration, but life is like that.
Fortunately, all of us have continued working together in a parallel fashion towards the
realization of that dream—the book that you have in your hands now is proof of that.
I can’t imagine a better complement for the UVa Online Judge. This book uses lots of
examples from UVa carefully selected and categorized both by problem type and solving
technique, providing incredibly useful help for the users of the site. By mastering and
practicing most programming exercises in this book, a reader can easily solve at least 500
problems in the UVa Online Judge, which will place them in the top 400-500 amongst
≈100000 UVa OJ users.
It’s clear that the book “Competitive Programming: Increasing the Lower Bound of
Programming Contests” is suitable for programmers who want 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 newcomers—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 code to implement given algorithms. Un-
derstanding a problem is one thing, but knowing the algorithm to solve it is another, and
implementing the solution well in short and efficient code is tricky. After you have read this
extraordinary book three times you will realize that you are a much better programmer and,
more importantly, a happier person.
vi
CONTENTS
c Steven & Felix
vii
CONTENTS
c Steven & Felix
Preface
This book is a must have for every competitive programmer. Mastering the contents of
this book is a necessary (but maybe not sufficient) condition if one wishes to take a leap
forward from being just another ordinary coder to being among one of the world’s finest
programmers.
Typical readers of this book would include:
1. University students who are competing in the annual ACM International Collegiate
Programming Contest (ICPC) [66] Regional Contests (including the World Finals),
2. Secondary or High School Students who are competing in the annual International
Olympiad in Informatics (IOI) [34] (including the National or Provincial Olympiads),
3. Coaches who are looking for comprehensive training materials for their students [24],
4. Anyone who loves solving problems through computer programs. There are numer-
ous programming contests for those who are no longer eligible for ICPC, including
TopCoder Open, Google CodeJam, Internet Problem Solving Contest (IPSC), etc.
Prerequisites
This book is not written for novice programmers. This book is aimed at readers who have
at least basic knowledge in programming methodology, are familiar with at least one of
these programming languages (C/C++ or Java, preferably both), have passed a basic data
structures and algorithms course (typically taught in year one of Computer Science university
curricula), and understand simple algorithmic analysis (at least the big-O notation). In
the third edition, more content has been added so that this book can also be used as a
supplementary reading for a basic Data Structures and Algorithms course.
viii
CONTENTS
c Steven & Felix
We know that one cannot probably win the ACM ICPC regional just by mastering the
contents of the current version (third edition) of this book. While we have included a lot of
materials in this book—much more than in the first two editions—we are aware that much
more than what this book can offer is required to achieve that feat. Some additional pointers
to useful references are listed in the chapter notes for readers who are hungry for more. We
believe, however, that your team will fare much better in future ICPCs after mastering the
contents of this book. We hope that this book will serve as both inspiration and motivation
for your 3-4 year journey competing in ACM ICPCs during your University days.
To IOI Contestants
Much of our advice for ACM ICPC contestants applies to you too. The ACM ICPC and IOI
syllabi are largely similar, except that IOI, for now, currently excludes the topics listed in
the following Table 1. You can skip these items until your university years (when you join
that university’s ACM ICPC teams). However, learning these techniques in advance may
definitely be beneficial as some tasks in IOI can become easier with additional knowledge.
We know that one cannot win a medal in IOI just by mastering the contents of the
current version (third edition) of this book. While we believe that many parts of the IOI
syllabus has been included in this book—hopefully enabling you to achieve a respectable
score in future IOIs—we are well aware that modern IOI tasks require keen problem solving
skills and tremendous creativity—virtues that we cannot possibly impart through this static
textbook. This book can provide knowledge, but the hard work must ultimately be done by
you. With practice comes experience, and with experience comes skill. So, keep practicing!
ix
CONTENTS
c Steven & Felix
x
CONTENTS
c Steven & Felix
To All Readers
Due to its diversity of coverage and depth of discussion, this book is not meant to be
read once, but several times. There are many written (≈ 238) and programming exercises
(≈ 1675) listed and spread across almost every section. You can skip these exercises at
first if the solution is too difficult or requires further knowledge and technique, and revisit
them after studying other chapters of this book. Solving these exercises will strengthen
your understanding of the concepts taught in this book as they usually involve interesting
applications, twists or variants of the topic being discussed. Make an effort to attempt
them—time spent solving these problems will definitely not be wasted.
We believe that this book is and will be relevant to many university and high school
students. Programming competitions such as the ICPC and IOI are here to stay, at least
for many years ahead. New students should aim to understand and internalize the basic
knowledge presented in this book before hunting for further challenges. However, the term
‘basic’ might be slightly misleading—please check the table of contents to understand what
we mean by ‘basic’.
As the title of this book may imply, the purpose of this book is clear: We aim to
improve everyone’s programming abilities and thus increase the lower bound of programming
competitions like the ICPC and IOI in the future. With more contestants mastering the
contents of this book, we hope that the year 2010 (when the first edition of this book was
published) will be a watershed marking an accelerated improvement in the standards of
programming contests. We hope to help more teams solve more (≥ 2) problems in future
ICPCs and help more contestants to achieve greater (≥ 200) scores in future IOIs. We also
hope to see many ICPC and IOI coaches around the world (especially in South East Asia)
adopt this book for the aid it provides in mastering topics that students cannot do without
in competitive programming contests. If such a proliferation of the required ‘lower-bound’
knowledge for competitive programming is achieved, then this book’s primary objective of
advancing the level of human knowledge will have been fulfilled, and we, as the authors of
this book, will be very happy indeed.
Convention
There are lots of C/C++ code and also some Java code (especially in Section 5.3) included
in this book. If they appear, they will be typeset in this monospace font.
For the C/C++ code in this book, we have adopted the frequent use of typedefs and
macros—features that are commonly used by competitive programmers for convenience,
brevity, and coding speed. However, we cannot use similar techniques for Java as it does
not contain similar or analogous features. Here are some examples of our C/C++ code
shortcuts:
xi
CONTENTS
c Steven & Felix
// We have abandoned the use of "REP" and "TRvii" since the second edition
// in order to reduce the confusion encountered by new programmers
The following shortcuts are frequently used in both our C/C++ and Java code:
// ans = a ? b : c; // to simplify: if (a) ans = b; else ans = c;
// ans += val; // to simplify: ans = ans + val; and its variants
// index = (index + 1) % n; // index++; if (index >= n) index = 0;
// index = (index + n - 1) % n; // index--; if (index < 0) index = n - 1;
// int ans = (int)((double)d + 0.5); // for rounding to nearest integer
// ans = min(ans, new_computation); // min/max shortcut
// alternative form but not used in this book: ans <?= new_computation;
// some code use short circuit && (AND) and || (OR)
Problem Categorization
As of 24 May 2013, Steven and Felix—combined—have solved 1903 UVa problems (≈ 46.45%
of the entire UVa problemset). About ≈ 1675 of them are discussed and categorized in this
book. Since late 2011, some Live Archive problems have also been integrated in the UVa
Online Judge. In this book, we use both problem numberings, but the primary sort key used
in the index section of this book is the UVa problem number.
These problems are categorized according to a ‘load balancing’ scheme: If a problem can
be classified into two or more categories, it will be placed in the category with a lower number
of problems. This way, you may find that some problems have been ‘wrongly’ categorized,
where the category that it appears in might not match the technique that you have used to
solve it. We can only guarantee that if you see problem X in category Y, then you know
that we have managed to solve problem X with the technique mentioned in the section that
discusses category Y.
We have also limited each category to at most 25 (TWENTY FIVE) problems, splitting
them into separate categories when needed.
If you need hints for any of the problems (that we have solved), flip to the handy index
at the back of this book instead of flipping through each chapter—it might save you some
time. The index contains a list of UVa/LA problems, ordered by their problem number (do
a binary search!) and augmented by the pages that contain discussion of said problems (and
the data structures and/or algorithms required to solve that problem). In the third edition,
we allow the hints to span more than one line so that they can be more meaningful.
Utilize this categorization feature for your training! Solving at least a few problems
from each category (especially the ones we have highlighted as must try *) is a great way
to diversify your problem solving skillset. For conciseness, we have limited ourselves to a
maximum of 3 highlights per category.
xii
CONTENTS
c Steven & Felix
• The first noticeable change is the layout. We now have a greater information density
on each page. The 2nd edition uses single line spacing instead of the 1.5 line spacing
used in the 1st edition. The positioning of small figures is also enhanced so that we
have a more compact layout. This is to avoid increasing the number of pages by too
much while still adding more content.
• Some minor bugs in our code examples (both the ones displayed in the book and the
soft copies provided in the companion web site) have been fixed. All code samples now
have much more meaningful comments to aid in comprehension.
• Besides enhancing the discussion of many data structures, algorithms, and program-
ming problems, we have also added these new materials in each chapter:
1. Many new Ad Hoc problems to kick start this book (Section 1.4).
2. A lightweight set of Boolean (bit-manipulation) techniques (Section 2.2), Implicit
Graphs (Section 2.4.1), and Fenwick Tree data structures (Section 2.4.4).
3. More DP: A clearer explanation of bottom-up DP, the O(n log k) solution for the
LIS problem, the 0-1 Knapsack/Subset Sum, and DP TSP (using the bitmask
technique) (Section 3.5.2).
4. A reorganization of the graph material into: Graph Traversal (both DFS and
BFS), Minimum Spanning Tree, Shortest Paths (Single-Source and All-Pairs),
Maximum Flow, and Special Graphs. New topics include Prim’s MST algorithm,
a discussion of DP as a traversal on implicit DAGs (Section 4.7.1), Eulerian
Graphs (Section 4.7.3), and the Augmenting Path algorithm (Section 4.7.4).
5. A reorganization of mathematical techniques (Chapter 5) into: Ad Hoc, Java
BigInteger, Combinatorics, Number Theory, Probability Theory, Cycle-Finding,
Game Theory (new), and Powers of a (Square) Matrix (new). Each topic has
been rewritten for clarity.
6. Basic string processing skills (Section 6.2), more string-related problems (Section
6.3), including string matching (Section 6.4), and an enhanced Suffix Tree/Array
explanation (Section 6.6).
7. More geometry libraries (Chapter 7), especially on points, lines and polygons.
8. A new Chapter 8, which contains discussion on problem decomposition, advanced
search techniques (A*, Depth Limited Search, Iterative Deepening, IDA*), ad-
vanced DP techniques (more bitmask techniques, the Chinese Postman Problem,
a compilation of common DP states, a discussion of better DP states, and some
harder DP problems).
xiii
CONTENTS
c Steven & Felix
• Many existing figures in this book have been redrawn and enhanced. Many new figures
have been added to help explain the concepts more clearly.
• The first edition is mainly written using from the viewpoint of the ICPC contestant and
C++ programmer. The second edition is written to be more balanced and includes
the IOI perspective. Java support is also strongly enhanced in the second edition.
However, we do not support any other programming languages as of yet.
• Steven’s ‘Methods to Solve’ website has now been fully integrated in this book in the
form of ‘one liner hints’ for each problem and the useful problem index at the back
of this book. Now, reaching 1000 problems solved in UVa online judge is no longer
a wild dream (we believe that this feat is doable by a serious 4-year CS university
undergraduate).
• Some examples in the first edition use old programming problems. In the second
edition, these examples have been replaced/added with newer examples.
• ≈ 600 more programming exercises from the UVa Online Judge and Live Archive have
been solved by Steven & Felix and added to this book. We have also added many more
written exercises throughout the book with hints/short solutions as appendices.
• Short profiles of data structure/algorithm inventors have been adapted from Wikipedia
[71] or other sources for this book. It is nice to know a little bit more about these
inventors.
• The third edition now uses a slightly larger font size (12 pt) compared to second edition
(11 pt), a 9 percent increase. Hopefully many readers will find the text more readable
this time. We also use larger figures. These decisions, however, have increased the
number of pages and rendered the book thicker. We have also adjusted the left/right
margin in odd/even pages to increase readability.
• The layout has been changed to start almost every section on a new page. This is to
make the layout far easier to manage.
• We have added many more written exercises throughout the book and classifed them
into non-starred (for self-checking purposes; hints/solutions are at the back of each
chapter) and starred * versions (for extra challenges; no solution is provided). The
written exercises have been placed close to the relevant discussion in the body text.
• ≈ 477 more programming exercises from the UVa Online Judge and Live Archive have
been solved by Steven & Felix and consequently added to this book. We thus have
maintained a sizeable ≈ 50% (to be precise, ≈ 46.45%) coverage of UVa Online Judge
problems even as the judge has grown in the same period of time. These newer problems
have been listed in an italic font. Some of the newer problems have replaced older ones
as the must try problems. All programming exercises are now always placed at the
end of a section.
xiv
CONTENTS
c Steven & Felix
• We now have proof that capable CS students can achieve ≥ 500 AC problems (from 0)
in the UVa Online Judge in just one University semester (4 months) with this book.
• The new (or revised) materials, chapter by chapter:
1. Chapter 1 contains a gentler introduction for readers who are new to competitive
programming. We have elaborated on stricter Input/Output (I/O) formats in
typical programming problems and common routines for dealing with them.
2. We add one more linear data structure: ‘deque’ in Section 2.2. Chapter 2 now
contains a more detailed discussion of almost all data structures discussed in this
chapter, especially Section 2.3 and 2.4.
3. In Chapter 3, we have a more detailed discussions of various Complete Search
techniques: Nested loops, generating subsets/permutations iteratively, and recur-
sive backtracking. New: An interesting trick to write and print Top-Down DP
solutions, Discussion of Kadane’s algorithm for Max 1D Range Sum.
4. In Chapter 4, we have revised white/gray/black labels (legacy from [7]) to their
standard nomenclature, renaming ‘max flow’ to ‘network flow’ in the process. We
have also referred to the algorithm author’s actual scientific paper for a better
understanding of the original ideas of the algorithm. We now have new diagrams
of the implicit DAG in classical DP problems found in Section 3.5.
5. Chapter 5: We have included greater coverage of Ad Hoc mathematics prob-
lems, a discussion of an interesting Java BigInteger operation: isProbablePrime,
added/expanded several commonly used Combinatorics formulae and modified
sieve algorithms, expanded/revised sections on Probability Theory (Section 5.6),
Cycle-finding (Section 5.7), and Game Theory (Section 5.8).
6. Chapter 6: We rewrite Section 6.6 to have a better explanation of Suffix Trie/Tree/
Array by reintroducing the concept of terminating character.
7. Chapter 7: We trim this chapter into two core sections and improve the library
code quality.
8. Chapter 8: The harder topics that were listed in Chapter 1-7 in the 2nd edition
have now been relocated to Chapter 8 (or Chapter 9 below). New: Discussion
of harder backtracking routine, State-Space search, meet in the middle, trick of
using balanced BST as memo table, and a more comprehensive section about
problem decomposition.
9. New Chapter 9: Various rare topics that appear once a while in programming
contests have been added. Some of them are easy, but many of them are hard
and can be somewhat important score determinants in programming contests.
Supporting Websites
This book has an official companion web site at sites.google.com/site/stevenhalim,
from which you can obtain a soft copy of sample source code and the (public/simpler version)
of the) PDF slides used in Steven’s CS3233 classes.
All programming exercises in this book are integrated in the uhunt.felix-halim.net tool
and can be found in the UVa Online Judge at uva.onlinejudge.org
New in the third edition: Many algorithms now have interactive visualizations at:
www.comp.nus.edu.sg/~stevenha/visualization
xv
CONTENTS
c Steven & Felix
• God, Jesus Christ, and the Holy Spirit, for giving me talent and passion in 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.
• my friend Ilham Winata Kurnia for proof reading the manuscript of the first edition.
• fellow Teaching Assistants of CS3233 and ACM ICPC Trainers @ NUS: Su Zhan, Ngo
Minh Duc, Melvin Zhang Zhiyong, Bramandia Ramadhana.
• the first ≈ 550 buyers of the 1st edition as of 1 August 2011 (this number is no longer
updated). Your supportive responses encourage us!
xvi
CONTENTS
c Steven & Felix
• the proof readers: Seven of CS3233 students above (underlined) plus Tay Wenbin.
• Last but not least, I want to re-thank my wife, Grace Suryani, for letting me do another
round of tedious book editing process while she was pregnant with our first baby: Jane
Angelina Halim.
• the ≈ 2000 buyers of the 2nd edition as of 24 May 2013 (this number is no longer
updated). Thanks :).
xvii
CONTENTS
c Steven & Felix
• fellow Teaching Assistant of CS3233 @ NUS in the past two years: Harta Wijaya,
Trinh Tuan Phuong, and Huang Da.
• the proof readers: Six of CS3233 students in Sem2 AY2011/2012 (underlined) and
Hubert Teo Hua Kian.
• the NUS Centre for Development of Teaching and Learning (CDTL) for giving the
initial funding to build the algorithm visualization website.
• my wife Grace Suryani and my daughter Jane Angelina for your love in our family.
Copyright
No part of this book may be reproduced or transmitted in any form or by any means, elec-
tronically or mechanically, including photocopying, scanning, uploading to any information
storage and retrieval system.
xviii
CONTENTS
c Steven & Felix
Authors’ Profiles
Steven Halim, PhD1
[email protected]
Steven Halim is currently a lecturer in
School of Computing, National University
of Singapore (SoC, NUS). He teaches sev-
eral programming courses in NUS, ranging
from basic programming methodology, inter-
mediate data structures and algorithms, and
also the ‘Competitive Programming’ module
that uses this book. He is the coach of both
the NUS ACM ICPC teams and the Singa-
pore IOI team. He participated in several
ACM ICPC Regional as student (Singapore
2001, Aizu 2003, Shanghai 2004). So far,
he and other trainers @ NUS have success-
fully groomed two ACM ICPC World Final-
ist teams (2009-2010; 2012-2013) as well as
two gold, six silver, and seven bronze IOI
medalists (2009-2012).
Steven is happily married with Grace
Suryani Tioso and currently has one daugh-
ter: Jane Angelina Halim.
1
PhD Thesis: “An Integrated White+Black Box Approach for Designing and Tuning Stochastic Local
Search Algorithms”, 2009.
2
PhD Thesis: “Solving Big Data Problems: from Sequences to Tables and Graphs”, 2012.
xix
CONTENTS
c Steven & Felix
6.1 L/R: Before/After Sorting; k = 1; the initial sorted order appears . . . . . . 255
6.2 L/R: Before/After Sorting; k = 2; ‘GATAGACA’ and ‘GACA’ are swapped . . . 256
6.3 Before/After sorting; k = 4; no change . . . . . . . . . . . . . . . . . . . . . 257
6.4 String Matching using Suffix Array . . . . . . . . . . . . . . . . . . . . . . . 260
6.5 Computing the LCP given the SA of T = ‘GATAGACA$’ . . . . . . . . . . . . 261
6.6 The Suffix Array, LCP, and owner of T = ‘GATAGACA$CATA#’ . . . . . . . . 262
xxi
List of Figures
3.1 8-Queens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.2 UVa 10360 [47] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.3 My Ancestor (all 5 root-to-leaf paths are sorted) . . . . . . . . . . . . . . . . 85
3.4 Visualization of UVa 410 - Station Balance . . . . . . . . . . . . . . . . . . . 90
3.5 UVa 410 - Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.6 UVa 410 - Greedy Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.7 UVa 10382 - Watering Grass . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.8 Bottom-Up DP (columns 21 to 200 are not shown) . . . . . . . . . . . . . . 100
3.9 Longest Increasing Subsequence . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.10 Coin Change . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
3.11 A Complete Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
3.12 Cutting Sticks Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
xxii
LIST OF FIGURES
c Steven & Felix
7.1 Rotating point (10, 3) by 180 degrees counter clockwise around origin (0, 0) 272
7.2 Distance to Line (left) and to Line Segment (middle); Cross Product (right) 274
xxiii
LIST OF FIGURES
c Steven & Felix
9.1 The Implication Graph of Example 1 (Left) and Example 2 (Right) . . . . . 336
9.2 The Standard TSP versus Bitonic TSP . . . . . . . . . . . . . . . . . . . . . 339
9.3 An Example of Chinese Postman Problem . . . . . . . . . . . . . . . . . . . 342
9.4 The Four Common Variants of Graph Matching in Programming Contests . 349
9.5 A Sample Test Case of UVa 10746: 3 Matchings with Min Cost = 40 . . . . 350
9.6 L: Sphere, M: Hemisphere and Great-Circle, R: gcDistance (Arc A-B) . . . . 352
9.7 Comparison Between Max Independent Paths vs Max Edge-Disjoint Paths . 354
9.8 An example of a rooted tree T with n = 10 vertices . . . . . . . . . . . . . . 359
9.9 The Magic Square Construction Strategy for Odd n . . . . . . . . . . . . . . 361
9.10 An Example of Min Cost Max Flow (MCMF) Problem (UVa 10594 [47]) . . 369
9.11 Min Path Cover on DAG (from UVa 1201 [47]) . . . . . . . . . . . . . . . . . 370
9.12 Example of an AVL Tree Deletion (Delete 7) . . . . . . . . . . . . . . . . . . 382
9.13 Explanation of RMQ(i, j) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
xxiv
Chapter 1
Introduction
An illustration: UVa Online Judge [47] Problem Number 10911 (Forming Quiz Teams).
1
1.1. COMPETITIVE PROGRAMMING
c Steven & Felix
Now ask yourself: Which of the following best describes you? Note that if you are
unclear with the material or the terminology shown in this chapter, you can re-read it
again after going through this book once.
• Uncompetitive programmer A (a.k.a. the blurry one):
Step 1: Reads the problem and becomes confused. (This problem is new for him).
Step 2: Tries to code something: Reading the non-trivial input and output.
Step 3: Realizes that all his attempts are not Accepted (AC):
Greedy (Section 3.4): Repeatedly pairing the two remaining students with the
shortest separating distances gives the Wrong Answer (WA).
Naı̈ve Complete Search: Using recursive backtracking (Section 3.2) and trying
all possible pairings yields Time Limit Exceeded (TLE).
• Uncompetitive programmer B (Give up):
Step 1: Reads the problem and realizes that he has seen this problem before.
But also remembers that he has not learned how to solve this kind of problem...
He is not aware of the Dynamic Programming (DP) solution (Section 3.5)...
Step 2: Skips the problem and reads another problem in the problem set.
• (Still) Uncompetitive programmer C (Slow):
Step 1: Reads the problem and realizes that it is a hard problem: ‘minimum
weight perfect matching on a small general weighted graph’. However,
since the input size is small, this problem is solvable using DP. The DP state is
a bitmask that describes a matching status, and matching unmatched students
i and j will turn on two bits i and j in the bitmask (Section 8.3.1).
Step 2: Codes I/O routine, writes recursive top-down DP, tests, debugs >.<...
Step 3: After 3 hours, his solution obtains AC (passed all the secret test data).
• Competitive programmer D:
Completes all the steps taken by uncompetitive programmer C in ≤ 30 minutes.
• Very competitive programmer E:
A very competitive programmer (e.g. the red ‘target’ coders in TopCoder [32])
would solve this ‘well known’ problem ≤ 15 minutes...
Please note that being well-versed in competitive programming is not the end goal, but
only a means to an end. The true end goal is to produce all-rounder computer scien-
tists/programmers who are much readier to produce better software and to face harder CS
research problems in the future. The founders of the ACM International Collegiate Pro-
gramming Contest (ICPC) [66] have this vision and we, the authors, agree with it. With
this book, we play our little role in preparing the current and the future generations to be
more competitive in dealing with well-known CS problems frequently posed in the recent
ICPCs and the International Olympiad in Informatics (IOI)s.
2
CHAPTER 1. INTRODUCTION
c Steven & Felix
Exercise 1.1.1: The greedy strategy of the uncompetitive programmer A above actually
works for the sample test case shown in Figure 1.1. Please give a better counter example!
Exercise 1.1.2: Analyze the time complexity of the naı̈ve complete search solution by
uncompetitive programmer A above to understand why it receives the TLE verdict!
Exercise 1.1.3*: Actually, a clever recursive backtracking solution with pruning can still
solve this problem. Solve this problem without using a DP table!
3
1.2. TIPS TO BE COMPETITIVE
c Steven & Felix
int main() {
int i, j, caseNo = 1, x[20], y[20];
// freopen("10911.txt", "r", stdin); // redirect input file to stdin
For your reference, the explanation of this ‘Dynamic Programming with bitmask’ solution
is given in Section 2.2, 3.5, and 8.3.1. Do not be alarmed if you do not understand it yet.
4
CHAPTER 1. INTRODUCTION
c Steven & Felix
In IOIs, the contestants are given 6 tasks over 2 days (8 tasks over 2 days in 2009-2010) that
cover items 1-5 and 10, with a much smaller subset of items 6-10 in Table 1.1. For details,
please refer to the 2009 IOI syllabus [20] and the IOI 1989-2008 problem classification [67].
No Category In This Book Frequency
1. Ad Hoc Section 1.4 1-2
2. Complete Search (Iterative/Recursive) Section 3.2 1-2
3. Divide and Conquer Section 3.3 0-1
4. Greedy (usually the original ones) Section 3.4 0-1
5. Dynamic Programming (usually the original ones) Section 3.5 1-3
6. Graph Chapter 4 1-2
7. Mathematics Chapter 5 1-2
8. String Processing Chapter 6 1
9. Computational Geometry Chapter 7 1
10. Some Harder/Rare Problems Chapter 8-9 1-2
Total in Set 8-17 (≈≤ 12)
Table 1.1: Recent ACM ICPC (Asia) Regional Problem Types
The classification in Table 1.1 is adapted from [48] and by no means complete. Some tech-
niques, e.g. ‘sorting’, are not classified here as they are ‘trivial’ and usually used only as a
‘sub-routine’ in a bigger problem. We do not include ‘recursion’ as it is embedded in cate-
gories like recursive backtracking or Dynamic Programming. We also omit ‘data structures’
as the usage of efficient data structure can be considered to be integral for solving harder
problems. Of course, problems sometimes require mixed techniques: A problem can be clas-
sified into more than one type. For example, Floyd Warshall’s algorithm is both a solution
for the All-Pairs Shortest Paths (APSP, Section 4.5) graph problem and a Dynamic Pro-
gramming (DP) algorithm (Section 3.5). Prim’s and Kruskal’s algorithms are both solutions
for the Minimum Spanning Tree (MST, Section 4.3) graph problem and Greedy algorithms
(Section 3.4). In Section 8.4, we will discuss (harder) problems that require more than one
algorithms and/or data structures to be solved.
In the (near) future, these classifications may change. One significant example is Dynamic
Programming. This technique was not known before 1940s, nor frequently used in ICPCs or
IOIs before mid 1990s, but it is considered a definite prerequisite today. As an illustration:
There were ≥ 3 DP problems (out of 11) in the recent ICPC World Finals 2010.
However, the main goal is not just to associate problems with the techniques required to
solve them like in Table 1.1. Once you are familiar with most of the topics in this book, you
should also be able to classify problems into the three types in Table 1.2.
To be competitive, that is, do well in a programming contest, you must be able to confidently
and frequently classify problems as type A and minimize the number of problems that you
classify into type B. That is, you need to acquire sufficient algorithm knowledge and develop
your programming skills so that you consider many classical problems to be easy. However,
to win a programming contest, you will also need to develop sharp problem solving skills
(e.g. reducing the given problem to a known problem, identifying subtle hints or special
5
1.2. TIPS TO BE COMPETITIVE
c Steven & Felix
properties in the problem, attacking the problem from a non obvious angle, etc) so that you
(or your team) will be able to derive the required solution to a hard/original type C problem
in IOI or ICPC Regionals/World Finals and do so within the duration of the contest.
Exercise 1.2.1: Read the UVa [47] problems shown in Table 1.3 and determine their problem
types. Two of them have been identified for you. Filling this table is easy after mastering
this book—all the techniques required to solve these problems are discussed in this book.
6
CHAPTER 1. INTRODUCTION
c Steven & Felix
The problem bounds are as important as your algorithm’s time complexity in determining
if your solution is appropriate. Suppose that you can only devise a relatively-simple-to-code
algorithm that runs with a horrendous time complexity of O(n4 ). This may appear to be
an infeasible solution, but if n ≤ 50, then you have actually solved the problem. You can
implement your O(n4 ) algorithm with impunity since 504 is just 6.25M and your algorithm
should still run in around a second.
Note, however, that the order of complexity does not necessarily indicate the actual
number of operations that your algorithm will require. If each iteration involves a large
number of operations (many floating point calculations, or a significant number of constant
sub-loops), or if your implementation has a high ‘constant‘ in its execution (unnecessarily
repeated loops or multiple passes, or even I/O or execution overhead), your code may take
longer to execute than expected. However, this will usually not be the case as the problem
authors should have designed the time limits so that a well-coded algorithm with a suitable
time complexity will achieve an AC verdict.
By analyzing the complexity of your algorithm with the given input bound and the stated
time/memory limit, you can better decide whether you should attempt to implement your
algorithm (which will take up precious time in the ICPCs and IOIs), attempt to improve
your algorithm first, or switch to other problems in the problem set.
As mentioned in the preface of this book, we will not discuss the concept of algorithmic
analysis in details. We assume that you already have this basic skill. There are a multitude
of other reference books (for example, the “Introduction to Algorithms” [7], “Algorithm De-
sign” [38], “Algorithms” [8], etc) that will help you to understand the following prerequisite
concepts/techniques in algorithmic analysis:
• Basic time and space complexity analysis for iterative and recursive algorithms:
– An algorithm with k-nested loops of about n iterations each has O(nk ) complexity.
– If your algorithm is recursive with b recursive calls per level and has L levels, the
algorithm has roughly O(bL) complexity, but this is a only a rough upper bound.
The actual complexity depends on what actions are done per level and whether
pruning is possible.
– A Dynamic Programming algorithm or other iterative routine which processes a
2D n × n matrix in O(k) per cell runs in O(k × n2 ) time. This is explained in
further detail in Section 3.5.
7
1.2. TIPS TO BE COMPETITIVE
c Steven & Felix
Many novice programmers would skip this phase and immediately begin implementing the
first (naı̈ve) algorithm that they can think of only to realize that the chosen data structure
or algorithm is not efficient enough (or wrong). Our advice for ICPC contestants6 : Refrain
from coding until you are sure that your algorithm is both correct and fast enough.
Table 1.4: Rule of thumb time complexities for the ‘Worst AC Algorithm’ for various single-
test-case input sizes n, assuming that your CPU can compute 100M items in 3s.
To help you understand the growth of several common time complexities, and thus help you
judge how fast is ‘enough’, refer to Table 1.4. Variants of such tables are also found in many
other books on data structures and algorithms. This table is written from a programming
contestant’s perspective. Usually, the input size constraints are given in a (good) problem
description. With the assumption that a typical CPU can execute a hundred million opera-
tions in around 3 seconds (the typical time limit in most UVa [47] problems), we can predict
the ‘worst’ algorithm that can still pass the time limit. Usually, the simplest algorithm has
the poorest time complexity, but if it can pass the time limit, just use it!
6
Unlike ICPC, the IOI tasks can usually be solved (partially or fully) using several possible solutions,
each with different time complexities and subtask scores. To gain valuable points, it may be good to use a
brute force solution to score a few points and to understand the problem better. There will be no significant
time penalty as IOI is not a speed contest. Then, iteratively improve the solution to gain more points.
8
CHAPTER 1. INTRODUCTION
c Steven & Felix
From Table 1.4, we see the importance of using good algorithms with small orders of growth
as they allow us to solve problems with larger input sizes. But a faster algorithm is usually
non-trivial and sometimes substantially harder to implement. In Section 3.2.3, we discuss a
few tips that may allow the same class of algorithms to be used with larger input sizes. In
subsequent chapters, we also explain efficient algorithms for various computing problems.
Exercise 1.2.2: Please answer the following questions below using your current knowledge
about classic algorithms and their time complexities. After you have finished reading this
book once, it may be beneficial to attempt this exercise again.
1. There are n webpages (1 ≤ n ≤ 10M). Each webpage i has a page rank ri . You want
to pick the top 10 pages with the highest page ranks. Which method is better?
(a) Load all n webpages’ page rank to memory, sort (Section 2.2) them in descending
page rank order, obtaining the top 10.
(b) Use a priority queue data structure (a heap) (Section 2.3).
3. Given a list L with 10K integers, you need to frequently obtain sum(i, j), i.e. the
sum of L[i] + L[i+1] + ...+ L[j]. Which data structure should you use?
5. You have to compute the shortest path between two vertices on a weighted Directed
Acyclic Graph (DAG) with |V |, |E| ≤ 100K. Which algorithm(s) can be used in a
typical programming contest (that is, with a time limit of approximately 3 seconds)?
9
1.2. TIPS TO BE COMPETITIVE
c Steven & Felix
6. Which algorithm produces a list of the first 10K prime numbers with the best time
complexity? (Section 5.5.1)
(a) Test if n! % m == 0.
(b) The naı̈ve approach above will not work, use: (Section 5.5.1).
8. Question 4, but with a larger set of points: N ≤ 1M and one additional constraint:
The points are randomly scattered on a 2D plane.
9. You want to enumerate all occurrences of a substring P (of length m) in a (long) string
T (of length n), if any. Both n and m have a maximum of 1M characters.
(a) Use the following C++ code snippet:
for (int i = 0; i < n; i++) {
bool found = true;
for (int j = 0; j < m && found; j++)
if (i + j >= n || P[j] != T[i + j]) found = false;
if (found) printf("P is found at index %d in T\n", i);
}
(b) The naı̈ve approach above will not work, use: (Section 6.4 or 6.6).
10
CHAPTER 1. INTRODUCTION
c Steven & Felix
when it crashes (as opposed to core dumps or segmentation faults in C/C++). On the
other hand, C/C++ has its own merits as well. Depending on the problem at hand, either
language may be the better choice for implementing a solution in the shortest time.
Suppose that a problem requires you to compute 25! (the factorial of 25). The answer is
very large: 15,511,210,043,330,985,984,000,000. This far exceeds the largest built-in primitive
integer data type (unsigned long long: 264 − 1). As there is no built-in arbitrary-precision
arithmetic library in C/C++ as of yet, we would have needed to implement one from scratch.
The Java code, however, is exceedingly simple (more details in Section 5.3). In this case,
using Java definitely makes for shorter coding time.
import java.util.Scanner;
import java.math.BigInteger;
Mastering and understanding the full capability of your favourite programming language is
also important. Take this problem with a non-standard input format: the first line of input
is an integer N. This is followed by N lines, each starting with the character ‘0’, followed
by a dot ‘.’, then followed by an unknown number of digits (up to 100 digits), and finally
terminated with three dots ‘...’.
3
0.1227...
0.517611738...
0.7341231223444344389923899277...
#include <cstdio>
using namespace std;
int main() {
scanf("%d\n", &N);
while (N--) { // we simply loop from N, N-1, N-2, ..., 0
scanf("0.%[0-9]...\n", &x); // ‘&’ is optional when x is a char array
// note: if you are surprised with the trick above,
// please check scanf details in www.cppreference.com
printf("the digits are 0.%s\n", x);
} } // return 0;
11
1.2. TIPS TO BE COMPETITIVE
c Steven & Felix
Not many C/C++ programmers are aware of partial regex capabilities built into the C
standard I/O library. Although scanf/printf are C-style I/O routines, they can still be
used in C++ code. Many C++ programmers ‘force’ themselves to use cin/cout all the time
even though it is sometimes not as flexible as scanf/printf and is also far slower.
In programming contests, especially ICPCs, coding time should not be the primary
bottleneck. Once you figure out the ‘worst AC algorithm’ that will pass the given time limit,
you are expected to be able to translate it into a bug-free code and fast!
Now, try some of the exercises below! If you need more than 10 lines of code to solve any
of them, you should revisit and update your knowledge of your programming language(s)!
A mastery of the programming languages you use and their built-in routines is extremely
important and will help you a lot in programming contests.
Exercise 1.2.3: Produce working code that is as concise as possible for the following tasks:
1. Using Java, read in a double
(e.g. 1.4732, 15.324547327, etc.)
echo it, but with a minimum field width of 7 and 3 digits after the decimal point
(e.g. ss1.473 (where ‘s’ denotes a space), s15.325, etc.)
2. Given an integer n (n ≤ 15), print π to n digits after the decimal point (rounded).
(e.g. for n = 2, print 3.14; for n = 4, print 3.1416; for n = 5, prints 3.14159.)
3. Given a date, determine the day of the week (Monday, . . . , Sunday) on that day.
(e.g. 9 August 2010—the launch date of the first edition of this book—is a Monday.)
4. Given n random integers, print the distinct (unique) integers in sorted order.
5. Given the distinct and valid birthdates of n people as triples (DD, MM, YYYY), order
them first by ascending birth months (MM), then by ascending birth dates (DD), and
finally by ascending age.
6. Given a list of sorted integers L of size up to 1M items, determine whether a value v
exists in L with no more than 20 comparisons (more details in Section 2.2).
7. Generate all possible permutations of {‘A’, ‘B’, ‘C’, . . . , ‘J’}, the first N = 10 letters
in the alphabet (see Section 3.2.1).
8. Generate all possible subsets of {0, 1, 2, . . . , N-1}, for N = 20 (see Section 3.2.1).
9. Given a string that represents a base X number, convert it to an equivalent string in
base Y, 2 ≤ X, Y ≤ 36. For example: “FF” in base X = 16 (hexadecimal) is “255” in
base Y1 = 10 (decimal) and “11111111” in base Y2 = 2 (binary). See Section 5.3.2.
10. Let’s define a ‘special word’ as a lowercase alphabet followed by two consecutive digits.
Given a string, replace all ‘special words’ of length 3 with 3 stars “***”, e.g.
S = “line: a70 and z72 will be replaced, aa24 and a872 will not”
should be transformed into:
S = “line: *** and *** will be replaced, aa24 and a872 will not”.
11. Given a valid mathematical expression involving ‘+’, ‘-’, ‘*’, ‘/’, ‘(’, and ‘)’ in a single
line, evaluate that expression. (e.g. a rather complicated but valid expression 3 + (8 -
7.5) * 10 / 5 - (2 + 5 * 7) should produce -33.0 when evaluated with standard
operator precedence.)
12
CHAPTER 1. INTRODUCTION
c Steven & Felix
13
1.2. TIPS TO BE COMPETITIVE
c Steven & Felix
that are ‘hidden’ or implied within the problem description. These cases are usually
included in the judge’s secret test cases but not in the sample input and output. Corner
cases typically occur at extreme values such as N = 0, N = 1, negative values, large
final (and/or intermediate) values that does not fit 32-bit signed integer, etc.
4. Your test cases should include large cases. Increase the input size incrementally up to
the maximum input bounds stated in the problem description. Use large test cases with
trivial structures that are easy to verify with manual computation and large random
test cases to test if your code terminates in time and still produces reasonable output
(since the correctness would be difficult to verify here). Sometimes your program may
work for small test cases, but produces wrong answer, crashes, or exceeds the time
limit when the input size increases. If that happens, check for overflows, out of bound
errors, or improve your algorithm.
5. Though this is rare in modern programming contests, do not assume that the input
will always be nicely formatted if the problem description does not explicitly state it
(especially for a badly written problem). Try inserting additional whitespace (spaces,
tabs) in the input and test if your code is still able to obtain the values correctly
without crashing.
However, after carefully following all these steps, you may still get non-AC verdicts. In
ICPC, you (and your team) can actually consider the judge’s verdict and the leader board
(usually available for the first four hours of the contest) in determining your next course of
action. In IOI 2010-2012, contestants have a limited number of tokens to use for checking
the correctness of their submitted code against the secret test cases. With more experience
in such contests, you will be able to make better judgments and choices.
1. You receive a WA verdict for a very easy problem. What should you do?
14
CHAPTER 1. INTRODUCTION
c Steven & Felix
6. Thirty minutes into the contest, you take a glance at the leader board. There are many
other teams that have solved a problem X that your team has not attempted. What
should you do?
7. Midway through the contest, you take a glance at the leader board. The leading team
(assume that it is not your team) has just solved problem Y . What should you do?
8. Your team has spent two hours on a nasty problem. You have submitted several im-
plementations by different team members. All submissions have been judged incorrect.
You have no idea what’s wrong. What should you do?
9. There is one hour to go before the end of the contest. You have 1 WA code and 1 fresh
idea for another problem. What should you (or your team) do?
(a) Abandon the problem with the WA code, switch to the other problem in an
attempt to solve one more problem.
(b) Insist that you have to debug the WA code. There is not enough time to start
working on a new problem.
(c) (In ICPC): Print the WA code. Ask two other team members to scrutinize it while
you switch to that other problem in an attempt to solve two more problems.
Figure 1.2: Left: University of Valladolid Online Judge; Right: ACM ICPC Live Archive.
15
1.3. GETTING STARTED: THE EASY PROBLEMS
c Steven & Felix
The USA Computing Olympiad has a very useful training website [48] with online contests
to help you learn programming and problem solving skills. This is geared for IOI participants
more than for ICPC participants. Go straight to their website and train.
The Sphere Online Judge [61] is another online judge where qualified users can add their
problems. This online judge is quite popular in countries like Poland, Brazil, and Vietnam.
We have used this SPOJ to publish some of our self-authored problems.
Figure 1.3: Left: USACO Training Gateway; Right: Sphere Online Judge
TopCoder arranges frequent ‘Single Round Match’ (SRM) [32] that consists of a few problems
to be solved in 1-2 hours. After the contest, you are given the chance to ‘challenge’ other
contestants code by supplying tricky test cases. This online judge uses a rating system (red,
yellow, blue, etc coders) to reward contestants who are really good at problem solving with a
higher rating as opposed to more diligent contestants who happen to solve a higher number
of easier problems.
• Practice coding on blank paper. (This is useful when your teammate is using the
computer. When it is your turn to use the computer, you can then just type the code
as fast as possible rather than spending time thinking in front of the computer.)
• The ‘submit and print’ strategy: If your code gets an AC verdict, ignore the printout.
If it still is not AC, debug your code using that printout (and let your teammate uses
the computer for other problem). Beware: Debugging without the computer is not an
easy skill to master.
• If your teammate is currently coding his algorithm, prepare challenges for his code by
preparing hard corner-case test data (hopefully his code passes all those).
• The X-factor: Befriend your teammates outside of training sessions and contests.
16
CHAPTER 1. INTRODUCTION
c Steven & Felix
unimportant details and focus on the essential ones. For example, the entire opening
paragraphs except the last sentence in UVa 579 - ClockHands are about the history of
the clock and is completely unrelated to the actual problem. However, harder problems
are usually written as succinctly as possible—they are already difficult enough without
additional embellishment.
• Input and Output description. In this section, you will be given details on how
the input is formatted and on how you should format your output. This part is usually
written in a formal manner. A good problem should have clear input constraints as the
same problem might be solvable with different algorithms for different input constraints
(see Table 1.4).
• Sample Input and Sample Output. Problem authors usually only provide trivial
test cases to contestants. The sample input/output is intended for contestants to check
their basic understanding of the problem and to verify if their code can parse the given
input using the given input format and produce the correct output using the given
output format. Do not submit your code to the judge if it does not even pass the given
sample input/output. See Section 1.2.5 about testing your code before submission.
• Hints or Footnotes. In some cases, the problem authors may drop hints or add
footnotes to further describe the problem.
• The number of test cases is given in the first line of the input.
• The multiple test cases are terminated by special values (usually zeroes).
• The multiple test cases are terminated by the EOF (end-of-file) signal.
17
1.3. GETTING STARTED: THE EASY PROBLEMS
c Steven & Felix
---------------------------------------------------------------------------
int a, b; | 1 2 | 3
// scanf returns the number of items read | 5 7 | 12
while (scanf("%d %d", &a, &b) == 2) | 6 3 | 9
// or you can check for EOF, i.e. |--------------|--------------
// while (scanf("%d %d", &a, &b) != EOF) | |
printf("%d\n", a + b); | |
Some other problems require us to output blank lines only between test cases. If we use the
approach above, we will end up with an extra new line at the end of our output, producing
unnecessary ‘Presentation Error’ (PE) verdict. We should use the following code instead:
18
CHAPTER 1. INTRODUCTION
c Steven & Felix
int k, ans, v; | 1 1 | 1
while (scanf("%d", &k) != EOF) { | 2 3 4 | 7
ans = 0; | 3 8 1 1 | 10
while (k--) { scanf("%d", &v); ans += v; } | 4 7 2 9 3 | 21
printf("%d\n", ans); | 5 1 1 1 1 1 | 5
} |--------------|--------------
Exercise 1.3.1*: What if the problem author decides to make the input a little more
problematic? Instead of an integer k at the beginning of each test case, you are now required
to sum all integers in each test case (each line). Hint: See Section 6.2.
Exercise 1.3.2*: Rewrite all C/C++ source code in this Section 1.3.2 in Java!
• Super Easy
You should get these problems AC9 in under 7 minutes10 each! If you are new to com-
petitive programming, we strongly recommend that you start your journey by solving
some problems from this category after completing the previous Section 1.3.2. Note:
Since each category contains numerous problems for you to try, we have highlighted a
maximum of three (3) must try * problems in each category. These are the problems
that, we think, are more interesting or are of higher quality.
• Easy
We have broken up the ‘Easy’ category into two smaller ones. The problems in this
category are still easy, but just ‘a bit’ harder than the ‘Super Easy’ ones.
• Super Easy Problems in the UVa Online Judge (solvable in under 7 minutes)
1. UVa 00272 - TEX Quotes (replace all double quotes to TEX() style quotes)
2. UVa 01124 - Celebrity Jeopardy (LA 2681, just echo/re-print the input again)
3. UVa 10550 - Combination Lock (simple, do as asked)
4. UVa 11044 - Searching for Nessy (one liner code/formula exists)
5. UVa 11172 - Relational Operators * (ad hoc, very easy, one liner)
6. UVa 11364 - Parking (linear scan to get l & r, answer = 2 ∗ (r − l))
7. UVa 11498 - Division of Nlogonia * (just use if-else statements)
9
Do not feel bad if you are unable to do so. There can be many reasons why a code may not get AC.
10
Seven minutes is just a rough estimate. Some of these problems can be solved with one-liners.
19
1.3. GETTING STARTED: THE EASY PROBLEMS
c Steven & Felix
20
CHAPTER 1. INTRODUCTION
c Steven & Felix
The categories:
• Game (Card)
There are lots of Ad Hoc problems involving popular games. Many are related to card
games. You will usually need to parse the input strings (see Section 6.3) as playing
cards have both suits (D/Diamond/♦, C/Club/♣, H/Heart/♥, and S/Spades/♠) and
ranks (usually: 2 < 3 < . . . < 9 < T/Ten < J/Jack < Q/Queen < K/King < A/Ace12 ).
It may be a good idea to map these troublesome strings to integer indices. For example,
one possible mapping is to map D2 → 0, D3 → 1, . . . , DA → 12, C2 → 13, C3 → 14,
. . . , SA → 51. Then, you can work with the integer indices instead.
• Game (Chess)
Chess is another popular game that sometimes appears in programming contest prob-
lems. Some of these problems are Ad Hoc and listed in this section. Some of them are
combinatorial with tasks like counting how many ways there are to place 8-queens in
8 × 8 chess board. These are listed in Chapter 3.
21
1.4. THE AD HOC PROBLEMS
c Steven & Felix
Bowling, etc. Knowing the details of these games may be helpful, but most of the
game rules are given in the problem description to avoid disadvantaging contestants
who are unfamiliar with the games.
• Problems related to Palindromes
These are also classic problems. A palindrome is a word (or a sequence) that can
be read the same way in either direction. The most common strategy to check if a
word is palindromic is to loop from the first character to the middle one and check
if the characters match in the corresponding position from the back. For example,
‘ABCDCBA’ is a palindrome. For some harder palindrome-related problems, you
may want to check Section 6.5 for Dynamic Programming solutions.
• Problems related to Anagrams
This is yet another class of classic problems. An anagram is a word (or phrase) whose
letters can be rearranged to obtain another word (or phrase). The common strategy
to check if two words are anagrams is to sort the letters of the words and compare
the results. For example, take wordA = ‘cab’, wordB = ‘bca’. After sorting, wordA
= ‘abc’ and wordB = ‘abc’ too, so they are anagrams. See Section 2.2 for various
sorting techniques.
• Interesting Real Life Problems, easier and harder (or more tedious)
This is one of the most interesting problem categories in the UVa Online Judge. We
believe that real life problems like these are interesting to those who are new to Com-
puter Science. The fact that we write programs to solve real life problems can be
an additional motivational boost. Who knows, you might stand to gain new (and
interesting) information from the problem description!
• Ad Hoc problems involving Time
These problems utilize time concepts such as dates, times, and calendars. These are
also real life problems. As mentioned earlier, these problems can be a little more
interesting to solve. Some of these problems will be far easier to solve if you have
mastered the Java GregorianCalendar class as it has many library functions that deal
with time.
• ‘Time Waster’ problems
These are Ad Hoc problems that are written specifically to make the required solution
long and tedious. These problems, if they do appear in a programming contest, would
determine the team with the most efficient coder—someone who can implement com-
plicated but still accurate solutions under time constraints. Coaches should consider
adding such problems in their training programmes.
• Ad Hoc problems in other chapters
There are many other Ad Hoc problems which we have shifted to other chapters since
they required knowledge above basic programming skills.
– Ad Hoc problems involving the usage of basic linear data structures (especially
arrays) are listed in Section 2.2.
– Ad Hoc problems involving mathematical computation are listed in Section 5.2.
– Ad Hoc problems involving string processing are listed in Section 6.3.
– Ad Hoc problems involving basic geometry are listed in Section 7.2.
– Ad Hoc problems listed in Chapter 9.
22
CHAPTER 1. INTRODUCTION
c Steven & Felix
Tips: After solving a number of programming problems, you begin to realize a pat-
tern in your solutions. Certain idioms are used frequently enough in competitive pro-
gramming implementation for shortcuts to be useful. From a C/C++ perspective,
these idioms might include: Libraries to be included (cstdio, cmath, cstring, etc),
data type shortcuts (ii, vii, vi, etc), basic I/O routines (freopen, multiple input for-
mat, etc), loop macros (e.g. #define REP(i, a, b) for (int i = int(a); i <=
int(b); i++), etc), and a few others. A competitive programmer using C/C++ can
store these in a header file like ‘competitive.h’. With such a header, the solution to
every problem begins with a simple #include<competitive.h>. However, this tips
should not be used beyond competitive programming, especially in software industry.
• Game (Card)
1. UVa 00162 - Beggar My Neighbour (card game simulation; straightforward)
2. UVa 00462 - Bridge Hand Evaluator * (simulation; card)
3. UVa 00555 - Bridge Hands (card game)
4. UVa 10205 - Stack ’em Up (card game)
5. UVa 10315 - Poker Hands (tedious problem)
6. UVa 10646 - What is the Card? * (shuffle cards with some rule and
then get certain card)
7. UVa 11225 - Tarot scores (another card game)
8. UVa 11678 - Card’s Exchange (actually just an array manipulation problem)
9. UVa 12247 - Jollo * (interesting card game; simple, but requires good
logic to get all test cases correct)
• Game (Chess)
1. UVa 00255 - Correct Move (check the validity of chess moves)
2. UVa 00278 - Chess * (ad hoc, chess, closed form formula exists)
3. UVa 00696 - How Many Knights * (ad hoc, chess)
4. UVa 10196 - Check The Check (ad hoc chess game, tedious)
5. UVa 10284 - Chessboard in FEN * (FEN = Forsyth-Edwards Notation
is a standard notation for describing board positions in a chess game)
6. UVa 10849 - Move the bishop (chess)
7. UVa 11494 - Queen (ad hoc, chess)
• Game (Others), Easier
1. UVa 00340 - Master-Mind Hints (determine strong and weak matches)
2. UVa 00489 - Hangman Judge * (just do as asked)
3. UVa 00947 - Master Mind Helper (similar to UVa 340)
4. UVa 10189 - Minesweeper * (simulate Minesweeper, similar to UVa 10279)
5. UVa 10279 - Mine Sweeper (a 2D array helps, similar to UVa 10189)
6. UVa 10409 - Die Game (just simulate the die movement)
7. UVa 10530 - Guessing Game (use a 1D flag array)
8. UVa 11459 - Snakes and Ladders * (simulate it, similar to UVa 647)
9. UVa 12239 - Bingo (try all 902 pairs, see if all numbers in [0..N] are there)
23
1.4. THE AD HOC PROBLEMS
c Steven & Felix
24
CHAPTER 1. INTRODUCTION
c Steven & Felix
25
1.4. THE AD HOC PROBLEMS
c Steven & Felix
26
CHAPTER 1. INTRODUCTION
c Steven & Felix
3. If list L is static, (b) Simple Array that is pre-processed with Dynamic Programming
(Section 2.2 & 3.5). If list L is dynamic, then (g) Fenwick Tree is a better answer
(easier to implement than (f) Segment Tree).
7. (b) The naı̈ve approach above will not work. We must (prime) factorize n! and m and
see if the (prime) factors of m can be found in the factors of n! (Section 5.5.5).
8. (b) No, we must find another way. First, find the Convex Hull of the N points in
O(n log n) (Section 7.3.7). Let the number of points in CH(S) = k. As the points are
randomly scattered, k will be much smaller than N. Then, find the two farthest points
by examining all pairs of points in the CH(S) in O(k 2 ).
9. (b) The naı̈ve approach is too slow. Use KMP or Suffix Array (Section 6.4 or 6.6)!
27
1.5. SOLUTIONS TO NON-STARRED EXERCISES
c Steven & Felix
// Java code for task 1, assuming all necessary imports have been done
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
double d = sc.nextDouble();
System.out.printf("%7.3f\n", d); // yes, Java has printf too!
} }
// C++ code for task 2, assuming all necessary includes have been done
int main() {
double pi = 2 * acos(0.0); // this is a more accurate way to compute pi
int n; scanf("%d", &n);
printf("%.*lf\n", n, pi); // this is the way to manipulate field width
}
// Java code for task 3, assuming all necessary imports have been done
class Main {
public static void main(String[] args) {
String[] names = new String[]
{ "", "Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat" };
Calendar calendar = new GregorianCalendar(2010, 7, 9); // 9 August 2010
// note that month starts from 0, so we need to put 7 instead of 8
System.out.println(names[calendar.get(Calendar.DAY_OF_WEEK)]); // "Wed"
} }
// C++ code for task 4, assuming all necessary includes have been done
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
int main() {
int a[] = {1, 2, 2, 2, 3, 3, 2, 2, 1};
vector<int> v(a, a + 9);
sort(ALL(v)); UNIQUE(v);
for (int i = 0; i < (int)v.size(); i++) printf("%d\n", v[i]);
}
// C++ code for task 5, assuming all necessary includes have been done
typedef pair<int, int> ii; // we will utilize the natural sort order
typedef pair<int, ii> iii; // of the primitive data types that we paired
int main() {
iii A = make_pair(ii(5, 24), -1982); // reorder DD/MM/YYYY
iii B = make_pair(ii(5, 24), -1980); // to MM, DD,
iii C = make_pair(ii(11, 13), -1983); // and then use NEGATIVE YYYY
vector<iii> birthdays;
birthdays.push_back(A); birthdays.push_back(B); birthdays.push_back(C);
sort(birthdays.begin(), birthdays.end()); // that’s all :)
}
28
CHAPTER 1. INTRODUCTION
c Steven & Felix
// C++ code for task 6, assuming all necessary includes have been done
int main() {
int n = 5, L[] = {10, 7, 5, 20, 8}, v = 7;
sort(L, L + n);
printf("%d\n", binary_search(L, L + n, v));
}
// C++ code for task 7, assuming all necessary includes have been done
int main() {
int p[10], N = 10; for (int i = 0; i < N; i++) p[i] = i;
do {
for (int i = 0; i < N; i++) printf("%c ", ’A’ + p[i]);
printf("\n");
}
while (next_permutation(p, p + N));
}
// C++ code for task 8, assuming all necessary includes have been done
int main() {
int p[20], N = 20;
for (int i = 0; i < N; i++) p[i] = i;
for (int i = 0; i < (1 << N); i++) {
for (int j = 0; j < N; j++)
if (i & (1 << j)) // if bit j is on
printf("%d ", p[j]); // this is part of set
printf("\n");
} }
// Java code for task 9, assuming all necessary imports have been done
class Main {
public static void main(String[] args) {
String str = "FF"; int X = 16, Y = 10;
System.out.println(new BigInteger(str, X).toString(Y));
} }
// Java code for task 10, assuming all necessary imports have been done
class Main {
public static void main(String[] args) {
String S = "line: a70 and z72 will be replaced, aa24 and a872 will not";
System.out.println(S.replaceAll("(^| )+[a-z][0-9][0-9]( |$)+", " *** "));
} }
// Java code for task 11, assuming all necessary imports have been done
class Main {
public static void main(String[] args) throws Exception {
ScriptEngineManager mgr = new ScriptEngineManager();
ScriptEngine engine = mgr.getEngineByName("JavaScript"); // "cheat"
Scanner sc = new Scanner(System.in);
while (sc.hasNextLine()) System.out.println(engine.eval(sc.nextLine()));
} }
29
1.5. SOLUTIONS TO NON-STARRED EXERCISES
c Steven & Felix
30
CHAPTER 1. INTRODUCTION
c Steven & Felix
8. Your team has spent two hours on a nasty problem. You have submitted several im-
plementations by different team members. All submissions have been judged incorrect.
You have no idea what’s wrong. What should you do?
(It is time to give up solving this problem. Do not hog the computer, let
your team mate solves another problem. Either your team has really mis-
understood the problem or in a very rare case, the judge solution is actually
wrong. In any case, this is not a good situation for your team.)
9. There is one hour to go before the end of the contest. You have 1 WA code and 1 fresh
idea for another problem. What should you (or your team) do?
(In chess terminology, this is called the ‘end game’ situation.)
(a) Abandon the problem with the WA code, switch to the other problem in an
attempt to solve one more problem.(OK in individual contests like IOI.)
(b) Insist that you have to debug the WA code. There is not enough time to start
working on a new problem. (If the idea for another problem involves com-
plex and tedious code, then deciding to focus on the WA code may be
a good idea rather than having two incomplete/‘non AC’ solutions.)
(c) (In ICPC): Print the WA code. Ask two other team members to scrutinize it while
you switch to that other problem in an attempt to solve two more problems.
(If the solution for the other problem can be coded in less than 30
minutes, then implement it while your team mates try to find the bug
for the WA code by studying the printed copy.)
Figure 1.4: Some references that inspired the authors to write this book
31
1.6. CHAPTER NOTES
c Steven & Felix
• To improve your typing skill as mentioned in Tip 1, you may want to play the many
typing games available online.
• Tip 2 is adapted from the introduction text in USACO training gateway [48].
• More details about Tip 3 can be found in many CS books, e.g. Chapter 1-5, 17 of [7].
• Online references for Tip 4:
http://www.cppreference.com and http://www.sgi.com/tech/stl/ for C++ STL;
http://docs.oracle.com/javase/7/docs/api/ for Java API.
You do not have to memorize all library functions, but it is useful to memorize functions
that you frequently use.
• For more insights on better testing (Tip 5), a slight detour to software engineering
books may be worth trying.
• There are many other Online Judges apart from those mentioned in Tip 6, e.g.
– Codeforces, http://codeforces.com/,
– Peking University Online Judge, (POJ) http://poj.org,
– Zhejiang University Online Judge, (ZOJ) http://acm.zju.edu.cn,
– Tianjin University Online Judge, http://acm.tju.edu.cn/toj,
– Ural State University (Timus) Online Judge, http://acm.timus.ru,
– URI Online Judge, http://www.urionlinejudge.edu.br, etc.
In this chapter, we have introduced the world of competitive programming to you. However,
a competitive programmer must be able to solve more than just Ad Hoc problems in a
programming contest. We hope that you will enjoy the ride and fuel your enthusiasm by
reading up on and learning new concepts in the other chapters of this book. Once you have
finished reading the book, re-read it once more. On the second time, attempt and solve the
≈ 238 written exercises and the ≈ 1675 programming exercises.
32
Chapter 2
33
2.1. OVERVIEW AND MOTIVATION
c Steven & Felix
Another strength of this book is the collection of both written and programming exercises
(mostly supported by the UVa Online Judge [47] and integrated with uHunt—see Appendix
A). In the third edition, we have added many more written exercises. We have classified the
written exercises into non-starred and starred ones. The non-starred written exercises are
meant to be used mainly for self-checking purposes; solutions are given at the back of each
chapter. The starred written exercises can be used for extra challenges; we do not provide
solutions for these but may instead provide some helpful hints.
In the third edition, we have added visualizations4 for many data structures and algo-
rithms covered in this book [27]. We believe that these visualizations will be a huge benefit
to the visual learners in our reader base. At this point in time (24 May 2013), the visualiza-
tions are hosted at: www.comp.nus.edu.sg/∼stevenha/visualization. The reference to
each visualization is included in the body text as a box like the one shown below.
Visualization: www.comp.nus.edu.sg/∼stevenha/visualization
3
However, we have chosen not to include code from Section 2.2-2.3 in the body text because they are
mostly ‘trivial’ for many readers, except perhaps for a few useful tricks.
4
They are built with HTML5 canvas and JavaScript technology.
34
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
35
2.2. LINEAR DS WITH BUILT-IN LIBRARIES
c Steven & Felix
There are generally three common methods to search for an item in an array:
1. O(n) Linear Search: Consider every element from index 0 to index n − 1 (avoid
this whenever possible).
2. O(log n) Binary Search: Use lower bound, upper bound, or binary search in
C++ STL algorithm (or Java Collections.binarySearch). If the input array is
unsorted, it is necessary to sort the array at least once (using one of the O(n log n)
sorting algorithm above) before executing one (or many) Binary Search(es).
3. O(1) with Hashing: This is a useful technique to use when fast access to known
values are required. If a suitable hash function is selected, the probability of a
collision to be made is negligibly small. Still, this technique is rarely used and we
can live without it6 for most (contest) problems.
Visualization: www.comp.nus.edu.sg/∼stevenha/visualization/sorting.html
Source code: ch2 02 algorithm collections.cpp/java
1. Representation: A 32 (or 64)-bit signed integer for up to 32 (or 64) items7 . With-
out a loss of generality, all examples below use a 32-bit signed integer called S.
6
However, questions about hashing frequently appear in interviews for IT jobs.
7
To avoid issues with the two’s complement representation, use a 32-bit/64-bit signed integer to represent
bitmasks of up to 30/62 items only, respectively.
36
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
37
2.2. LINEAR DS WITH BUILT-IN LIBRARIES
c Steven & Felix
6. To toggle (flip the status of) the j-th item of the set,
use the bitwise XOR operation S ∧ = (1 << j).
7. To get the value of the least significant bit that is on (first from the right),
use T = (S & (-S)).
Example for n = 3
S + 1 = 8 (base 10) = 1000 <- bit ‘1’ is shifted to left 3 times
1
------ -
S = 7 (base 10) = 111 (base 2)
Example for n = 5
S + 1 = 32 (base 10) = 100000 <- bit ‘1’ is shifted to left 5 times
1
-------- -
S = 31 (base 10) = 11111 (base 2)
Visualization: www.comp.nus.edu.sg/∼stevenha/visualization/bitmask.html
Source code: ch2 03 bit manipulation.cpp/java
Many bit manipulation operations are written as preprocessor macros in our C/C++
example source code (but written plainly in our Java example code since Java does
not support macros).
38
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
The only exception is probably UVa 11988 - Broken Keyboard (a.k.a. Beiju Text)—
where you are required to dynamically maintain a (linked) list of characters and effi-
ciently insert a new character anywhere in the list, i.e. at front (head), current, or back
(tail) of the (linked) list. Out of 1903 UVa problems that the authors have solved, this
is likely to be the only pure linked list problem we have encountered thus far.
Visualization: www.comp.nus.edu.sg/∼stevenha/visualization/list.html
Source code: ch2 04 stack queue.cpp/java
Exercise 2.2.1*: Suppose you are given an unsorted array S of n integers. Solve each
of the following tasks below with the best possible algorithms that you can think of and
analyze their time complexities. Let’s assume the following constraints: 1 ≤ n ≤ 100K so
that O(n2 ) solutions are theoretically infeasible in a contest environment.
1. Determine if S contains one or more pairs of duplicate integers.
2*. Given an integer v, find two integers a, b ∈ S such that a + b = v.
3*. Follow-up to Question 2: what if the given array S is already sorted ?
4*. Print the integers in S that fall between a range [a . . . b] (inclusive) in sorted order.
5*. Determine the length of the longest increasing contiguous sub-array in S.
6. Determine the median (50th percentile) of S. Assume that n is odd.
9
The Java Queue is only an interface that is usually instantiated with Java LinkedList.
10
The Java Deque is also an interface. Deque is usually instantiated with Java LinkedList.
39
2.2. LINEAR DS WITH BUILT-IN LIBRARIES
c Steven & Felix
Exercise 2.2.2: There are several other ‘cool’ tricks possible with bit manipulation tech-
niques but these are rarely used. Please implement these tasks with bit manipulation:
Exercise 2.2.3*: We can also use a resizeable array (C++ STL vector or Java Vector) to
implement an efficient stack. Figure out how to achieve this. Follow up question: Can we
use a static array, linked list, or deque instead? Why or why not?
Exercise 2.2.4*: We can use a linked list (C++ STL list or Java LinkedList) to imple-
ment an efficient queue (or deque). Figure out how to achieve this. Follow up question: Can
we use a resizeable array instead? Why or why not?
Programming exercises involving linear data structures (and algorithms) with libraries:
• 1D Array Manipulation, e.g. array, C++ STL vector (or Java Vector/ArrayList)
1. UVa 00230 - Borrowers (a bit of string parsing, see Section 6.2; maintain list
of sorted books; sort key: author names first and if ties, by title; the input
size is small although not stated; we do not need to use balanced BST)
2. UVa 00394 - Mapmaker (any n-dimensional array is stored in computer mem-
ory as a single dimensional array; follow the problem description)
3. UVa 00414 - Machined Surfaces (get longest stretch of ‘B’s)
4. UVa 00467 - Synching Signals (linear scan, 1D boolean flag)
5. UVa 00482 - Permutation Arrays (you may need to use a string tokenizer—
see Section 6.2—as the size of the array is not specified)
6. UVa 00591 - Box of Bricks (sum all items; get the average; sum the total
absolute differences of each item from the average divided by two)
7. UVa 00665 - False Coin (use 1D boolean flags; all coins are initially potential
false coins; if ‘=’, all coins on the left and right are not false coins; if ‘<’ or
‘>’, all coins not on the left and right are not false coins; check if there is
only one candidate false coin left at the end)
8. UVa 00755 - 487-3279 (Direct Addressing Table; convert the letters except
Q & Z to 2-9; keep ‘0’-‘9’ as 0-9; sort the integers; find duplicates if any)
40
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
9. UVa 10038 - Jolly Jumpers * (use 1D boolean flags to check [1..n − 1])
10. UVa 10050 - Hartals (1D boolean flag)
11. UVa 10260 - Soundex (Direct Addressing Table for soundex code mapping)
12. UVa 10978 - Let’s Play Magic (1D string array manipulation)
13. UVa 11093 - Just Finish it up (linear scan, circular array, a bit challenging)
14. UVa 11192 - Group Reverse (character array)
15. UVa 11222 - Only I did it (use several 1D arrays to simplify this problem)
16. UVa 11340 - Newspaper * (DAT; see Hashing in Section 2.3)
17. UVa 11496 - Musical Loop (store data in 1D array, count the peaks)
18. UVa 11608 - No Problem (use three arrays: created; required; available)
19. UVa 11850 - Alaska (for each integer location from 0 to 1322; can Brenda
reach (anywhere within 200 miles of) any charging stations?)
20. UVa 12150 - Pole Position (simple manipulation)
21. UVa 12356 - Army Buddies * (similar to deletion in doubly linked lists,
but we can still use a 1D array for the underlying data structure)
• 2D Array Manipulation
1. UVa 00101 - The Blocks Problem (‘stack’ like simulation; but we need to
access the content of each stack too, so it is better to use 2D array)
2. UVa 00434 - Matty’s Blocks (a kind of visibility problem in geometry, solvable
with using 2D array manipulation)
3. UVa 00466 - Mirror Mirror (core functions: rotate and reflect)
4. UVa 00541 - Error Correction (count the number of ‘1’s for each row/col; all
of them must be even; if ∃ an error, check if it is on the same row and col)
5. UVa 10016 - Flip-flop the Squarelotron (tedious)
6. UVa 10703 - Free spots (use 2D boolean array of size 500 × 500)
7. UVa 10855 - Rotated squares * (string array, 90o clockwise rotation)
8. UVa 10920 - Spiral Tap * (simulate the process)
9. UVa 11040 - Add bricks in the wall (non trivial 2D array manipulation)
10. UVa 11349 - Symmetric Matrix (use long long to avoid issues)
11. UVa 11360 - Have Fun with Matrices (do as asked)
12. UVa 11581 - Grid Successors * (simulate the process)
13. UVa 11835 - Formula 1 (do as asked)
14. UVa 12187 - Brothers (simulate the process)
15. UVa 12291 - Polyomino Composer (do as asked, a bit tedious)
16. UVa 12398 - NumPuzz I (simulate backwards, do not forget to mod 10)
• C++ STL algorithm (Java Collections)
1. UVa 00123 - Searching Quickly (modified comparison function, use sort)
2. UVa 00146 - ID Codes * (use next permutation)
3. UVa 00400 - Unix ls (this command very frequently used in UNIX)
4. UVa 00450 - Little Black Book (tedious sorting problem)
5. UVa 00790 - Head Judge Headache (similar to UVa 10258)
6. UVa 00855 - Lunch in Grid City (sort, median)
7. UVa 01209 - Wordfish (LA 3173, Manila06) (STL next and prev permutation)
8. UVa 10057 - A mid-summer night ... (involves the median, use STL sort,
upper bound, lower bound and some checks)
41
2.2. LINEAR DS WITH BUILT-IN LIBRARIES
c Steven & Felix
42
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
• Balanced Binary Search Tree (BST): C++ STL map/set (Java TreeMap/TreeSet)
The BST is one way to organize data in a tree structure. In each subtree rooted at x,
the following BST property holds: Items on the left subtree of x are smaller than x
and items on the right subtree of x are greater than (or equal to) x. This is essentially
an application of the Divide and Conquer strategy (also see Section 3.3). Organizing
the data like this (see Figure 2.2) allows for O(log n) search(key), insert(key),
findMin()/findMax(), successor(key)/predecessor(key), and delete(key) since
in the worst case, only O(log n) operations are required in a root-to-leaf scan (see
[7, 5, 54, 12] for details). However, this only holds if the BST is balanced.
43
2.3. NON-LINEAR DS WITH BUILT-IN LIBRARIES
c Steven & Felix
STL set (and Java TreeSet) only stores the key. For most (contest) problems, we use
a map (to really map information) instead of a set (a set is only useful for efficiently
determining the existence of a certain key). However, there is a small drawback. If we
use the library implementations, it becomes difficult or impossible to augment (add
extra information to) the BST. Please attempt Exercise 2.3.5* and read Section 9.29
for more details.
Visualization: www.comp.nus.edu.sg/∼stevenha/visualization/bst.html
Source code: ch2 05 map set.cpp/java
The (Max) Heap is a useful data structure for modeling a Priority Queue, where the
item with the highest priority (the maximum element) can be dequeued (ExtractMax())
14
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled.
All vertices in the last level must also be filled from left-to-right.
44
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
and a new item v can be enqueued (Insert(v)), both in O(log n) time. The imple-
mentation15 of priority queue is available in the C++ STL queue library (or Java
PriorityQueue). Priority Queues are an important component in algorithms like
Prim’s (and Kruskal’s) algorithms for the Minimum Spanning Tree (MST) problem
(see Section 4.3), Dijkstra’s algorithm for the Single-Source Shortest Paths (SSSP)
problem (see Section 4.4.3), and the A* Search algorithm (see Section 8.2.5).
This data structure is also used to perform partial sort in the C++ STL algorithm
library. One possible implementation is by processing the elements one by one and
creating a Max16 Heap of k elements, removing the largest element whenever its size
exceeds k (k is the number of elements requested by user). The smallest k elements
can then be obtained in descending order by dequeuing the remaining elements in the
Max Heap. As each dequeue operation is O(log k), partial sort has O(n log k) time
complexity17 . When k = n, this algorithm is equivalent to a heap sort. Note that
although the time complexity of a heap sort is also O(n log n), heap sorts are often
slower than quick sorts because heap operations access data stored in distant indices
and are thus not cache-friendly.
Visualization: www.comp.nus.edu.sg/∼stevenha/visualization/heap.html
Source code: ch2 06 priority queue.cpp/java
15
The default C++ STL priority queue is a Max Heap (dequeuing yields items in descending key order)
whereas the default Java PriorityQueue is a Min Heap (yields items in ascending key order). Tips: A Max
Heap containing numbers can easily be converted into a Min Heap (and vice versa) by inserting the negated
keys. This is because negating a set of numbers will reverse their order of appearance when sorted. This
trick is used several times in this book. However, if the priority queue is used to store 32-bit signed integers,
an overflow will occur if −231 is negated as 231 − 1 is the maximum value of a 32-bit signed integer.
16
The default partial sort produces the smallest k elements in ascending order.
17
You may have noticed that the time complexity O(n log k) where k is the output size and n is the input
size. This means that the algorithm is ‘output-sensitive’ since its running time depends not only on the
input size but also on the amount of items that it has to output.
18
Note that C++11 is a new C++ standard, older compilers may not support it yet.
45
2.3. NON-LINEAR DS WITH BUILT-IN LIBRARIES
c Steven & Felix
Exercise 2.3.1: Someone suggested that it is possible to store the key → value pairs
in a sorted array of structs so that we can use the O(log n) binary search for the
example problem above. Is this approach feasible? If no, what is the issue?
Exercise 2.3.2: We will not discuss the basics of BST operations in this book. Instead,
we will use a series of sub-tasks to verify your understanding of BST-related concepts.
We will use Figure 2.2 as an initial reference in all sub-tasks except sub-task 2.
Exercise 2.3.3*: Suppose you are given a reference to the root R of a binary tree
T containing n vertices. You can access a node’s left, right and parent vertices as
well as its key through its reference. Solve each of the following tasks below with the
best possible algorithms that you can think of and analyze their time complexities.
Let’s assume the following constraints: 1 ≤ n ≤ 100K so that O(n2 ) solutions are
theoretically infeasible in a contest environment.
1. Check if T is a BST.
2*. Output the elements in T that are within a given range [a..b] in ascending order.
3*. Output the contents of the leaves of T in descending order.
Exercise 2.3.4*: The inorder traversal (also see Section 4.7.2) of a standard (not
necessarily balanced) BST is known to produce the BST’s element in sorted order and
runs in O(n). Does the code below also produce the BST elements in sorted order?
Can it be made to run in a total time of O(n) instead of O(log n + (n − 1) × log n) =
O(n log n)? If possible, how?
x = findMin(); output x
for (i = 1; i < n; i++) // is this loop O(n log n)?
x = successor(x); output x
Exercise 2.3.5*: Some (hard) problems require us to write our own balanced Bi-
nary Search Tree (BST) implementations due to the need to augment the BST with
additional data (see Chapter 14 of [7]). Challenge: Solve UVa 11849 - CD which is a
pure balanced BST problem with your own balanced BST implementation to test its
performance and correctness.
Exercise 2.3.6: We will not discuss the basics of Heap operations in this book.
Instead, we will use a series of questions to verify your understanding of Heap concepts.
46
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
1. With Figure 2.3 as the initial heap, display the steps taken by Insert(26).
2. After answering question 1 above, display the steps taken by ExtractMax().
Exercise 2.3.7: Is the structure represented by a 1-based compact array (ignoring
index 0) sorted in descending order a Max Heap?
Exercise 2.3.8*: Prove or disprove this statement: “The second largest element in
a Max Heap with n ≥ 3 distinct elements is always one of the direct children of the
root”. Follow up question: What about the third largest element? Where is/are the
potential location(s) of the third largest element in a Max Heap?
Exercise 2.3.9*: Given a 1-based compact array A containing n integers (1 ≤ n ≤
100K) that are guaranteed to satisfy the Max Heap property, output the elements in
A that are greater than an integer v. What is the best algorithm?
Exercise 2.3.10*: Given an unsorted array S of n distinct integers (2k ≤ n ≤ 100000),
find the largest and smallest k (1 ≤ k ≤ 32) integers in S in O(n log k). Note: For this
written exercise, assume that an O(n log n) algorithm is not acceptable.
Exercise 2.3.11*: One heap operation not directly supported by the C++ STL
priority queue (and Java PriorityQueue) is the UpdateKey(index, newKey) oper-
ation, which allows the (Max) Heap element at a certain index to be updated (increased
or decreased). Write your own binary (Max) Heap implementation with this operation.
Exercise 2.3.12*: Another heap operation that may be useful is the DeleteKey(index)
operation to delete (Max) Heap elements at a certain index. Implement this!
Exercise 2.3.13*: Suppose that we only need the DecreaseKey(index, newKey)
operation, i.e. an UpdateKey operation where the update always makes newKey smaller
than its previous value. Can we use a simpler approach than in Exercise 2.3.11? Hint:
Use lazy deletion, we will use this technique in our Dijkstra code in Section 4.4.3.
Exercise 2.3.14*: Is it possible to use a balanced BST (e.g. C++ STL set or Java
TreeSet) to implement a Priority Queue with the same O(log n) enqueue and dequeue
performance? If yes, how? Are there any potential drawbacks? If no, why?
Exercise 2.3.15*: Is there a better way to implement a Priority Queue if the keys are
all integers within a small range, e.g. [0 . . . 100]? We are expecting an O(1) enqueue
and dequeue performance. If yes, how? If no, why?
Exercise 2.3.16: Which non-linear data structure should you use if you have to
support the following three dynamic operations: 1) many insertions, 2) many deletions,
and 3) many requests for the data in sorted order?
Exercise 2.3.17: There are M strings. N of them are unique (N ≤ M). Which non-
linear data structure discussed in this section should you use if you have to index (label)
these M strings with integers from [0..N-1]? The indexing criteria is as follows: The
first string must be given an index of 0; The next different string must be given index
1, and so on. However, if a string is re-encountered, it must be given the same index
as its earlier copy! One application of this task is in constructing the connection graph
from a list of city names (which are not integer indices!) and a list of highways between
these cities (see Section 2.4.1). To do this, we first have to map these city names into
integer indices (which are far more efficient to work with).
47
2.3. NON-LINEAR DS WITH BUILT-IN LIBRARIES
c Steven & Felix
19
This is another way to implement the edge sorting in Kruskal’s algorithm. Our (C++) implementation
shown in Section 4.3.2 simply uses vector + sort instead of priority queue (a heap sort).
48
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
2.4.1 Graph
The graph is a pervasive structure which appears in many Computer Science problems. A
graph (G = (V, E)) in its basic form is simply a set of vertices (V ) and edges (E; storing
connectivity information between vertices in V ). Later in Chapter 3, 4, 8, and 9, we will
explore many important graph problems and algorithms. To prepare ourselves, we will
discuss three basic ways (there are a few other rare structures) to represent a graph G with
V vertices and E edges in this subsection20 .
A). The Adjacency Matrix, usually in the form of a 2D array (see Figure 2.4).
In (programming contest) problems involving graphs, the number of vertices V is usually
known. Thus we can build a ‘connectivity table’ by creating a static 2D array: int
AdjMat[V ][V ]. This has an O(V 2 ) space 21 complexity. For an unweighted graph, set
AdjMat[i][j] to a non-zero value (usually 1) if there is an edge between vertex i-j or
zero otherwise. For a weighted graph, set AdjMat[i][j] = weight(i,j) if there is an
edge between vertex i-j with weight(i,j) or zero otherwise. Adjacency Matrix cannot
be used to store multigraph. For a simple graph without self-loops, the main diagonal
of the matrix contains only zeroes, i.e. AdjMat[i][i] = 0, ∀i ∈ [0..V-1].
An Adjacency Matrix is a good choice if the connectivity between two vertices in a
small dense graph is frequently required. However, it is not recommended for large
sparse graphs as it would require too much space (O(V 2 )) and there would be many
blank (zero) cells in the 2D array. In a competitive setting, it is usually infeasible to
use Adjacency Matrices when the given V is larger than ≈ 1000. Another drawback
of Adjacency Matrix is that it also takes O(V ) time to enumerate the list of neighbors
of a vertex v—an operation common to many graph algorithms—even if a vertex only
has a handful of neighbors. A more compact and efficient graph representation is the
Adjacency List discussed below.
20
The most appropriate notation for the cardinality of a set S is |S|. However, in this book, we will often
overload the meaning of V or E to also mean |V | or |E|, depending on the context.
21
We differentiate between the space and time complexities of data structures. The space complexity is
an asymptotic measure of the memory requirements of a data structure whereas the time complexity is an
asymptotic measure of the time taken to run a certain algorithm or an operation on the data structure.
49
2.4. DATA STRUCTURES WITH OUR OWN LIBRARIES
c Steven & Felix
B). The Adjacency List, usually in the form of a vector of vector of pairs (see Figure 2.4).
Using the C++ STL: vector<vii> AdjList, with vii defined as in:
typedef pair<int, int> ii; typedef vector<ii> vii; // data type shortcuts
Using the Java API: Vector< Vector < IntegerPair > > AdjList.
IntegerPair is a simple Java class that contains a pair of integers like ii above.
In Adjacency Lists, we have a vector of vector of pairs, storing the list of neighbors
of each vertex u as ‘edge information’ pairs. Each pair contains two pieces of informa-
tion, the index of the neighbouring vertex and the weight of the edge. If the graph is
unweighted, simply store the weight as 0, 1, or drop the weight attribute22 entirely. The
space complexity of Adjacency List is O(V + E) because if there are E bidirectional
edges in a (simple) graph, this Adjacency List will only store 2E ‘edge information’
pairs. As E is usually much smaller than V × (V − 1)/2 = O(V 2 )—the maximum num-
ber of edges in a complete (simple) graph, Adjacency Lists are often more space-efficient
than Adjacency Matrices. Note that Adjacency List can be used to store multigraph.
With Adjacency Lists, we can also enumerate the list of neighbors of a vertex v efficiently.
If v has k neighbors, the enumeration will require O(k) time. Since this is one of the
most common operations in most graph algorithms, it is advisable to use Adjacency
Lists as your first choice of graph representation. Unless otherwise stated, most graph
algorithms discussed in this book use the Adjacency List.
C). The Edge List, usually in the form of a vector of triples (see Figure 2.4).
Using the C++ STL: vector< pair<int, ii> > EdgeList.
Using the Java API: Vector< IntegerTriple > EdgeList.
IntegerTriple is a class that contains a triple of integers like pair<int, ii> above.
In the Edge List, we store a list of all E edges, usually in some sorted order. For
directed graphs, we can store a bidirectional edge twice, one for each direction. The
space complexity is clearly O(E). This graph representation is very useful for Kruskal’s
algorithm for MST (Section 4.3.2), where the collection of undirected edges need to
be sorted23 by ascending weight. However, storing graph information in Edge List
complicates many graph algorithms that require the enumeration of edges incident to a
vertex.
Visualization: www.comp.nus.edu.sg/∼stevenha/visualization/graphds.html
Source code: ch2 07 graph ds.cpp/java
Implicit Graph
Some graphs do not have to be stored in a graph data structure or explicitly generated for
the graph to be traversed or operated upon. Such graphs are called implicit graphs. You
will encounter them in the subsequent chapters. Implicit graphs can come in two flavours:
1. The edges can be determined easily.
Example 1: Navigating a 2D grid map (see Figure 2.5.A). The vertices are the cells in
the 2D character grid where ‘.’ represents land and ‘#’ represents an obstacle. The
edges can be determined easily: There is an edge between two neighboring cells in the
22
For simplicity, we will always assume that the second attribute exists in all graph implementations in
this book although it is not always used.
23
pair objects in C++ can be easily sorted. The default sorting criteria is to sort on the first item and
then the second item for tie-breaking. In Java, we can write our own IntegerPair/IntegerTriple class
that implements Comparable.
50
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
grid if they share an N/S/E/W border and if both are ‘.’ (see Figure 2.5.B).
Example 2: The graph of chess knight movements on an 8 × 8 chessboard. The vertices
are the cells in the chessboard. Two squares in the chessboard have an edge between
them if they differ by two squares horizontally and one square vertically (or two squares
vertically and one square horizontally). The first three rows and four columns of a
chessboard are shown in Figure 2.5.C (many other vertices and edges are not shown).
2. The edges can be determined with some rules.
Example: A graph contains N vertices ([1..N]). There is an edge between two vertices
i and j if (i + j) is a prime. See Figure 2.5.D that shows such a graph with N = 5 and
several more examples in Section 8.2.3.
Exercise 2.4.1.1*: Create the Adjacency Matrix, Adjacency List, and Edge List represen-
tations of the graphs shown in Figure 4.1 (Section 4.2.1) and in Figure 4.9 (Section 4.2.9).
Hint: Use the graph data structure visualization tool shown above.
Exercise 2.4.1.2*: Given a (simple) graph in one representation (Adjacency Matrix/AM,
Adjacency List/AL, or Edge List/EL), convert it into another graph representation in the
most efficient way possible! There are 6 possible conversions here: AM to AL, AM to EL,
AL to AM, AL to EL, EL to AM, and EL to AL.
Exercise 2.4.1.3: If the Adjacency Matrix of a (simple) graph has the property that it is
equal to its transpose, what does this imply?
Exercise 2.4.1.4*: Given a (simple) graph represented by an Adjacency Matrix, perform
the following tasks in the most efficient manner. Once you have figured out how to do this
for Adjacency Matrices, perform the same task with Adjacency Lists and then Edge Lists.
1. Count the number of vertices V and directed edges E (assume that a bidirectional
edge is equivalent to two directed edges) of the graph.
2*. Count the in-degree and the out-degree of a certain vertex v.
3*. Transpose the graph (reverse the direction of each edges).
4*. Check if the graph is a complete graph Kn . Note: A complete graph is a simple
undirected graph in which every pair of distinct vertices is connected by a single edge.
5*. Check if the graph is a tree (a connected undirected graph with E = V − 1 edges).
6*. Check if the graph is a star graph Sk . Note: A star graph Sk is a complete bipartite
K1,k graph. It is a tree with only one internal vertex and k leaves.
Exercise 2.4.1.5*: Research other possible methods of representing graphs other than the
ones discussed above, especially for storing special graphs!
51
2.4. DATA STRUCTURES WITH OUR OWN LIBRARIES
c Steven & Felix
52
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
at work. With the heuristic, the path taken from any node to the representative item by
following the chain of ‘parent’ links is effectively minimized.
In Figure 2.6, bottom, isSameSet(0, 4) demonstrates another operation for this data
structure. This function isSameSet(i, j) simply calls findSet(i) and findSet(j) and
checks if both refer to the same representative item. If they do, then ‘i’ and ‘j’ both belong
to the same set. Here, we see that findSet(0) = findSet(p[0]) = findSet(1) = 1 is
not the same as findSet(4)= findSet(p[4]) = findSet(3) = 3. Therefore item 0 and
item 4 belongs to different disjoint sets.
There is a technique that can vastly speed up the findSet(i) function: Path compression.
Whenever we find the representative (root) item of a disjoint set by following the chain of
‘parent’ links from a given item, we can set the parent of all items traversed to point directly
to the root. Any subsequent calls to findSet(i) on the affected items will then result in
only one link being traversed. This changes the structure of the tree (to make findSet(i)
more efficient) but yet preserves the actual constitution of the disjoint set. Since this will
occur any time findSet(i) is called, the combined effect is to render the runtime of the
findSet(i) operation to run in an extremely efficient amortized O(M × α(n)) time.
In Figure 2.7, we demonstrate this ‘path compression’. First, we call unionSet(0, 3).
This time, we set p[1] = 3 and update rank[3] = 2. Now notice that p[0] is unchanged,
i.e. p[0] = 1. This is an indirect reference to the (true) representative item of the set, i.e.
p[0] = 1 → p[1] = 3. Function findSet(i) will actually require more than one step to
53
2.4. DATA STRUCTURES WITH OUR OWN LIBRARIES
c Steven & Felix
traverse the chain of ‘parent’ links to the root. However, once it finds the representative
item, (e.g. ‘x’) for that set, it will compress the path by setting p[i] = x, i.e. findSet(0)
sets p[0] = 3. Therefore, subsequent calls of findSet(i) will be just O(1). This simple
strategy is aptly named the ‘path compression’ heuristic. Note that rank[3] = 2 now no
longer reflects the true height of the tree. This is why rank only reflects the upper bound of
the actual height of the tree. Our C++ implementation is shown below:
Visualization: www.comp.nus.edu.sg/∼stevenha/visualization/ufds.html
Source code: ch2 08 unionfind ds.cpp/java
Exercise 2.4.2.1: There are two more queries that are commonly performed in this data
structure. Update the code provided in this section to support these two queries efficiently:
int numDisjointSets() that returns the number of disjoint sets currently in the structure
and int sizeOfSet(int i) that returns the size of set that currently contains item i.
Exercise 2.4.2.2*: Given 8 disjoint sets: {0, 1, 2, . . . , 7}, please create a sequence of
unionSet(i, j) operations to create a tree with rank = 3! Is this possible for rank = 4?
54
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
55
2.4. DATA STRUCTURES WITH OUR OWN LIBRARIES
c Steven & Felix
Figure 2.8: Segment Tree of Array A = {18, 17, 13, 19, 15, 11, 20} and RMQ(1, 3)
We are now at the root of the left subtree (index 2) that represents segment [0, 3]. This
segment [0, 3] is still larger than the desired RMQ(1, 3). In fact, RMQ(1, 3) intersects
both the left sub-segment [0, 1] (index 4) and the right sub-segment [2, 3] (index 5) of
segment [0, 3], so we have to explore both subtrees (sub-segments).
The left segment [0, 1] (index 4) of [0, 3] (index 2) is not yet inside the RMQ(1, 3),
so another split is necessary. From segment [0, 1] (index 4), we move right to segment
[1, 1] (index 9), which is now inside28 [1, 3]. At this point, we know that RMQ(1, 1) =
st[9] = 1 and we can return this value to the caller. The right segment [2, 3] (index 5)
of [0, 3] (index 2) is inside the required [1, 3]. From the stored value inside this vertex,
we know that RMQ(2, 3) = st[5] = 2. We do not need to traverse further down.
Now, back in the call to segment [0, 3] (index 2), we now have p1 = RMQ(1, 1) = 1
and p2 = RMQ(2, 3) = 2. Because A[p1] > A[p2] since A[1] = 17 and A[2] = 13, we
now have RMQ(1, 3) = p2 = 2. This is the final answer.
Figure 2.9: Segment Tree of Array A = {18, 17, 13, 19, 15, 11, 20} and RMQ(4, 6)
Now let’s take a look at another example: RMQ(4, 6). The execution in Figure 2.9 is as
follows: We again start from the root segment [0, 6] (index 1). Since it is larger than
the RMQ(4, 6), we move right to segment [4, 6] (index 3) as segment [0, 3] (index 2)
is outside. Since this segment exactly represents RMQ(4, 6), we simply return the index of
minimum element that is stored in this vertex, which is 5. Thus RMQ(4, 6) = st[3] = 5.
This data structure allows us to avoid traversing the unnecessary parts of the tree! In the
worst case, we have two root-to-leaf paths which is just O(2 ×log(2n)) = O(log n). Example:
In RMQ(3, 4) = 4, we have one root-to-leaf path from [0, 6] to [3, 3] (index 1 → 2 →
5 → 11) and another root-to-leaf path from [0, 6] to [4, 4] (index 1 → 3 → 6 → 12).
If the array A is static (i.e. unchanged after it is instantiated), then using a Segment
Tree to solve the RMQ problem is overkill as there exists a Dynamic Programming (DP)
solution that requires O(n log n) one-time pre-processing and allows for O(1) per RMQ. This
DP solution will be discussed later in Section 9.33.
Segment Tree is useful if the underlying array is frequently updated (dynamic). For
example, if A[5] is now changed from 11 to 99, then we just need to update the vertices
along the leaf to root path in O(log n). See path: [5, 5] (index 13, st[13] is unchanged)
→ [4, 5] (index 6, st[6] = 4 now) → [4, 6] (index 3, st[3] = 4 now) → [0, 6] (index
28
Segment [L, R] is said to be inside query range [i, j] if L ≥ i && R ≤ j.
56
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
1, st[1] = 2 now) in Figure 2.10. For comparison, the DP solution presented in Section
9.33 requires another O(n log n) pre-processing to update the structure and is ineffective for
such dynamic updates.
Figure 2.10: Updating Array A to {18, 17, 13, 19, 15, 99, 20}
Our Segment Tree implementation is shown below. The code shown here supports only static
RMQs (dynamic updates are left as an exercise to the reader).
// compute the min position in the left and right part of the interval
int p1 = rmq(left(p) , L , (L+R) / 2, i, j);
int p2 = rmq(right(p), (L+R) / 2 + 1, R , i, j);
public:
SegmentTree(const vi &_A) {
A = _A; n = (int)A.size(); // copy content for local usage
st.assign(4 * n, 0); // create large enough vector of zeroes
build(1, 0, n - 1); // recursive build
}
57
2.4. DATA STRUCTURES WITH OUR OWN LIBRARIES
c Steven & Felix
int main() {
int arr[] = { 18, 17, 13, 19, 15, 11, 20 }; // the original array
vi A(arr, arr + 7);
SegmentTree st(A);
printf("RMQ(1, 3) = %d\n", st.rmq(1, 3)); // answer = index 2
printf("RMQ(4, 6) = %d\n", st.rmq(4, 6)); // answer = index 5
} // return 0;
Visualization: www.comp.nus.edu.sg/∼stevenha/visualization/segmenttree.html
Source code: ch2 09 segmenttree ds.cpp/java
Exercise 2.4.3.1*: Draw the Segment Tree corresponding to array A = {10, 2, 47, 3,
7, 9, 1, 98, 21}. Answer RMQ(1, 7) and RMQ(3, 8)! Hint: Use the Segment Tree
visualization tool shown above.
Exercise 2.4.3.2*: In this section, we have seen how Segment Trees can be used to answer
Range Minimum Queries (RMQs). Segment Trees can also be used to answer dynamic
Range Sum Queries (RSQ(i, j)), i.e. a sum from A[i] + A[i + 1] + ...+ A[j]. Modify
the given Segment Tree code above to deal with RSQ.
Exercise 2.4.3.3: Using a similar Segment Tree to Exercise 2.4.3.1 above, answer the
queries RSQ(1, 7) and RSQ(3, 8). Is this a good approach to solve the problem if array A
is never changed? (also see Section 3.5.2).
Exercise 2.4.3.4*: The Segment Tree code shown above lacks the (point) update operation
as discussed in the body text. Add the O(log n) update function to update the value of a
certain index (point) in array A and simultaneously update the corresponding Segment Tree!
Exercise 2.4.3.5*: The (point) update operation shown in the body text only changes the
value of a certain index in array A. What if we delete existing elements of array A or insert a
new elements into array A? Can you explain what will happen with the given Segment Tree
code and what you should do to address it?
Exercise 2.4.3.6*: There is also one more important Segment Tree operation that has not
yet been discussed, the range update operation. Suppose a certain subarray of A is updated
to a certain common value. Can we update the Segment Tree efficiently? Study and solve
UVa 11402 - Ahoy Pirates—a problem that requires range updates.
58
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
The cumulative frequency table can also be used as a solution to the Range Sum Query
(RSQ) problem mentioned in Exercise 2.4.3.2*. It stores RSQ(1, i) ∀i ∈ [1..n] where
n is the largest integer index/score30 . In the example above, we have n = 10, RSQ(1, 1)
= 0, RSQ(1, 2) = 1, . . . , RSQ(1, 6) = 7, . . . , RSQ(1, 8) = 10, . . . , and RSQ(1, 10) =
11. We can then obtain the answer to the RSQ for an arbitrary range RSQ(i, j) when
i = 1 by subtracting RSQ(1, j) - RSQ(1, i - 1). For example, RSQ(4, 6) = RSQ(1, 6)
- RSQ(1, 3) = 7 - 1 = 6.
If the frequencies are static, then the cumulative frequency table as in Table 2.1 can
be computed efficiently with a simple O(n) loop. First, set cf[1] = f[1]. Then, for i ∈
[2..n], compute cf[i] = cf[i - 1] + f[i]. This will be discussed further in Section
3.5.2. However, when the frequencies are frequently updated (increased or decreased) and
the RSQs are frequently asked afterwards, it is better to use a dynamic data structure.
Instead of using a Segment Tree to implement a dynamic cumulative frequency table,
we can implement the far simpler Fenwick Tree instead (compare the source code for both
implementations, provided in this section and in the previous Section 2.4.3). This is perhaps
one of the reasons why the Fenwick Tree is currently included in the IOI syllabus [20]. Fen-
wick Tree operations are also extremely efficient as they use fast bit manipulation techniques
(see Section 2.2).
In this section, we will use the function LSOne(i) (which is actually (i & (-i))) exten-
sively, naming it to match its usage in the original paper [18]. In Section 2.2, we have seen
that the operation (i & (-i)) produces the first Least Significant One-bit in i.
29
The test scores are shown in sorted order for simplicity, they do not have to be sorted.
30
Please differentiate m = the number of data points and n = the largest integer value among the m data
points. The meaning of n in Fenwick Tree is a bit different compared to other data structures in this book.
59
2.4. DATA STRUCTURES WITH OUR OWN LIBRARIES
c Steven & Felix
The Fenwick Tree is typically implemented as an array (we use a vector for size flexibil-
ity). The Fenwick Tree is a tree that is indexed by the bits of its integer keys. These integer
keys fall within the fixed range [1..n]—skipping31 index 0. In a programming contest envi-
ronment, n can approach ≈ 1M so that the Fenwick Tree covers the range [1..1M]—large
enough for many practical (contest) problems. In Table 2.1 above, the scores [1..10] are
the integer keys in the corresponding array with size n = 10 and m = 11 data points.
Let the name of the Fenwick Tree array be ft. Then, the element at index i is responsible
for elements in the range [i-LSOne(i)+1..i] and ft[i] stores the cumulative frequency
of elements {i-LSOne(i)+1, i-LSOne(i)+2, i-LSOne(i)+3, .., i}. In Figure 2.11, the
value of ft[i] is shown in the circle above index i and the range [i-LSOne(i)+1..i] is
shown as a circle and a bar (if the range spans more than one index) above index i. We can
see that ft[4] = 2 is responsible for range [4-4+1..4] = [1..4], ft[6] = 5 is responsible
for range [6-2+1..6] = [5..6], ft[7] = 2 is responsible for range [7-1+1..7] = [7..7],
ft[8] = 10 is responsible for range [8-8+1..8] = [1..8] etc32 .
With such an arrangement, if we want to obtain the cumulative frequency between
[1..b], i.e. rsq(b), we simply add ft[b], ft[b’], ft[b’’], . . . until index bi is 0. This
sequence of indices is obtained via subtracting the Least Significant One-bit via the bit ma-
nipulation expression: b’ = b - LSOne(b). Iteration of this bit manipulation effectively
strips off the least significant one-bit of b at each step. As an integer b only has O(log b)
bits, rsq(b) runs in O(log n) time when b = n. In Figure 2.11, rsq(6) = ft[6] + ft[4]
= 5 + 2 = 7. Notice that indices 4 and 6 are responsible for range [1..4] and [5..6],
respectively. By combining them, we account for the entire range of [1..6]. The indices
6, 4, and 0 are related in their binary form: b = 610 = (110)2 can be transformed to b’ =
410 = (100)2 and subsequently to b’’ = 010 = (000)2 .
With rsq(b) available, obtaining the cumulative frequency between two indices [a..b]
where a != 1 is simple, just evaluate rsq(a, b) = rsq(b) - rsq(a - 1). For example, if
we want to compute rsq(4, 6), we can simply return rsq(6) - rsq(3) = (5+2) - (0+1)
= 7 - 1 = 6. Again, this operation runs in O(2 × log b) ≈ O(log n) time when b = n.
Figure 2.12 displays the value of rsq(3).
When updating the value of the element at index k by adjusting its value by v (note
that v can be either positive or negative), i.e. calling adjust(k, v), we have to update
ft[k], ft[k’], ft[k’’], . . . until index ki exceeds n. This sequence of indices are obtained
31
We have chosen to follow the original implementation by [18] that ignores index 0 to facilitate an easier
understanding of the bit manipulation operations of Fenwick Tree. Note that index 0 has no bit turned on.
Thus, the operation i +/- LSOne(i) simply returns i when i = 0. Index 0 is also used as the terminating
condition in the rsq function.
32
In this book, we will not detail why this arrangement works and will instead show that it allows for
efficient O(log n) update and RSQ operations. Interested readers are advised to read [18].
60
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
via this similar iterative bit manipulation expression: k’ = k + LSOne(k). Starting from
any integer k, the operation adjust(k, v) will take at most O(log n) steps until k > n. In
Figure 2.13, adjust(5, 1) will affect (add +1 to) ft[k] at indices k = 510 = (101)2 , k’ =
(101)2 + (001)2 = (110)2 = 610 , and k’’ = (110)2 + (010)2 = (1000)2 = 810 via the
expression given above. Notice that if you project a line upwards from index 5 in Figure
2.13, you will see that the line indeed intersects the ranges under the responsibility of index
5, index 6, and index 8.
In summary, Fenwick Tree supports both RSQ and update operations in just O(n) space and
O(log n) time given a set of m integer keys that ranges from [1..n]. This makes Fenwick
Tree an ideal data structure for solving dynamic RSQ problems on with discrete arrays (the
static RSQ problem can be solved with simple O(n) pre-processing and O(1) per query as
shown earlier). Our short C++ implementation of a basic Fenwick Tree is shown below.
class FenwickTree {
private: vi ft; // recall that vi is: typedef vector<int> vi;
public: FenwickTree(int n) { ft.assign(n + 1, 0); } // init n + 1 zeroes
int rsq(int b) { // returns RSQ(1, b)
int sum = 0; for (; b; b -= LSOne(b)) sum += ft[b];
return sum; } // note: LSOne(S) (S & (-S))
int rsq(int a, int b) { // returns RSQ(a, b)
return rsq(b) - (a == 1 ? 0 : rsq(a - 1)); }
// adjusts value of the k-th element by v (v can be +ve/inc or -ve/dec)
void adjust(int k, int v) { // note: n = ft.size() - 1
for (; k < (int)ft.size(); k += LSOne(k)) ft[k] += v; }
};
61
2.4. DATA STRUCTURES WITH OUR OWN LIBRARIES
c Steven & Felix
int main() {
int f[] = { 2,4,5,5,6,6,6,7,7,8,9 }; // m = 11 scores
FenwickTree ft(10); // declare a Fenwick Tree for range [1..10]
// insert these scores manually one by one into an empty Fenwick Tree
for (int i = 0; i < 11; i++) ft.adjust(f[i], 1); // this is O(k log n)
printf("%d\n", ft.rsq(1, 1)); // 0 => ft[1] = 0
printf("%d\n", ft.rsq(1, 2)); // 1 => ft[2] = 1
printf("%d\n", ft.rsq(1, 6)); // 7 => ft[6] + ft[4] = 5 + 2 = 7
printf("%d\n", ft.rsq(1, 10)); // 11 => ft[10] + ft[8] = 1 + 10 = 11
printf("%d\n", ft.rsq(3, 6)); // 6 => rsq(1, 6) - rsq(1, 2) = 7 - 1
ft.adjust(5, 2); // update demo
printf("%d\n", ft.rsq(1, 10)); // now 13
} // return 0;
Visualization: www.comp.nus.edu.sg/∼stevenha/visualization/bit.html
Source code: ch2 10 fenwicktree ds.cpp/java
Exercise 2.4.4.1: Just a simple exercise of the two basic bit-manipulation operations used
in the Fenwick Tree: What are the values of 90 - LSOne(90) and 90 + LSOne(90)?
Exercise 2.4.4.2: What if the problem that you want to solve includes an element at integer
key 0? Recall that the standard integer key range in our library code is is [1..n] and that
this implementation cannot use index 0 since it is used as the terminating condition of rsq.
Exercise 2.4.4.3: What if the problem that you want to solve uses non-integer keys? For
example, what if the test scores shown in Table 2.1 above are f = {5.5, 7.5, 8.0, 10.0}
(i.e. allowing either a 0 or a 5 after the decimal place)? What if the test scores are f =
{5.53, 7.57, 8.10, 9.91} (i.e. allowing for two digits after the decimal point)?
Exercise 2.4.4.4: The Fenwick Tree supports an additional operation that we have decided
to leave as an exercise to the reader: Find the smallest index with a given cumulative
frequency. For example, we may need to determine the minimum index/score i in Table 2.1
such that there are at least 7 students covered in the range [1..i] (index/score 6 in this
case). Implement this feature.
Exercise 2.4.4.5*: Solve this dynamic RSQ problem: UVa 12086 - Potentiometers using
both a Segment Tree and Fenwick Tree. Which solution is easier to produce in this case?
Also see Table 2.2 for a comparison between these two data structures.
Exercise 2.4.4.6*: Extend the 1D Fenwick Tree to 2D!
Exercise 2.4.4.7*: Fenwick Trees are normally used for point update and range (sum)
query. Show how to use a Fenwick Tree for range update and point queries. For example,
given lots of intervals with small ranges (from 1 to at most 1 million) determine the number
of intervals encompassing index i.
62
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
Programming exercises that use the data structures discussed and implemented:
• Graph Data Structures Problems
1. UVa 00599 - The Forrest for the Trees * (v−e = number of connected
components, keep a bitset of size 26 to count the number of vertices that
have some edge. Note: Also solvable with Union-Find)
2. UVa 10895 - Matrix Transpose * (transpose adjacency list)
3. UVa 10928 - My Dear Neighbours (counting out degrees)
4. UVa 11550 - Demanding Dilemma (graph representation, incidence matrix)
5. UVa 11991 - Easy Problem from ... * (use the idea of an Adj List)
Also see: More graph problems in Chapter 4
• Union-Find Disjoint Sets
1. UVa 00793 - Network Connections * (trivial; application of disjoint sets)
2. UVa 01197 - The Suspects (LA 2817, Kaohsiung03, Connected Components)
3. UVa 10158 - War (advanced usage of disjoint sets with a nice twist; memorize
list of enemies)
4. UVa 10227 - Forests (merge two disjoint sets if they are consistent)
5. UVa 10507 - Waking up brain * (disjoint sets simplifies this problem)
6. UVa 10583 - Ubiquitous Religions (count disjoint sets after all unions)
7. UVa 10608 - Friends (find the set with the largest element)
8. UVa 10685 - Nature (find the set with the largest element)
9. UVa 11503 - Virtual Friends * (maintain set attribute (size) in rep item)
10. UVa 11690 - Money Matters (check if total money from each member is 0)
• Tree-related Data Structures
1. UVa 00297 - Quadtrees (simple quadtree problem)
2. UVa 01232 - SKYLINE (LA 4108, Singapore07, a simple problem if input
size is small; but since n ≤ 100000, we have to use a Segment Tree; note that
this problem is not about RSQ/RMQ)
3. UVa 11235 - Frequent Values * (range maximum query)
4. UVa 11297 - Census (Quad Tree with updates or use 2D segment tree)
5. UVa 11350 - Stern-Brocot Tree (simple tree data structure question)
6. UVa 11402 - Ahoy, Pirates * (segment tree with lazy updates)
7. UVa 12086 - Potentiometers (LA 2191, Dhaka06; pure dynamic range sum
query problem; solvable with Fenwick Tree or Segment Tree)
8. UVa 12532 - Interval Product * (clever usage of Fenwick/Segment Tree)
Also see: DS as part of the solution of harder problems in Chapter 8
63
2.5. SOLUTION TO NON-STARRED EXERCISES
c Steven & Felix
1. S & (N − 1)
2. (S & (S − 1)) == 0
3. S & (S − 1)
4. S (S + 1)
5. S & (S + 1)
6. S (S − 1)
Exercise 2.3.1: Since the collection is dynamic, we will encounter frequent insertion and
deletion queries. An insertion can potentially change the sort order. If we store the informa-
tion in a static array, we will have to use one O(n) iteration of an insertion sort after each
insertion and deletion (to close the gap in the array). This is inefficient!
Exercise 2.3.2:
3. To find the min/max element, we can start from root and keep going left/right until we
encounter a vertex with no left/right subtrees respectively. That vertex is the answer.
4. We will obtain the sorted output: 4, 5, 6, 7, 15, 23, 50, 71. See Section 4.7.2 if you are
not familiar with the inorder tree traversal algorithm.
5. successor(23): Find the minimum element of the subtree rooted at the right of 23,
which is the subtree rooted at 71. The answer is 50.
successor(7): 7 has no right subtree, so 7 must be the maximum of a certain subtree.
That subtree is the subtree rooted at 6. The parent of 6 is 15 and 6 is the left subtree
of 15. By the BST property, 15 must be the successor of 7.
successor(71): 71 is the largest element and has no successor.
Note: The algorithm to find the predecessor of a node is similar.
64
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
Exercise 2.3.3*: For Sub-task 1, we run inorder traversal in O(n) and see if the values are
sorted. Solutions to other sub-tasks are not shown.
Exercise 2.3.6: The answers:
1. Insert(26): Insert 26 as the left subtree of 3, swap 26 with 3, then swap 26 with 19
and stop. The Max Heap array A now contains {-, 90, 26, 36, 17, 19, 25, 1, 2, 7, 3}.
Exercise 2.3.7: Yes, check that all indices (vertices) satisfy the Max Heap property.
Exercise 2.3.16: Use the C++ STL set (or Java TreeSet) as it is a balanced BST that
supports O(log n) dynamic insertions and deletions. We can use the inorder traversal to
print the data in the BST in sorted order (simply use C++ iterators or Java Iterators).
Exercise 2.3.17: Use the C++ STL map (Java TreeMap) and a counter variable. A hash
table is also a possible solution but not necessary for programming contests. This trick is
quite frequently used in various (contest) problems. Example usage:
char str[1000];
map<string, int> mapper;
int i, idx;
for (i = idx = 0; i < M; i++) { // idx starts from 0
scanf("%s", &str);
if (mapper.find(str) == mapper.end()) // if this is the first encounter
// alternatively, we can also test if mapper.count(str) is greater than 0
mapper[str] = idx++; // give str the current idx and increase idx
}
65
2.5. SOLUTION TO NON-STARRED EXERCISES
c Steven & Felix
For int sizeOfSet(int i), we use another vi setSize(N) initialized to all ones (each
set has only one element). During unionSet(i, j), update the setSize array by performing
setSize[find(j)] += setSize[find(i)] (or the other way around depending on rank) if
isSameSet(i, j) returns false. Now int sizeOfSet(int i) can simply return the value
of setSize[find(i)];
These two variants have been implemented in ch2 08 unionfind ds.cpp/java.
Exercise 2.4.3.3: RSQ(1, 7) = 167 and RSQ(3, 8) = 139; No, using a Segment Tree is
overkill. There is a simple DP solution that uses an O(n) pre-processing step and takes O(1)
time per RSQ (see Section 9.33).
Exercise 2.4.4.1: 90 - LSOne(90) = (1011010)2 - (10)2 = (1011000)2 = 88 and
90 + LSOne(90) = (1011010)2 + (10)2 = (1011100)2 = 92.
Exercise 2.4.4.2: Simple: shift all indices by one. Index iin the 1-based Fenwick Tree now
refers to index i − 1 in the actual problem.
Exercise 2.4.4.3: Simple: convert the floating point numbers into integers. For the first
task, we can multiply every number by two. For the second case, we can multiply all numbers
by one hundred.
Exercise 2.4.4.4: The cumulative frequency is sorted, thus we can use a binary search.
Study the ‘binary search for the answer’ technique discussed in Section 3.3. The resulting
time complexity is O(log2 n).
66
CHAPTER 2. DATA STRUCTURES AND LIBRARIES
c Steven & Felix
The breakdown of the number of programming exercises from each section is shown below:
67
2.6. CHAPTER NOTES
c Steven & Felix
68
Chapter 3
69
3.2. COMPLETE SEARCH
c Steven & Felix
Here is some advice for this chapter: Please do not just memorize the solutions for each
problem discussed, but instead remember and internalize the thought process and problem
solving strategies used. Good problem solving skills are more important than memorized
solutions for well-known Computer Science problems when dealing with (often creative and
novel) contest problems.
70
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
71
3.2. COMPLETE SEARCH
c Steven & Felix
Notice the way a short circuit AND was used to speed up the solution by enforcing a
lightweight check on whether x, y, and z are all different before we check the three formulas.
The code shown above already passes the required time limit for this problem, but we can
do better. We can also use the second
√ equation x × y × z = B and assume that x = y = z
3
to obtain x × x × x < B or x < B. The new range of x is [−22 . . . 22]. We can also prune
the search space by using if statements to execute only some of the (inner) loops, or use
break and/or continue statements to stop/skip loops. The code shown below is now much
faster than the code shown above (there are a few other optimizations required to solve the
extreme version of this problem: UVa 11571 - Simple Equations - Extreme!!):
72
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
n is 8 and maximum m is 20, the largest test case will still only require 20 × 8! = 806400
operations—a perfectly viable solution.
If you have never written an algorithm to generate all permutations of a set of numbers
(see Exercise 1.2.3, task 7), you may still be unsure about how to proceed. The simple
C++ solution is shown below.
#include <algorithm> // next_permutation is inside this C++ STL
// the main routine
int i, n = 8, p[8] = {0, 1, 2, 3, 4, 5, 6, 7}; // the first permutation
do { // try all possible O(n!) permutations, the largest input 8! = 40320
... // check the given social constraint based on ‘p’ in O(m)
} // the overall time complexity is thus O(m * n!)
while (next_permutation(p, p + n)); // this is inside C++ STL <algorithm>
Exercise 3.2.1.1: For the solution of UVa 725, why is it better to iterate through fghij
and not through abcde?
Exercise 3.2.1.2: Does a 10! algorithm that permutes abcdefghij work for UVa 725?
Exercise 3.2.1.3*: Java does not have a built-in next permutation function yet. If you
are a Java user, write your own recursive backtracking routine to generate all permutations!
This is similar to the recursive backtracking for the 8-Queens problem.
Exercise 3.2.1.4*: How would you solve UVa 12455 if 1 ≤ n ≤ 30 and each integer can be
as big as 1000000000? Hint: See Section 8.2.4.
1
This is also known as the ‘Subset Sum’ problem, see Section 3.5.3.
73
3.2. COMPLETE SEARCH
c Steven & Felix
74
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
void backtrack(int c) {
if (c == 8 && row[b] == a) { // candidate sol, (a, b) has 1 queen
printf("%2d %d", ++lineCounter, row[0] + 1);
for (int j = 1; j < 8; j++) printf(" %d", row[j] + 1);
printf("\n"); }
for (int r = 0; r < 8; r++) // try all possible row
if (place(r, c)) { // if can place a queen at this col and row
row[c] = r; backtrack(c + 1); // put this queen here and recurse
} }
int main() {
scanf("%d", &TC);
while (TC--) {
scanf("%d %d", &a, &b); a--; b--; // switch to 0-based indexing
memset(row, 0, sizeof row); lineCounter = 0;
printf("SOLN COLUMN\n");
printf(" # 1 2 3 4 5 6 7 8\n\n");
backtrack(0); // generate all possible 8! candidate solutions
if (TC) printf("\n");
} } // return 0;
bitset<30> rw, ld, rd; // for the largest n = 14, we have 27 diagonals
Initially all n rows (rw), 2 × n − 1 left diagonals (ld), and 2 × n − 1 right diagonals (rd) are
unused (these three bitsets are all set to false). When a queen is placed at cell (r, c),
we flag rw[r] = true to disallow this row from being used again. Furthermore, all (a, b)
where abs(r - a) = abs(c - b) also cannot be used anymore. There are two possibilities
after removing the abs function: r - c = a - b and r + c = a + b. Note that r + c and
r - c represent indices for the two diagonal axes. As r - c can be negative, we add an
offset of n - 1 to both sides of the equation so that r - c + n - 1 = a - b + n - 1. If a
queen is placed on cell (r, c), we flag ld[r - c + n - 1] = true and rd[r + c] = true
to disallow these two diagonals from being used again. With these additional data structures
and the additional problem-specific constraint in UVa 11195 (board[r][c] cannot be a bad
cell), we can extend our code to become:
75
3.2. COMPLETE SEARCH
c Steven & Felix
void backtrack(int c) {
if (c == n) { ans++; return; } // a solution
for (int r = 0; r < n; r++) // try all possible row
if (board[r][c] != ’*’ && !rw[r] && !ld[r - c + n - 1] && !rd[r + c]) {
rw[r] = ld[r - c + n - 1] = rd[r + c] = true; // flag off
backtrack(c + 1);
rw[r] = ld[r - c + n - 1] = rd[r + c] = false; // restore
} }
Visualization: www.comp.nus.edu.sg/∼stevenha/visualization/recursion.html
Exercise 3.2.2.1: The code shown for UVa 750 can be further optimized by pruning the
search when ‘row[b] != a’ earlier during the recursion (not only when c == 8). Modify it!
Exercise 3.2.2.2*: Unfortunately, the updated solution presented using bitsets: rw, ld,
and rd will still obtain a TLE for UVa 11195 - Another n-Queen Problem. We need to
further speed up the solution using bitmask techniques and another way of using the left
and right diagonal constraints. This solution will be discussed in Section 8.2.1. For now,
use the (non Accepted) idea presented here for UVa 11195 to speed up the code for UVa 750
and two more similar problems: UVa 167 and 11085!
3.2.3 Tips
The biggest gamble in writing a Complete Search solution is whether it will or will not be
able to pass the time limit. If the time limit is 10 seconds (online judges do not usually
use large time limits for efficient judging) and your program currently runs in ≈ 10 seconds
on several (can be more than one) test cases with the largest input size as specified in the
problem description, yet your code is still judged to be TLE, you may want to tweak the
‘critical code’2 in your program instead of re-solving the problem with a faster algorithm
which may not be easy to design.
Here are some tips that you may want to consider when designing your Complete Search
solution for a certain problem to give it a higher chance of passing the Time Limit. Writing
a good Complete Search solution is an art in itself.
76
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
77
3.2. COMPLETE SEARCH
c Steven & Felix
a square box (x-d, y-d) to (x+d, y+d) is maximized. The value d is the power of the
gas-bomb (d ≤ 50), see Figure 3.2.
An immediate solution is to attack this problem in the most obvious fashion possible:
bomb each of the 10242 cells and select the most effective location. For each bombed cell
(x, y), we can perform an O(d2) scan to count the number of rats killed within the square-
bombing radius. For the worst case, when the array has size 10242 and d = 50, this takes
10242 × 502 = 2621M operations. TLE3 !
Another option is to attack this problem backwards: Create
an array int killed[1024][1024]. For each rat population
at coordinate (x, y), add it to killed[i][j], where |i − x| ≤
d and |j − y| ≤ d. This is because if a bomb was placed at
(i, j), the rats at coordinate (x, y) will be killed. This
pre-processing takes O(n × d2 ) operations. Then, to determine
the most optimal bombing position, we can simply find the
coordinate of the highest entry in array killed, which can be
done in 10242 operations. This approach only requires 20000 ×
502 + 10242 = 51M operations for the worst test case (n =
20000, d = 50), ≈ 51 times faster than the frontal attack! This Figure 3.2: UVa 10360 [47]
is an AC solution.
1. A biased opinion: Use C++ instead of Java. An algorithm implemented using C++
usually runs faster than the one implemented in Java in many online judges, including
UVa [47]. Some programming contests give Java users extra time to account for the
difference in performance.
2. For C/C++ users, use the faster C-style scanf/printf rather than cin/cout. For
Java users, use the faster BufferedReader/BufferedWriter classes as follows:
3. Use the expected O(n log n) but cache-friendly quicksort in C++ STL algorithm::sort
(part of ‘introsort’) rather than the true O(n log n) but non cache-friendly heapsort (its
root-to-leaf/leaf-to-root operations span a wide range of indices—lots of cache misses).
4. Access a 2D array in a row major fashion (row by row) rather than in a column major
fashion—multidimensional arrays are stored in a row-major order in memory.
3
Although 2013 CPU can compute ≈ 100M operations in a few seconds, 2621M operations will still take
too long in a contest environment.
78
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
5. Bit manipulation on the built-in integer data types (up to the 64-bit integer) is more
efficient than index manipulation in an array of booleans (see bitmask in Section 2.2).
If we need more than 64 bits, use the C++ STL bitset rather than vector<bool>
(e.g. for Sieve of Eratosthenes in Section 5.5.1).
6. Use lower level data structures/types at all times if you do not need the extra func-
tionality in the higher level (or larger) ones. For example, use an array with a slightly
larger size than the maximum size of input instead of using resizable vectors. Also,
use 32-bit ints instead of 64-bit long longs as the 32-bit int is faster in most 32-bit
online judge systems.
7. For Java, use the faster ArrayList (and StringBuilder) rather than Vector (and
StringBuffer). Java Vectors and StringBuffers are thread safe but this feature
is not needed in competitive programming. Note: In this book, we will stick with
Vectors to avoid confusing bilingual C++ and Java readers who use both the C++
STL vector and Java Vector.
8. Declare most data structures (especially the bulky ones, e.g. large arrays) once by
placing them in global scope. Allocate enough memory to deal with the largest input
of the problem. This way, we do not have to pass the data structures around as function
arguments. For problems with multiple test cases, simply clear/reset the contents of
the data structure before dealing with each test case.
9. When you have the option to write your code either iteratively or recursively, choose the
iterative version. Example: The iterative C++ STL next permutation and iterative
subset generation techniques using bitmask shown in Section 3.2.1 are (far) faster than
if you write similar routines recursively (mainly due to overheads in function calls).
10. Array access in (nested) loops can be slow. If you have an array A and you frequently
access the value of A[i] (without changing it) in (nested) loops, it may be beneficial
to use a local variable temp = A[i] and works with temp instead.
11. In C/C++, appropriate usage of macros or inline functions can reduce runtime.
12. For C++ users: Using C-style character arrays will yield faster execution than when
using the C++ STL string. For Java users: Be careful with String manipulation as
Java String objects are immutable. Operations on Java Strings can thus be very
slow. Use Java StringBuilder instead.
Browse the Internet or relevant books (e.g. [69]) to find (much) more information on how to
speed up your code. Practice this ‘code hacking skill’ by choosing a harder problem in UVa
online judge where the runtime of the best solution is not 0.000s. Submit several variants of
your Accepted solution and check the runtime differences. Adopt hacking modification that
consistently gives you faster runtime.
79
3.2. COMPLETE SEARCH
c Steven & Felix
80
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
9. UVa 10730 - Antiarithmetic? (2 nested loops with pruning can pass possibly
pass the weaker test cases; note that this brute force solution is too slow for
the larger test data generated in the solution of UVa 11129)
10. UVa 11242 - Tour de France * (plus sorting)
11. UVa 12488 - Start Grid (2 nested loops; simulate overtaking process)
12. UVa 12583 - Memory Overflow (2 nested loops; be careful of overcounting)
• Iterative (Three Or More Nested Loops, Easier)
1. UVa 00154 - Recycling (3 nested loops)
2. UVa 00188 - Perfect Hash (3 nested loops, until the answer is found)
3. UVa 00441 - Lotto * (6 nested loops)
4. UVa 00626 - Ecosystem (3 nested loops)
5. UVa 00703 - Triple Ties: The ... (3 nested loops)
6. UVa 00735 - Dart-a-Mania * (3 nested loops, then count)
7. UVa 10102 - The Path in the ... * (4 nested loops will do, we do not
need BFS; get max of minimum Manhattan distance from a ‘1’ to a ‘3’.)
8. UVa 10502 - Counting Rectangles (6 nested loops, rectangle, not too hard)
9. UVa 10662 - The Wedding (3 nested loops)
10. UVa 10908 - Largest Square (4 nested loops, square, not too hard)
11. UVa 11059 - Maximum Product (3 nested loops, input is small)
12. UVa 11975 - Tele-loto (3 nested loops, simulate the game as asked)
13. UVa 12498 - Ant’s Shopping Mall (3 nested loops)
14. UVa 12515 - Movie Police (3 nested loops)
• Iterative (Three-or-More Nested Loops, Harder)
1. UVa 00253 - Cube painting (try all, similar problem in UVa 11959)
2. UVa 00296 - Safebreaker (try all 10000 possible codes, 4 nested loops, use
similar solution as ‘Master-Mind’ game)
3. UVa 00386 - Perfect Cubes (4 nested loops with pruning)
4. UVa 10125 - Sumsets (sort; 4 nested loops; plus binary search)
5. UVa 10177 - (2/3/4)-D Sqr/Rects/... (2/3/4 nested loops, precalculate)
6. UVa 10360 - Rat Attack (also solvable using 10242 DP max sum)
7. UVa 10365 - Blocks (use 3 nested loops with pruning)
8. UVa 10483 - The Sum Equals ... (2 nested loops for a, b, derive c from a, b;
there are 354 answers for range [0.01 .. 255.99]; similar with UVa 11236)
9. UVa 10660 - Citizen attention ... * (7 nested loops, Manhattan distance)
10. UVa 10973 - Triangle Counting (3 nested loops with pruning)
11. UVa 11108 - Tautology (5 nested loops, try all 25 = 32 values with pruning)
12. UVa 11236 - Grocery Store * (3 nested loops for a, b, c; derive d from
a, b, c; check if you have 949 lines of output)
13. UVa 11342 - Three-square (pre-calculate squared values from 02 to 2242 , use
3 nested loops to generate the answers; use map to avoid duplicates)
14. UVa 11548 - Blackboard Bonanza (4 nested loops, string, pruning)
15. UVa 11565 - Simple Equations * (3 nested loops with pruning)
16. UVa 11804 - Argentina (5 nested loops)
17. UVa 11959 - Dice (try all possible dice positions, compare with the 2nd one)
Also see Mathematical Simulation in Section 5.2
81
3.2. COMPLETE SEARCH
c Steven & Felix
82
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
6. UVa 00571 - Jugs (solution can be suboptimal, add flag to avoid cycling)
7. UVa 00574 - Sum It Up * (print all solutions with backtracking)
8. UVa 00598 - Bundling Newspaper (print all solutions with backtracking)
9. UVa 00775 - Hamiltonian Cycle (backtracking suffices because the search
space cannot be that big; in a dense graph, it is more likely to have a Hamil-
tonian cycle, so we can prune early; we do NOT have to find the best one
like in TSP problem)
10. UVa 10001 - Garden of Eden (the upperbound of 232 is scary but with
efficient pruning, we can pass the time limit as the test case is not extreme)
11. UVa 10063 - Knuth’s Permutation (do as asked)
12. UVa 10460 - Find the Permuted String (similar nature with UVa 10063)
13. UVa 10475 - Help the Leaders (generate and prune; try all)
14. UVa 10503 - The dominoes solitaire * (max 13 spaces only)
15. UVa 10506 - Ouroboros (any valid solution is AC; generate all possible next
digit (up to base 10/digit [0..9]); check if it is still a valid Ouroboros sequence)
16. UVa 10950 - Bad Code (sort the input; run backtracking; the output should
be sorted; only display the first 100 sorted output)
17. UVa 11201 - The Problem with the ... (backtracking involving strings)
18. UVa 11961 - DNA (there are at most 410 possible DNA strings; moreover,
the mutation power is at most K ≤ 5 so the search space is much smaller;
sort the output and then remove duplicates)
• Recursive Backtracking (Harder)
1. UVa 00129 - Krypton Factor (backtracking, string processing check, a bit of
output formatting)
2. UVa 00165 - Stamps (requires some DP too; can be pre-calculated)
3. UVa 00193 - Graph Coloring * (Max Independent Set, input is small)
4. UVa 00208 - Firetruck (backtracking with some pruning)
5. UVa 00416 - LED Test * (backtrack, try all)
6. UVa 00433 - Bank (Not Quite O.C.R.) (similar to UVa 416)
7. UVa 00565 - Pizza Anyone? (backtracking with lots of pruning)
8. UVa 00861 - Little Bishops (backtracking with pruning as in 8-queens recur-
sive backtracking solution; then pre-calculate the results)
9. UVa 00868 - Numerical maze (try row 1 to N; 4 ways; some constraints)
10. UVa 01262 - Password * (LA 4845, Daejeon10, sort the columns in the
two 6×5 grids first so that we can process common passwords in lexicographic
order; backtracking; important: skip two similar passwords)
11. UVa 10094 - Place the Guards (this problem is like the n-queens chess prob-
lem, but must find/use the pattern!)
12. UVa 10128 - Queue (backtracking with pruning; try up to all N! (13!) per-
mutations that satisfy the requirement; then pre-calculate the results)
13. UVa 10582 - ASCII Labyrinth (simplify complex input first; then backtrack)
14. UVa 11090 - Going in Cycle (minimum mean weight cycle problem; solvable
with backtracking with important pruning when current running mean is
greater than the best found mean weight cycle cost)
83
3.3. DIVIDE AND CONQUER
c Steven & Felix
We have seen examples of the D&C paradigm in the previous sections of this book: Various
sorting algorithms (e.g. Quick Sort, Merge Sort, Heap Sort) and Binary Search in Section
2.2 utilize this paradigm. The way data is organized in Binary Search Tree, Heap, Segment
Tree, and Fenwick Tree in Section 2.3, 2.4.3, and 2.4.4 also relies upon the D&C paradigm.
84
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
itself, we have found the solution. As there are Q queries, this approach runs in O(QN) (the
input tree can be a sorted linked list, or rope, of length N) and will get a TLE as N ≤ 80K
and Q ≤ 20K.
A better solution is to store all the 20K queries (we do not have to answer them im-
mediately). Traverse the tree just once starting from the root using the O(N) preorder
tree traversal algorithm (Section 4.7.2). This preorder tree traversal is slightly modified to
remember the partial root-to-current-vertex sequence as it executes. The array is always
sorted because the vertices along the root-to-current-vertex path have increasing weights,
see Figure 3.3 (right). The preorder tree traversal on the tree shown in Figure 3.3 (left)
produces the following partial root-to-current-vertex sorted array: {{3}, {3, 5}, {3, 5, 7},
{3, 5, 7, 8}, backtrack, {3, 5, 7, 9}, backtrack, backtrack, backtrack, {3, 8}, backtrack,
{3, 6}, {3, 6, 20}, backtrack, {3, 6, 10}, and finally {3, 6, 10, 20}, backtrack, backtrack,
backtrack (done)}.
During the preorder traversal, when we land on a queried vertex, we can perform a
O(log N) binary search (to be precise: lower bound) on the partial root-to-current-vertex
weight array to obtain the ancestor closest to the root with a value of at least P , recording
these solutions. Finally, we can perform a simple O(Q) iteration to output the results. The
overall time complexity of this approach is O(Q log N), which is now manageable given the
input bounds.
Bisection Method
We have discussed the applications of Binary Searches in finding items in static sorted
sequences. However, the binary search principle4 can also be used to find the root of a
function that may be difficult to compute directly.
Example: You buy a car with loan and now want to pay the loan in monthly installments
of d dollars for m months. Suppose the value of the car is originally v dollars and the bank
charges an interest rate of i% for any unpaid loan at the end of each month. What is the
amount of money d that you must pay per month (to 2 digits after the decimal point)?
Suppose d = 576.19, m = 2, v = 1000, and i = 10%. After one month, your debt
becomes 1000 × (1.1) − 576.19 = 523.81. After two months, your debt becomes 523.81 ×
(1.1) − 576.19 ≈ 0. If we are only given m = 2, v = 1000, and i = 10%, how would we
determine that d = 576.19? In other words, find the root d such that the debt payment
function f (d, m, v, i) ≈ 0.
An easy way to solve this root finding problem is to use the bisection method. We pick
a reasonable range as a starting point. We want to fix d within the range [a..b] where
4
We use the term ‘binary search principle’ to refer to the D&C approach of halving the range of possible
answers. The ‘binary search algorithm’ (finding index of an item in a sorted array), the ‘bisection method’
(finding the root of a function), and ‘binary search the answer’ (discussed in the next subsection) are all
instances of this principle.
85
3.3. DIVIDE AND CONQUER
c Steven & Felix
a = 0.01 as we have to pay at least one cent and b = (1 + i%) × v as the earliest we can
complete the payment is m = 1 if we pay exactly (1 + i%) × v dollars after one month. In
this example, b = (1 + 0.1) × 1000 = 1100.00 dollars. For the bisection method to work5 ,
we must ensure that the function values of the two extreme points in the initial Real range
[a..b], i.e. f (a) and f (b) have opposite signs (this is true for the computed a and b above).
a b d = a+b
2
status: f (d, m, v, i) action
0.01 1100.00 550.005 undershoot by 54.9895 increase d
550.005 1100.00 825.0025 overshoot by 522.50525 decrease d
550.005 825.0025 687.50375 overshoot by 233.757875 decrease d
550.005 687.50375 618.754375 overshoot by 89.384187 decrease d
550.005 618.754375 584.379688 overshoot by 17.197344 decrease d
550.005 584.379688 567.192344 undershoot by 18.896078 increase d
567.192344 584.379688 575.786016 undershoot by 0.849366 increase d
... ... ... a few iterations later . . . ...
... ... 576.190476 stop; error is now less than answer = 576.19
Notice that bisection method only requires O(log2 ((b − a)/)) iterations to get an answer
that is good enough (the error is smaller than the threshold error that we can tolerate).
In this example, bisection method only takes log2 1099.99/ tries. Using a small = 1e-9,
this yields only ≈ 40 iterations. Even if we use a smaller = 1e-15, we will still only need
≈ 60 tries. Notice that the number of tries is small. The bisection method is much more
efficient compared to exhaustively evaluating each possible value of d =[0.01..1100.00]/
for this example function. Note: The bisection method can be written with a loop that tries
the values of d ≈ 40 to 60 times (see our implementation in the ‘binary search the answer’
discussion below).
86
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
will not bring your jeep safely to the goal event. On the other hand, setting your jeep fuel
tank volume to any value between [X..10000.000] will bring your jeep safely to the goal
event, usually with some fuel left. This property allows us to binary search the answer X!
We can use the following code to obtain the solution for this problem.
#define EPS 1e-9 // this value is adjustable; 1e-9 is usually small enough
bool can(double f) { // details of this simulation is omitted
// return true if the jeep can reach goal state with fuel tank capacity f
// return false otherwise
}
Note that some programmers choose to use a constant number of refinement iterations
instead of allowing the number of iterations to vary dynamically to avoid precision errors
when testing fabs(hi - lo) > EPS and thus being trapped in an infinite loop. The only
changes required to implement this approach are shown below. The other parts of the code
are the same as above.
Exercise 3.3.1.1: There is an alternative solution for UVa 11935 that does not use ‘binary
search the answer’ technique. Can you spot it?
Exercise 3.3.1.2*: The example shown here involves binary-searching the answer where
the answer is a floating point number. Modify the code to solve ‘binary search the answer’
problems where the answer lies in an integer range!
87
3.3. DIVIDE AND CONQUER
c Steven & Felix
programming contests is the Binary Search principle. If you want to do well in programming
contests, please spend time practicing the various ways to apply it.
Once you are more familiar with the ‘Binary Search the Answer’ technique discussed in
this section, please explore Section 8.4.1 for a few more programming exercises that use this
technique with other algorithm that we will discuss in the latter parts of this book.
We notice that there are not that many D&C problems outside of our binary search
categorization. Most D&C solutions are ‘geometry-related’ or ‘problem specific’, and thus
cannot be discussed in detail in this book. However, we will encounter some of them in
Section 8.4.1 (binary search the answer plus geometry formulas), Section 9.14 (Inversion
Index), Section 9.21 (Matrix Power), and Section 9.29 (Selection Problem).
88
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
3.4 Greedy
An algorithm is said to be greedy if it makes the locally optimal choice at each step with the
hope of eventually reaching the globally optimal solution. In some cases, greedy works—the
solution is short and runs efficiently. For many others, however, it does not. As discussed
in other typical Computer Science textbooks, e.g. [7, 38], a problem must exhibit these two
properties in order for a greedy algorithm to work:
1. It has optimal sub-structures.
Optimal solution to the problem contains optimal solutions to the sub-problems.
2. It has the greedy property (difficult to prove in time-critical contest environment!).
If we make a choice that seems like the best at the moment and proceed to solve the
remaining subproblem, we reach the optimal solution. We will never have to reconsider
our previous choices.
3.4.1 Examples
Coin Change - The Greedy Version
Problem description: Given a target amount V cents and a list of denominations of n coins,
i.e. we have coinValue[i] (in cents) for coin types i ∈ [0..n-1], what is the minimum
number of coins that we must use to represent amount V ? Assume that we have an unlimited
supply of coins of any type. Example: If n = 4, coinValue = {25, 10, 5, 1} cents6 , and
we want to represent V = 42 cents, we can use this Greedy algorithm: Select the largest
coin denomination which is not greater than the remaining amount, i.e. 42-25 = 17 → 17-10
= 7 → 7-5 = 2 → 2-1 = 1 → 1-1 = 0, a total of 5 coins. This is optimal.
The problem above has the two ingredients required for a successful greedy algorithm:
1. It has optimal sub-structures.
We have seen that in our quest to represent 42 cents, we used 25+10+5+1+1.
This is an optimal 5-coin solution to the original problem!
Optimal solutions to sub-problem are contained within the 5-coin solution, i.e.
a. To represent 17 cents, we can use 10+5+1+1 (part of the solution for 42 cents),
b. To represent 7 cents, we can use 5+1+1 (also part of the solution for 42 cents), etc
2. It has the greedy property: Given every amount V , we can greedily subtract from it
the largest coin denomination which is not greater than this amount V . It can be
proven (not shown here for brevity) that using any other strategies will not lead to an
optimal solution, at least for this set of coin denominations.
However, this greedy algorithm does not work for all sets of coin denominations. Take for
example {4, 3, 1} cents. To make 6 cents with that set, a greedy algorithm would choose 3
coins {4, 1, 1} instead of the optimal solution that uses 2 coins {3, 3}. The general version
of this problem is revisited later in Section 3.5.2 (Dynamic Programming).
89
3.4. GREEDY
c Steven & Felix
S
A=( j=1 Mj )/C, i.e. A is the average of the total mass in each of the C chambers.
C
Imbalance = i=1 |Xi − A|, i.e. the sum of differences between the total mass in each
chamber w.r.t. A where Xi is the total mass of specimens in chamber i.
90
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
Problem description: n sprinklers are installed in a horizontal strip of grass L meters long
and W meters wide. Each sprinkler is centered vertically in the strip. For each sprinkler,
we are given its position as the distance from the left end of the center line and its radius of
operation. What is the minimum number of sprinklers that should be turned on in order to
water the entire strip of grass? Constraint: n ≤ 10000. For an illustration of the problem,
see Figure 3.7—left side. The answer for this test case is 6 sprinklers (those labeled with
{A, B, D, E, F, H}). There are 2 unused sprinklers: {C, G}.
We cannot solve this problem with a brute force strategy that tries all possible subsets of
sprinklers to be turned on since the number of sprinklers can go up to 10000. It is definitely
infeasible to try all 210000 possible subsets of sprinklers.
This problem is actually a variant of the well known greedy problem called the interval
covering problem. However, it includes a simple geometric twist. The original interval
covering problem deals with intervals. This problem deals with sprinklers that have circles
of influence in a horizontal area rather than simple intervals. We first have to transform the
problem to resemble the standard interval covering problem.
See Figure 3.7—right side. We can convert these circles and horizontal strips into inter-
vals. We can compute dx = sqrt(R2 - (W/2)2). Suppose a circle is centered at (x, y).
The interval represented by this circle is [x-dx..x+dx]. To see why this works, notice that
the additional circle segment beyond dx away from x does not completely cover the strip in
the horizontal region it spans. If you have difficulties with this geometric transformation,
see Section 7.2.4 which discusses basic operations involving a right triangle.
91
3.4. GREEDY
c Steven & Felix
Now that we have transformed the original problem into the interval covering problem, we
can use the following Greedy algorithm. First, the Greedy algorithm sorts the intervals by
increasing left endpoint and by decreasing right endpoint if ties arise. Then, the Greedy
algorithm processes the intervals one at a time. It takes the interval that covers ‘as far
right as possible’ and yet still produces uninterrupted coverage from the leftmost side to the
rightmost side of the horizontal strip of grass. It ignores intervals that are already completely
covered by other (previous) intervals.
For the test case shown in Figure 3.7—left side, this Greedy algorithm first sorts the
intervals to obtain the sequence {A, B, C, D, E, F, G, H}. Then it processes them one by
one. First, it takes ‘A’ (it has to), takes ‘B’ (connected to interval ‘A’), ignores ‘C’ (as it is
embedded inside interval ‘B’), takes ‘D’ (it has to, as intervals ‘B’ and ‘E’ are not connected
if ‘D’ is not used), takes ‘E’, takes ‘F’, ignores ‘G’ (as taking ‘G’ is not ‘as far right as
possible’ and does not reach the rightmost side of the grass strip), takes ‘H’ (as it connects
with interval ‘F’ and covers more to the right than interval of ‘G’ does, going beyond the
rightmost end of the grass strip). In total, we select 6 sprinklers: {A, B, D, E, F, H}. This
is the minimum possible number of sprinklers for this test case.
Exercise 3.4.1.1*: Which of the following sets of coins (all in cents) are solvable using the
greedy ‘coin change’ algorithm discussed in this section? If the greedy algorithm fails on a
certain set of coin denominations, determine the smallest counter example V cents on which
it fails to be optimal. See [51] for more details about finding such counter examples.
92
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
1. S1 = {10, 7, 5, 4, 1}
2. S2 = {64, 32, 16, 8, 4, 2, 1}
3. S3 = {13, 11, 7, 5, 3, 2, 1}
4. S4 = {7, 6, 5, 4, 3, 2, 1}
5. S5 = {21, 17, 11, 10, 1}
93
3.4. GREEDY
c Steven & Felix
94
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
3.5.1 DP Illustration
We will illustrate the concept of Dynamic Programming with an example problem: UVa
11450 - Wedding Shopping. The abridged problem statement: Given different options for
each garment (e.g. 3 shirt models, 2 belt models, 4 shoe models, . . . ) and a certain limited
budget, our task is to buy one model of each garment. We cannot spend more money than
the given budget, but we want to spend the maximum possible amount.
The input consists of two integers 1 ≤ M ≤ 200 and 1 ≤ C ≤ 20, where M is the budget
and C is the number of garments that you have to buy, followed by some information about
the C garments. For the garment g ∈ [0..C-1], we will receive an integer 1 ≤ K ≤ 20
which indicates the number of different models there are for that garment g, followed by K
integers indicating the price of each model ∈ [1..K] of that garment g.
The output is one integer that indicates the maximum amount of money we can spend
purchasing one of each garment without exceeding the budget. If there is no solution due to
the small budget given to us, then simply print “no solution”.
Suppose we have the following test case A with M = 20, C = 3:
Price of the 3 models of garment g = 0 → 6 4 8 // the prices are not sorted in the input
Price of the 2 models of garment g = 1 → 5 10
Price of the 4 models of garment g = 2→1535
For this test case, the answer is 19, which may result from buying the underlined items
(8+10+1). This is not unique, as solutions (6+10+3) and (4+10+5) are also optimal.
However, suppose we have this test case B with M = 9 (limited budget), C = 3:
Price of the 3 models of garment g = 0→648
Price of the 2 models of garment g = 1 → 5 10
Price of the 4 models of garment g = 2→1535
95
3.5. DYNAMIC PROGRAMMING
c Steven & Felix
The answer is then “no solution” because even if we buy all the cheapest models for each
garment, the total price (4+5+1) = 10 still exceeds our given budget M = 9.
In order for us to appreciate the usefulness of Dynamic Programming in solving the
above-mentioned problem, let’s explore how far the other approaches discussed earlier will
get us in this particular problem.
96
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
This solution works correctly, but it is very slow! Let’s analyze the worst case time com-
plexity. In the largest test case, garment g = 0 has up to 20 models; garment g = 1 also
has up to 20 models and all garments including the last garment g = 19 also have up to 20
models. Therefore, this Complete Search runs in 20 × 20 × . . . × 20 operations in the worst
case, i.e. 2020 = a very large number. If we can only come up with this Complete Search
solution, we cannot solve this problem.
Let’s verify if this problem indeed has overlapping sub-problems. Suppose that there are 2
models in a certain garment g with the same price p. Then, a Complete Search will move to
the same sub-problem shop(money - p, g + 1) after picking either model! This situation
will also occur if some combination of money and chosen model’s price causes money1 - p1
= money2 - p2 at the same garment g. This will—in a Complete Search solution—cause the
same sub-problem to be computed more than once, an inefficient state of affairs!
So, how many distinct sub-problems (a.k.a. states in DP terminology) are there in this
problem? Only 201 × 20 = 4020. There are only 201 possible values for money (0 to 200
inclusive) and 20 possible values for the garment g (0 to 19 inclusive). Each sub-problem just
needs to be computed once. If we can ensure this, we can solve this problem much faster.
The implementation of this DP solution is surprisingly simple. If we already have the re-
cursive backtracking solution (see the recurrences—a.k.a. transitions in DP terminology—
shown in the Complete Search approach above), we can implement the top-down DP by
adding these two additional steps:
1. Initialize10 a DP ‘memo’ table with dummy values that are not used in the problem,
e.g. ‘-1’. The DP table should have dimensions corresponding to the problem states.
9
Optimal sub-structures are also required for Greedy algorithms to work, but this problem lacks the
‘greedy property’, making it unsolvable with the Greedy algorithm.
10
For C/C++ users, the memset function in <cstring> is a good tool to perform this step.
97
3.5. DYNAMIC PROGRAMMING
c Steven & Felix
2. At the start of the recursive function, check if this state has been computed before.
(a) If it has, simply return the value from the DP memo table, O(1).
(This the origin of the term ‘memoization’.)
(b) If it has not been computed, perform the computation as per normal (only once)
and then store the computed value in the DP memo table so that further calls to
this sub-problem (state) return immediately.
Analyzing a basic11 DP solution is easy. If it has M distinct states, then it requires O(M)
memory space. If computing one state (the complexity of the DP transition) requires O(k)
steps, then the overall time complexity is O(kM). This UVa 11450 problem has M =
201 × 20 = 4020 and k = 20 (as we have to iterate through at most 20 models for each
garment g). Thus, the time complexity is at most 4020 × 20 = 80400 operations per test
case, a very manageable calculation.
We display our code below for illustration, especially for those who have never coded a
top-down DP algorithm before. Scrutinize this code and verify that it is indeed very similar
to the recursive backtracking code that you have seen in Section 3.2.
98
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
We want to take this opportunity to illustrate another style used in implementing DP solu-
tions (only applicable for C/C++ users). Instead of frequently addressing a certain cell in
the memo table, we can use a local reference variable to store the memory address of the
required cell in the memo table as shown below. The two coding styles are not very different,
and it is up to you to decide which style you prefer.
1. Determine the required set of parameters that uniquely describe the problem (the
state). This step is similar to what we have discussed in recursive backtracking and
top-down DP earlier.
3. Now, with the base-case cells/states in the DP table already filled, determine the
cells/states that can be filled next (the transitions). Repeat this process until the DP
table is complete. For the bottom-up DP, this part is usually accomplished through
iterations, using loops (more details about this later).
For UVa 11450, we can write the bottom-up DP as follow: We describe the state of a sub-
problem with two parameters: The current garment g and the current money. This state
formulation is essentially equivalent to the state in the top-down DP above, except that we
have reversed the order to make g the first parameter (thus the values of g are the row indices
of the DP table so that we can take advantage of cache-friendly row-major traversal in a 2D
array, see the speed-up tips in Section 3.2.3). Then, we initialize a 2D table (boolean matrix)
reachable[g][money] of size 20 × 201. Initially, only cells/states reachable by buying any
of the models of the first garment g = 0 are set to true (in the first row). Let’s use test case
A above as example. In Figure 3.8, top, the only columns ‘20-6 = 14’, ‘20-4 = 16’, and ‘20-8
= 12’ in row 0 are initially set to true.
99
3.5. DYNAMIC PROGRAMMING
c Steven & Felix
Now, we loop from the second garment g = 1 (second row) to the last garment g = C-1 =
3-1 = 2 (third and last row) in row-major order (row by row). If reachable[g-1][money]
is true, then the next state reachable[g][money-p] where p is the price of a model of
current garment g is also reachable as long as the second parameter (money) is not negative.
See Figure 3.8, middle, where reachable[0][16] propagates to reachable[1][16-5] and
reachable[1][16-10] when the model with price 5 and 10 in garment g = 1 is bought,
respectively; reachable[0][12] propagates to reachable[1][12-10] when the model with
price 10 in garment g = 1 is bought, etc. We repeat this table filling process row by row
until we are done with the last row12 .
Finally, the answer can be found in the last row when g = C-1. Find the state in
that row that is both nearest to index 0 and reachable. In Figure 3.8, bottom, the cell
reachable[2][1] provides the answer. This means that we can reach state (money = 1)
by buying some combination of the various garment models. The required final answer is
actually M - money, or in this case, 20-1 = 19. The answer is “no solution” if there is no
state in the last row that is reachable (where reachable[C-1][money] is set to true). We
provide our implementation below for comparison with the top-down version.
int main() {
int g, money, k, TC, M, C;
int price[25][25]; // price[g (<= 20)][model (<= 20)]
bool reachable[25][210]; // reachable table[g (<= 20)][money (<= 200)]
scanf("%d", &TC);
while (TC--) {
scanf("%d %d", &M, &C);
for (g = 0; g < C; g++) {
scanf("%d", &price[g][0]); // we store K in price[g][0]
for (money = 1; money <= price[g][0]; money++)
scanf("%d", &price[g][money]);
}
12
Later in Section 4.7.1, we will discuss DP as a traversal of an (implicit) DAG. To avoid unnecessary
‘backtracking’ along this DAG, we have to visit the vertices in their topological order (see Section 4.2.5).
The order in which we fill the DP table is a topological ordering of the underlying implicit DAG.
100
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
There is an advantage for writing DP solutions in the bottom-up fashion. For problems
where we only need the last row of the DP table (or, more generally, the last updated slice
of all the states) to determine the solution—including this problem, we can optimize the
memory usage of our DP solution by sacrificing one dimension in our DP table. For harder
DP problems with tight memory requirements, this ‘space saving trick’ may prove to be
useful, though the overall time complexity does not change.
Let’s take a look again at Figure 3.8. We only need to store two rows, the current row
we are processing and the previous row we have processed. To compute row 1, we only need
to know the columns in row 0 that are set to true in reachable. To compute row 2, we
similarly only need to know the columns in row 1 that are set to true in reachable. In
general, to compute row g, we only need values from the previous row g − 1. So, instead
of storing a boolean matrix reachable[g][money] of size 20 × 201, we can simply store
reachable[2][money] of size 2 × 201. We can use this programming trick to reference one
row as the ‘previous’ row and another row as the ‘current’ row (e.g. prev = 0, cur = 1)
and then swap them (e.g. now prev = 1, cur = 0) as we compute the bottom-up DP row
by row. Note that for this problem, the memory savings are not significant. For harder DP
problems, for example where there might be thousands of garment models instead of 20, this
space saving trick can be important.
101
3.5. DYNAMIC PROGRAMMING
c Steven & Felix
styles can be better than the other. To help you understand which style that you should
use when presented with a DP problem, please study the trade-offs between top-down and
bottom-up DPs listed in Table 3.2.
Top-Down Bottom-Up
Pros: Pros:
1. It is a natural transformation from the 1. Faster if many sub-problems are revisited
normal Complete Search recursion as there is no overhead from recursive calls
2. Computes the sub-problems only when 2. Can save memory space with the ‘space
necessary (sometimes this is faster) saving trick’ technique
Cons: Cons:
1. Slower if many sub-problems are revis- 1. For programmers who are inclined to re-
ited due to function call overhead (this is not cursion, this style may not be intuitive
usually penalized in programming contests)
2. If there are M states, an O(M) table size 2. If there are M states, bottom-up DP
is required, which can lead to MLE for some visits and fills the value of all these M states
harder problems (except if we use the trick
in Section 8.3.4)
102
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
Exercise 3.5.1.1: To verify your understanding of UVa 11450 problem discussed in this
section, determine what is the output for test case D below?
Test case D with M = 25, C = 3:
Price of the 3 models of garment g = 0 → 6 4 8
Price of the 2 models of garment g = 1 → 10 6
Price of the 4 models of garment g = 2 → 7 3 1 5
Exercise 3.5.1.2: Is the following state formulation shop(g, model), where g represents
the current garment and model represents the current model, appropriate and exhaustive
for UVa 11450 problem?
Exercise 3.5.1.3: Add the space saving trick to the bottom-up DP code in Approach 5!
103
3.5. DYNAMIC PROGRAMMING
c Steven & Felix
There is an even better algorithm for this problem. The main part of Jay Kadane’s O(n)
(can be viewed as a greedy or DP) algorithm to solve this problem is shown below.
The key idea of Kadane’s algorithm is to keep a running sum of the integers seen so far and
greedily reset that to 0 if the running sum dips below 0. This is because re-starting from
0 is always better than continuing from a negative running sum. Kadane’s algorithm is the
required algorithm to solve this UVa 507 problem as n ≤ 20K.
Note that we can also view this Kadane’s algorithm as a DP solution. At each step,
we have two choices: We can either leverage the previously accumulated maximum sum, or
begin a new range. The DP variable dp(i) thus represents the maximum sum of a range of
integers that ends with element A[i]. Thus, the final answer is the maximum over all the
values of dp(i) where i ∈ [0..n-1]. If zero-length ranges are allowed, then 0 must also be
considered as a possible answer. The implementation above is essentially an efficient version
that utilizes the space saving trick discussed earlier.
Attacking this problem naı̈vely using a Complete Search as shown below does not work as
it runs in O(n6). For the largest test case with n = 100, an O(n6 ) algorithm is too slow.
maxSubRect = -127*100*100; // the lowest possible value for this problem
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) // start coordinate
for (int k = i; k < n; k++) for (int l = j; l < n; l++) { // end coord
subRect = 0; // sum the items in this sub-rectangle
for (int a = i; a <= k; a++) for (int b = j; b <= l; b++)
subRect += A[a][b];
maxSubRect = max(maxSubRect, subRect); } // the answer is here
104
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
The solution for the Max 1D Range Sum in the previous subsection can be extended to two
(or more) dimensions as long as the inclusion-exclusion principle is properly applied. The
only difference is that while we dealt with overlapping sub-ranges in Max 1D Range Sum,
we will deal with overlapping sub-matrices in Max 2D Range Sum. We can turn the n × n
input matrix into an n × n cumulative sum matrix where A[i][j] no longer contains its
own value, but the sum of all items within sub-matrix (0, 0) to (i, j). This can be done
simultaneously while reading the input and still runs in O(n2 ). The code shown below turns
the input square matrix (see Table 3.3.A) into a cumulative sum matrix (see Table 3.3.B).
With the sum matrix, we can answer the sum of any sub-matrix (i, j) to (k, l) in O(1)
using the code below. For example, let’s compute the sum of (1, 2) to (3, 3). We split
the sum into 4 parts and compute A[3][3] - A[0][3] - A[3][1] + A[0][1] = -3 - 13
- (-9) + (-2) = -9 as highlighted in Table 3.3.C. With this O(1) DP formulation, the
Max 2D Range Sum problem can now be solved in O(n4 ). For the largest test case of UVa
108 with n = 100, this is still fast enough.
From these two examples—the Max 1D and 2D Range Sum Problems—we can see that not
every range problem requires a Segment Tree or a Fenwick Tree as discussed in Section 2.4.3
or 2.4.4. Static-input range-related problems are often solvable with DP techniques. It is
also worth mentioning that the solution for a range problem is very natural to produce with
bottom-up DP techniques as the operand is already a 1D or a 2D array. We can still write
the recursive top-down solution for a range problem, but the solution is not as natural.
105
3.5. DYNAMIC PROGRAMMING
c Steven & Felix
As mentioned in Section 3.1, a naı̈ve Complete Search that enumerates all possible subse-
quences to find the longest increasing one is too slow as there are O(2n ) possible subsequences.
Instead of trying all possible subsequences, we can consider the problem with a different ap-
proach. We can write the state of this problem with just one parameter: i. Let LIS(i) be
the LIS ending at index i. We know that LIS(0) = 1 as the first number in A is itself a
subsequence. For i ≥ 1, LIS(i) is slightly more complex. We need to find the index j such
that j < i and A[j] < A[i] and LIS(j) is the largest. Once we have found this index j,
we know that LIS(i) = 1 + LIS(j). We can write this recurrence formally as:
106
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
There are clearly many overlapping sub-problems in LIS problem because to compute LIS(i),
we need to compute LIS(j) ∀j ∈ [0..i-1]. However, there are only n distinct states, the
indices of the LIS ending at index i, ∀i ∈ [0..n-1]. As we need to compute each state
with an O(n) loop, this DP algorithm runs in O(n2 ).
If needed, the LIS solution(s) can be reconstructed by storing the predecessor information
(the arrows in Figure 3.9) and tracing the arrows from index k that contain the highest value
of LIS(k). For example, LIS(5) is the optimal final state. Check Figure 3.9. We can trace
the arrows as follow: LIS(5) → LIS(4) → LIS(3) → LIS(0), so the optimal solution (read
backwards) is index {0, 3, 4, 5} or {-7, 2, 3, 8}.
The LIS problem can also be solved using the output-sensitive O(n log k) greedy +
D&C algorithm (where k is the length of the LIS) instead of O(n2 ) by maintaining an
array that is always sorted and therefore amenable to binary search. Let array L be an
array such that L(i) represents the smallest ending value of all length-i LISs found
so far. Though this definition is slightly complicated, it is easy to see that it is always
ordered—L(i-1) will always be smaller than L(i) as the second-last element of any
LIS (of length-i) is smaller than its last element. As such, we can binary search array L
to determine the longest possible subsequence we can create by appending the current
element A[i]—simply find the index of the last element in L that is less than A[i].
Using the same example, we will update array L step by step using this algorithm:
• Initially, at A[0] = -7, we have L = {-7}.
• We can insert A[1] = 10 at L[1] so that we have a length-2 LIS, L = {-7, 10}.
• For A[2] = 9, we replace L[1] so that we have a ‘better’ length-2 LIS ending:
L = {-7, 9}.
This is a greedy strategy. By storing the LIS with smaller ending value,
we maximize our ability to further extend the LIS with future values.
• For A[3] = 2, we replace L[1] to get an ‘even better’ length-2 LIS ending:
L = {-7, 2}.
• We insert A[4] = 3 at L[2] so that we have a longer LIS, L = {-7, 2, 3}.
• We insert A[5] = 8 at L[3] so that we have a longer LIS, L = {-7, 2, 3, 8}.
• For A[6] = 8, nothing changes as L[3] = 8.
L = {-7, 2, 3, 8} remains unchanged.
• For A[7] = 1, we improve L[1] so that L = {-7, 1, 3, 8}.
This illustrates how the array L is not the LIS of A. This step is important as
there can be longer subsequences in the future that may extend the length-2
subsequence at L[1] = 1. For example, try this test case: A = {-7, 10, 9, 2,
3, 8, 8, 1, 2, 3, 4}. The length of LIS for this test case is 5.
• The answer is the largest length of the sorted array L at the end of the process.
107
3.5. DYNAMIC PROGRAMMING
c Steven & Felix
Solution: Use these Complete Search recurrences val(id, remW) where id is the index of
the current item to be considered and remW is the remaining weight left in the knapsack:
1. val(id, 0) = 0 // if remW = 0, we cannot take anything else
2. val(n, remW) = 0 // if id = n, we have considered all items
3. if W[id] > remW, we have no choice but to ignore this item
val(id, remW) = val(id + 1, remW)
4. if W[id] ≤ remW, we have two choices: ignore or take this item; we take the maximum
val(id, remW) = max(val(id + 1, remW), V[id] + val(id + 1, remW - W[id]))
The answer can be found by calling value(0, S). Note the overlapping sub-problems in this
0-1 Knapsack problem. Example: After taking item 0 and ignoring item 1-2, we arrive at
state (3, 2)—at the third item (id = 3) with two units of weight left (remW = 2). After
ignoring item 0 and taking item 1-2, we also arrive at the same state (3, 2). Although
there are overlapping sub-problems, there are only O(nS) possible distinct states (as id can
vary between [0..n-1] and remW can vary between [0..S])! We can compute each of these
states in O(1), thus the overall time complexity16 of this DP solution is O(nS).
Note: The top-down version of this DP solution is often faster than the bottom-up
version. This is because not all states are actually visited, and hence the critical DP states
involved are actually only a (very small) subset of the entire state space. Remember: The
top-down DP only visits the required states whereas bottom-up DP visits all distinct states.
Both versions are provided in our source code library.
Source code: ch3 07 UVa10130.cpp/java
Solution: Use these Complete Search recurrence relations for change(value), where value
is the remaining amount of cents that we need to represent in coins:
16
If S is large such that N S >> 1M , this DP solution is not feasible, even with the space saving trick!
108
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
We can see that there are a lot of overlapping sub-problems in this Coin Change problem
(e.g. both change(10) and change(6) require the value of change(5)). However, there are
only O(V ) possible distinct states (as value can vary between [0..V])! As we need to try
n types of coins per state, the overall time complexity of this DP solution is O(nV ).
A variant of this problem is to count the number of possible (canonical) ways to get
value V cents using a list of denominations of n coins. For example 1 above, the answer
is 3: {1+1+1+1+1 + 1+1+1+1+1, 5 + 1+1+1+1+1, 5 + 5}.
Solution: Use these Complete Search recurrence relation: ways(type, value), where
value is the same as above but we now have one more parameter type for the index
of the coin type that we are currently considering. This second parameter type is
important as this solution considers the coin types sequentially. Once we choose to
ignore a certain coin type, we should not consider it again to avoid double-counting:
1. ways(type, 0) = 1 // one way, use nothing
2. ways(type, <0) = 0 // no way, we cannot reach negative value
3. ways(n, value) = 0 // no way, we have considered all coin types ∈ [0..n-1]
4. ways(type, value) = ways(type + 1, value) + // if we ignore this coin type,
ways(type, value - coinValue[type]) // plus if we use this coin type
There are only O(nV ) possible distinct states. Since each state can be computed in
O(1), the overall time complexity17 of this DP solution is O(nV ). The answer can be
found by calling ways(0, V). Note: If the coin values are not changed and you are
given many queries with different V, then we can choose not to reset the memo table.
Therefore, we run this O(nV ) algorithm once and just perform an O(1) lookup for
subsequent queries.
17
If V is large such that nV >> 1M , this DP solution is not feasible even with the space saving trick!
109
3.5. DYNAMIC PROGRAMMING
c Steven & Felix
A ‘brute force’ TSP solution (either iterative or recursive) that tries all O((n − 1)!) possible
tours (fixing the first city to vertex A in order to take advantage of symmetry) is only
effective when n is at most 12 as 11! ≈ 40M. When n > 12, such brute force solutions will
get a TLE in programming contests. However, if there are multiple test cases, the limit for
such ‘brute force’ TSP solution is probably just n = 11.
We can utilize DP for TSP since the computation of sub-tours is clearly overlapping, e.g.
the tour A − B − C−(n − 3) other cities that finally return to A clearly overlaps the tour
A − C − B−the same (n − 3) other cities that also return to A. If we can avoid re-computing
the lengths of such sub-tours, we can save a lot of computation time. However, a distinct
state in TSP depends on two parameters: The last city/vertex visited pos and something
that we may have not seen before—a subset of visited cities.
There are many ways to represent a set. However, since we are going to pass this set
information around as a parameter of a recursive function (if using top-down DP), the
representation we use must be lightweight and efficient! In Section 2.2, we have presented
a viable option for this usage: The bitmask. If we have n cities, we use a binary integer of
length n. If bit i is ‘1’ (on), we say that item (city) i is inside the set (it has been visited)
and item i is not inside the set (and has not been visited) if the bit is instead ‘0’ (off). For
example: mask= 1810 = 100102 implies that items (cities) {1, 4} are in19 the set (and have
been visited). Recall that to check if bit i is on or off, we can use mask & (1 << i). To set
bit i, we can use mask |= (1 << i).
Solution: Use these Complete Search recurrence relations for tsp(pos, mask):
1. tsp(pos, 2n − 1) = dist[pos][0] // all cities have been visited, return to starting city
// Note: mask = (1 << n) - 1 or 2n − 1 implies that all n bits in mask are on.
2. tsp(pos, mask) = min(dist[pos][nxt] + tsp(nxt, mask | (1 << nxt)))
// ∀ nxt ∈ [0..n-1], nxt != pos, and (mask & (1 << nxt)) is ‘0’ (turned off)
// We basically tries all possible next cities that have not been visited before at each step.
There are only O(n × 2n ) distinct states because there are n cities and we remember up to
2n other cities that have been visited in each tour. Each state can be computed in O(n),
18
Such a tour is called a Hamiltonian tour, which is a cycle in an undirected graph which visits each vertex
exactly once and also returns to the starting vertex.
19
Remember that in mask, indices starts from 0 and are counted from the right.
110
CHAPTER 3. PROBLEM SOLVING PARADIGMS
c Steven & Felix
thus the overall time complexity of this DP solution is O(2n × n2 ). This allows us to solve
up to20 n ≈ 16 as 162 × 216 ≈ 17M. This is not a huge improvement over the brute force
solution but if the programming contest problem involving TSP has input size 11 ≤ n ≤ 16,
then DP is the solution, not brute force. The answer can be found by calling tsp(0, 1):
We start from city 0 (we can start from any vertex; but the simplest choice is vertex 0) and
set mask = 1 so that city 0 is never re-visited again.
Usually, DP TSP problems in programming contests require some kind of graph prepro-
cessing to generate the distance matrix dist before running the DP solution. These variants
are discussed in Section 8.4.3.
DP solutions that involve a (small) set of Booleans as one of the parameters are more
well known as the DP with bitmask technique. More challenging DP problems involving this
technique are discussed in Section 8.3 and 9.2.
Visualization: www.comp.nus.edu.sg/∼stevenha/visualization/rectree.html
Source code: ch3 09 UVa10496.cpp/java
Exercise 3.5.2.1: The solution for the Max 2D Range Sum problem runs in O(n4 ). Actually,
there exists an O(n3 ) solution that combines the DP solution for the Max Range 1D Sum
problem on one dimension and uses the same idea as proposed by Kadane on the other
dimension. Solve UVa 108 with an O(n3 ) solution!
Exercise 3.5.2.2: The solution for the Range Minimum Query(i, j) on 1D arrays in Sec-
tion 2.4.3 uses Segment Tree. This is overkill if the given array is static and unchanged
throughout all the queries. Use a DP technique to answer RMQ(i, j) in O(n log n) pre-
processing and O(1) per query.
Exercise 3.5.2.3: Solve the LIS problem using the O(n log k) solution and also reconstruct
one of the LIS.
Exercise 3.5.2.4: Can we use an iterative Complete Search technique that tries all possible
subsets of n items as discussed in Section 3.2.1 to solve the 0-1 Knapsack problem? What
are the limitations, if any?
Exercise 3.5.2.5*: Suppose we add one more parameter to this classic 0-1 Knapsack prob-
lem. Let Ki denote the number of copies of item i for use in the problem. Example: n = 2,
V = {100, 70}, W = {5, 4}, K = {2, 3}, S = 17 means that there are two copies of item 0
with weight 5 and value 100 and there are three copies of item 1 with weight 4 and value
70. The optimal solution for this example is to take one of item 0 and three of item 1, with
a total weight of 17 and total value
n−1310. Solve new variant of the problem assuming that
1 ≤ n ≤ 500, 1 ≤ S ≤ 2000, n ≤ i=0 Ki ≤ 40000! Hint: Every integer can be written as a
sum of powers of 2.
Exercise 3.5.2.6*: The DP TSP solution shown in this section can still be slightly enhanced
to make it able to solve test case with n = 17 in contest environment. Show the required
minor change to make this possible! Hint: Consider symmetry!
Exercise 3.5.2.7*: On top of the minor change asked in Exercise 3.5.2.5*, what other
change(s) is/are needed to have a DP TSP solution that is able to handle n = 18 (or even
n = 19, but with much lesser number of test cases)?
20
As programming contest problems usually require exact solutions, the DP-TSP solution presented here
is already one of the best solutions. In real life, the TSP often needs to be solved for instances with thousands
of cities. To solve larger problems like that, we have non-exact approaches like the ones presented in [26].
111
3.5. DYNAMIC PROGRAMMING
c Steven & Felix