Example: confidence

Competitive Programmer’s Handbook - CSES

Competitive Programmer s HandbookAntti LaaksonenDraft July 3, 2018iiContentsPrefaceixI Basic techniques11 programming languages .. Input and output .. Working with numbers .. Shortening code .. Mathematics .. Contests and resources ..152 Time Calculation rules .. Complexity classes .. Estimating efficiency .. Maximum subarray sum ..213 Sorting theory .. Sorting in C++ .. Binary search ..314 Data Dynamic arrays .. Set structures .. Map structures .. Iterators and ranges .. Other structures .. Comparison to sorting ..445 Complete Generating subsets .. Generating permutations .. Backtracking .. Pruning the search .. Meet in the middle ..54iii6 Greedy Coin problem .. Scheduling.

Chapter 1 Introduction Competitive programming combines two topics: (1) the design of algorithms and (2) the implementation of algorithms. The design of algorithms consists of problem solving and mathematical thinking. Skills for analyzing problems and …

Tags:

  Programming, Chapter, Competitive, Competitive programming

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of Competitive Programmer’s Handbook - CSES

1 Competitive Programmer s HandbookAntti LaaksonenDraft July 3, 2018iiContentsPrefaceixI Basic techniques11 programming languages .. Input and output .. Working with numbers .. Shortening code .. Mathematics .. Contests and resources ..152 Time Calculation rules .. Complexity classes .. Estimating efficiency .. Maximum subarray sum ..213 Sorting theory .. Sorting in C++ .. Binary search ..314 Data Dynamic arrays .. Set structures .. Map structures .. Iterators and ranges .. Other structures .. Comparison to sorting ..445 Complete Generating subsets .. Generating permutations .. Backtracking .. Pruning the search .. Meet in the middle ..54iii6 Greedy Coin problem .. Scheduling.

2 Tasks and deadlines .. Minimizing sums .. Data compression ..627 Dynamic Coin problem .. Longest increasing subsequence .. Paths in a grid .. Knapsack problems .. Edit distance .. Counting tilings ..758 Amortized Two pointers method .. Nearest smaller elements .. Sliding window minimum ..819 Range Static array queries .. Binary indexed tree .. Segment tree .. Additional techniques ..9310 Bit Bit representation .. Bit operations .. Representing sets .. Bit optimizations .. Dynamic programming .. 102II Graph algorithms10711 Basics of Graph terminology .. Graph representation .. 11312 Graph Depth-first search .. Breadth-first search .. Applications .. 121iv13 Shortest Bellman Ford algorithm.

3 Dijkstra s algorithm .. Floyd Warshall algorithm .. 12914 Tree Tree traversal .. Diameter .. All longest paths .. Binary trees .. 13915 Spanning Kruskal s algorithm .. Union-find structure .. Prim s algorithm .. 14716 Directed Topological sorting .. Dynamic programming .. Successor paths .. Cycle detection .. 15517 Strong Kosaraju s algorithm .. 2 SAT problem .. 16018 Tree Finding ancestors .. Subtrees and paths .. Lowest common ancestor .. Offline algorithms .. 17019 Paths and Eulerian paths .. Hamiltonian paths .. De Bruijn sequences .. Knight s tours .. 17920 Flows and Ford Fulkerson algorithm .. Disjoint paths .. Maximum matchings .. Path covers .. 190vIII Advanced topics19521 Number Primes and factors.

4 Modular arithmetic .. Solving equations .. Other results .. 20522 Binomial coefficients .. Catalan numbers .. Inclusion-exclusion .. Burnside s lemma .. Cayley s formula .. 21523 Operations .. Linear recurrences .. Graphs and matrices .. 22224 Calculation .. Events .. Random variables .. Markov chains .. Randomized algorithms .. 23125 Game Game states .. Nim game .. Sprague Grundy theorem .. 23826 String String terminology .. Trie structure .. String hashing .. Z-algorithm .. 24727 Square root Combining algorithms .. Integer partitions .. Mo s algorithm .. 25528 Segment trees Lazy propagation .. Dynamic trees .. Data structures .. Two-dimensionality.

5 264vi29 Complex numbers .. Points and lines .. Polygon area .. Distance functions .. 27230 Sweep line Intersection points .. Closest pair problem .. Convex hull problem .. 278 Bibliography281viiviiiPrefaceThe purpose of this book is to give you a thorough introduction to competitiveprogramming. It is assumed that you already know the basics of programming ,but no previous background in Competitive programming is book is especially intended for students who want to learn algorithmsand possibly participate in the International Olympiad in Informatics (IOI) or inthe International Collegiate programming Contest (ICPC). Of course, the book isalso suitable for anybody else interested in Competitive takes a long time to become a good Competitive programmer, but it is alsoan opportunity to learn a lot.

6 You can be sure that you will get a good generalunderstanding of algorithms if you spend time reading the book, solving problemsand taking part in book is under continuous development. You can always send feedback onthe book July 2018 Antti LaaksonenixxPart IBasic techniques1 chapter 1 IntroductionCompetitive programming combines two topics: (1) the design of algorithms and(2) the implementation of of algorithmsconsists of problem solving and mathematicalthinking. Skills for analyzing problems and solving them creatively are algorithm for solving a problem has to be both correct and efficient, and thecore of the problem is often about inventing an efficient knowledge of algorithms is important to Competitive , a solution to a problem is a combination of well-known techniques andnew insights.

7 The techniques that appear in Competitive programming also formthe basis for the scientific research of of algorithmsrequires good programming skills. Incompetitive programming , the solutions are graded by testing an implementedalgorithm using a set of test cases. Thus, it is not enough that the idea of thealgorithm is correct, but the implementation also has to be good coding style in contests is straightforward and concise. Programsshould be written quickly, because there is not much time available. Unlike intraditional software engineering, the programs are short (usually at most a fewhundred lines of code), and they do not need to be maintained after the languagesAt the moment, the most popular programming languages used in contests areC++, Python and Java. For example, in Google Code Jam 2017, among the best3,000 participants, 79 % used C++, 16 % used Python and 8 % used Java [29].

8 Some participants also used several people think that C++ is the best choice for a Competitive programmer,and C++ is nearly always available in contest systems. The benefits of using C++are that it is a very efficient language and its standard library contains a largecollection of data structures and the other hand, it is good to master several languages and understandtheir strengths. For example, if large integers are needed in the problem, Pythoncan be a good choice, because it contains built-in operations for calculating with3large integers. Still, most problems in programming contests are set so that usinga specific programming language is not an unfair example programs in this book are written in C++, and the standardlibrary s data structures and algorithms are often used. The programs follow theC++11 standard, which can be used in most contests nowadays.

9 If you cannotprogram in C++ yet, now is a good time to start ++ code templateA typical C++ code template for Competitive programming looks like this:#include <bits/stdc++.h>using namespace std;int main() {// solution comes here}The#includeline at the beginning of the code is a feature of theg++compilerthat allows us to include the entire standard library. Thus, it is not needed toseparately include libraries such asiostream,vectorandalgorithm, but ratherthey are available declares that the classes and functions of the standard librarycan be used directly in the code. Without theusingline we would have to write,for example,std::cout, but now it suffices to code can be compiled using the following command:g++ -std=c++11 -O2 -Wall -o testThis command produces a binary filetestfrom the source Thecompiler follows the C++11 standard (-std=c++11), optimizes the code (-O2) andshows warnings about possible errors (-Wall).

10 Input and outputIn most contests, standard streams are used for reading input and writing C++, the standard streams arecinfor input andcoutfor output. In addition,the C functionsscanfandprintfcan be input for the program usually consists of numbers and strings that areseparated with spaces and newlines. They can be read from thecinstream asfollows:int a, b;string x;cin >> a >> b >> x;4 This kind of code always works, assuming that there is at least one space ornewline between each element in the input. For example, the above code canread both of the following inputs:123 456 monkey123 456monkeyThecoutstream is used for output as follows:int a = 123, b = 456;string x = "monkey";cout << a << " " << b << " " << x << "\n";Input and output is sometimes a bottleneck in the program. The followinglines at the beginning of the code make input and output more efficient:ios::sync_with_stdio(0); (0);Note that the newline"\n"works faster thanendl, becauseendlalwayscauses a flush C functionsscanfandprintfare an alternative to the C++ standardstreams.


Related search queries