CompetitiveProgramminginPython Want to kill it at your job interview in the tech industry? Want to win that coding competition? Learn all the algorithmic techniques and programming skills you need fromtwoexperiencedcoaches,problem-setters,andjudgesforcodingcompetitions. The authors highlight the versatility of each algorithm by considering a variety of problemsandshowhowtoimplementalgorithmsinsimpleandefficientcode.What toexpect: * Master128algorithmsinPython. * Discovertherightwaytotackleaproblemandquicklyimplementasolutionoflow complexity. * Understand classic problems like Dijkstra’s shortest path algorithm and Knuth–Morris–Pratt’sstringmatchingalgorithm,pluslesser-knowndatastructures likeFenwicktreesandKnuth’sdancinglinks. * Developaframeworktotacklealgorithmicproblemsolving,including:Definition, Complexity,Applications,Algorithm,KeyInformation,Implementation,Variants, InPractice,andProblems. * Pythoncodeincludedinthebookandonthecompanionwebsite. Christoph Dürr is a senior researcher at the French National Center for Scientific Research (CNRS), affiliated with the Sorbonne University in Paris. After a PhD in 1996atParis-SudUniversity,heworkedforoneyearasapostdoctoralresearcherat the International Computer Science Institute in Berkeley and one year in the School of Computer Science and Engineering in the Hebrew University of Jerusalem in Israel.Hehasworkedinthefieldsofquantumcomputation,discretetomographyand algorithmicgametheory,andhiscurrentresearchactivityfocusesonalgorithmsand optimisation. From 2007 to 2014, he taught a preparation course for programming contests at the engineering school École Polytechnique, and acts regularly as a problemsetter,trainer,orcompetitorforvariouscodingcompetitions.Inaddition,he lovescarrotcake. Jill-Jênn Vie is a research scientist at Inria in machine learning. He is an alumnus from École normale supérieure Paris-Saclay, where he founded the algorithmic club of Paris-Saclay (CAPS) and coached several teams for the International Collegiate Programming Contest (ICPC). He published a book in theoretical computer science to help students prepare for prestigious French competitive exams such as Grandes Écoles or agrégation, and directed a television show “Blame the Algorithm” about the algorithms that govern our lives. He is part of the advisory board of the French Computer Science Society (SIF), itself a member of the International Federation for InformationProcessing(IFIP). Competitive Programming in Python 128 Algorithms to Develop Your Coding Skills CHRISTOPH DÜRR CNRS,SorbonneUniversity JILL-JÊNN VIE Inria TranslatedbyGregGibbonsandDanièleGibbons UniversityPrintingHouse,CambridgeCB28BS,UnitedKingdom OneLibertyPlaza,20thFloor,NewYork,NY10006,USA 477WilliamstownRoad,PortMelbourne,VIC3207,Australia 314–321,3rdFloor,Plot3,SplendorForum,JasolaDistrictCentre,NewDelhi–110025,India 79AnsonRoad,#06–04/06,Singapore079906 CambridgeUniversityPressispartoftheUniversityofCambridge. ItfurtherstheUniversity’smissionbydisseminatingknowledgeinthepursuitof education,learning,andresearchatthehighestinternationallevelsofexcellence. www.cambridge.org Informationonthistitle:www.cambridge.org/9781108716826 DOI:10.1017/9781108591928 ©CambridgeUniversityPress2021 TranslationfromtheFrenchlanguageedition: Programmationefficace-128algorithmesqu’ilfautavoircomprisetcodésenPythonaucourdesavie ByChristophDürr&Jill-JênnVie Copyright©2016EditionMarketingS.A. www.editions-ellipses.fr AllRightsReserved Thispublicationisincopyright.Subjecttostatutoryexception andtotheprovisionsofrelevantcollectivelicensingagreements, noreproductionofanypartmaytakeplacewithoutthewritten permissionofCambridgeUniversityPress. Firstpublished2021 PrintedintheUnitedKingdombyTJBooksLimited,PadstowCornwall AcataloguerecordforthispublicationisavailablefromtheBritishLibrary. LibraryofCongressCataloging-in-PublicationData Names:Dürr,Christoph,1969–author.|Vie,Jill-Jênn,1990–author.| Gibbons,Greg,translator.|Gibbons,Danièle,translator. Title:CompetitiveprogramminginPython:128algorithmstodevelopyour codingskills/ChristophDürr,Jill-JênnVie;translatedbyGreg Gibbons,DanièleGibbons. Othertitles:Programmationefficace.English Description:Firstedition.|NewYork:CambridgeUniversityPress,2020. |Includesbibliographicalreferencesandindex. Identifiers:LCCN2020022774(print)|LCCN2020022775(ebook)| ISBN9781108716826(paperback)|ISBN9781108591928(epub) Subjects:LCSH:Python(Computerprogramlanguage)|Algorithms. Classification:LCCQA76.73.P98D87132020(print)|LCCQA76.73.P98 (ebook)|DDC005.13/3–dc23 LCrecordavailableathttps://lccn.loc.gov/2020022774 LCebookrecordavailableathttps://lccn.loc.gov/2020022775 ISBN978-1-108-71682-6Paperback CambridgeUniversityPresshasnoresponsibilityforthepersistenceoraccuracyof URLsforexternalorthird-partyinternetwebsitesreferredtointhispublication anddoesnotguaranteethatanycontentonsuchwebsitesis,orwillremain, accurateorappropriate. Contents Preface pageix 1 Introduction 1 1.1 ProgrammingCompetitions 1 1.2 PythoninaFewWords 5 1.3 Input-Output 13 1.4 Complexity 17 1.5 AbstractTypesandEssentialDataStructures 20 1.6 Techniques 28 1.7 Advice 37 1.8 AProblem:‘FrostingontheCake’ 39 2 CharacterStrings 42 2.1 Anagrams 42 2.2 T9—Texton9Keys 43 2.3 SpellCheckingwithaLexicographicTree 46 2.4 SearchingforPatterns 48 2.5 MaximalBoundaries—Knuth–Morris–Pratt 49 2.6 PatternMatching—Rabin–Karp 56 2.7 LongestPalindromeofaString—Manacher 59 3 Sequences 62 3.1 ShortestPathinaGrid 62 3.2 TheLevenshteinEditDistance 63 3.3 LongestCommonSubsequence 65 3.4 LongestIncreasingSubsequence 68 3.5 WinningStrategyinaTwo-PlayerGame 70 4 Arrays 72 4.1 MergeofSortedLists 73 4.2 SumOveraRange 74 4.3 DuplicatesinaRange 74 4.4 MaximumSubarraySum 75 vi Contents 4.5 QueryfortheMinimumofaRange—SegmentTree 75 4.6 QuerytheSumoveraRange—FenwickTree 77 4.7 WindowswithkDistinctElements 80 5 Intervals 82 5.1 IntervalTrees 82 5.2 UnionofIntervals 85 5.3 TheIntervalPointCoverProblem 85 6 Graphs 88 6.1 EncodinginPython 88 6.2 ImplicitGraphs 90 6.3 Depth-FirstSearch—DFS 91 6.4 Breadth-FirstSearch—BFS 93 6.5 ConnectedComponents 94 6.6 BiconnectedComponents 97 6.7 TopologicalSort 102 6.8 StronglyConnectedComponents 105 6.9 2-Satisfiability 110 7 CyclesinGraphs 113 7.1 EulerianTour 113 7.2 TheChinesePostmanProblem 116 7.3 CycleswithMinimalRatioofWeighttoLength—Karp 117 7.4 CycleswithMinimalCost-to-TimeRatio 120 7.5 TravellingSalesman 120 7.6 FullExample:MenuTour 121 8 ShortestPaths 124 8.1 CompositionProperty 124 8.2 GraphswithWeights0or1 126 8.3 GraphswithNon-negativeWeights—Dijkstra 127 8.4 GraphswithArbitraryWeights—Bellman–Ford 130 8.5 AllSource–Destinationpaths—Floyd–Warshall 132 8.6 Grid 133 8.7 Variants 135 9 MatchingsandFlows 138 9.1 MaximumBipartiteMatching 139 9.2 Maximal-WeightPerfectMatching—Kuhn–Munkres 145 9.3 PlanarMatchingwithoutCrossings 151 9.4 StableMarriages—Gale–Shapley 153 Contents vii 9.5 MaximumFlowbyFord–Fulkerson 155 9.6 MaximumFlowbyEdmonds–Karp 158 9.7 MaximumFlowbyDinic 159 9.8 Minimums−t Cut 162 9.9 s−t MinimumCutforPlanarGraphs 163 9.10 ATransportProblem 165 9.11 ReductionsbetweenMatchingsandFlows 165 9.12 WidthofaPartialOrder—Dilworth 167 10 Trees 171 10.1 HuffmanCoding 172 10.2 LowestCommonAncestor 174 10.3 LongestPathinaTree 178 10.4 MinimumWeightSpanningTree—Kruskal 179 11 Sets 182 11.1 TheKnapsackProblem 182 11.2 MakingChange 184 11.3 SubsetSum 185 11.4 Thek-sumProblem 187 12 PointsandPolygons 189 12.1 ConvexHull 190 12.2 MeasuresofaPolygon 193 12.3 ClosestPairofPoints 195 12.4 SimpleRectilinearPolygon 198 13 Rectangles 200 13.1 FormingRectangles 200 13.2 LargestSquareinaGrid 201 13.3 LargestRectangleinaHistogram 202 13.4 LargestRectangleinaGrid 204 13.5 UnionofRectangles 205 13.6 UnionofDisjointRectangles 212 14 NumbersandMatrices 214 14.1 GCD 214 14.2 BézoutCoefficients 214 14.3 BinomialCoefficients 215 14.4 FastExponentiation 216 14.5 PrimeNumbers 217 14.6 EvaluateanArithmeticalExpression 218 viii Contents 14.7 SystemofLinearEquations 221 14.8 MultiplicationofaMatrixSequence 225 15 ExhaustiveSearch 227 15.1 AllPathsforaLaser 227 15.2 TheExactCoverProblem 231 15.3 Problems 237 15.4 Sudoku 238 15.5 EnumerationofPermutations 240 15.6 LeCompteestBon 243 16 Conclusion 245 16.1 CombineAlgorithmstoSolveaProblem 245 16.2 ForFurtherReading 245 16.3 Rendez-vousontryalgo.org 246 Debuggingtool 247 References 248 Index 251 Preface Algorithms play an important role in our society, solving numerous mathematical problems which appear in a broad spectrum of situations. To give a few examples, thinkofplanningtaxiroutesgivenasetofreservations(seeSection9.12);assigning students to schools in a large urban school district, such as New York (see Section 9.4); or identifying a bottleneck in a transportation network (see Section 9.8). This iswhyjobinterviewsintheIT(InformationTechnology)industrytestcandidatesfor theirproblem-solvingskills.Manyprogrammingcontestsareorganisedbycompanies such as Google, Facebook and Microsoft to spot gifted candidates and then send them job offers. This book will help students to develop a culture of algorithms and data structures,sothat they know how toapply them properly when faced withnew mathematicalproblems. Designing the right algorithm to solve a given problem is only half of the work; to complete the job, the algorithm needs to be implemented efficiently. This is why this book also emphasises implementation issues, and provides full source code for mostofthealgorithmspresented.WehavechosenPythonfortheseimplementations. Whatmakesthislanguagesoenticingisthatitallowsaparticularlyclearandrefined expression,illustratingtheessentialstepsofthealgorithm,withoutobscuringthings behind burdensome notations describing data structures. Surprisingly, it is actually possibletore-readcodewrittenseveralmonthsagoandevenunderstandit! We have collected here 128 algorithmic problems, indexed by theme rather than by technique. Many are classic, whereas certain are atypical. This work should prove itself useful when preparing to solve the wide variety of problems posed in programming contests such as ICPC, Google Code Jam, Facebook Hacker Cup, Prologin, France-ioi, etc. We hope that it could serve as a basis for an advanced course in programming and algorithms, where even certain candidates for the ‘agrégation de mathématiques option informatique’ (French competitive exam for thehighestteacher’scertification)willfindafeworiginaldevelopments.Thewebsite tryalgo.org, maintained by the authors, contains links to the code of this book, as wellastoselectedproblemsatvariousonlinecontests.Thisallowsreaderstoverify theirfreshlyacquiredskills. This book would never have seen the light of day without the support of the authors’ life partners. Danke, Hương. Merci, 智子. The authors would also like to thank the students of the École polytechnique and the École normale supérieure of Paris-Saclay, whose practice, often nocturnal, generated a major portion of the