This is the 100% identical eBook (PDF) version of CP4 Book 1 that was released on 19 July 2020 Please read https://cpbook.net/errata for the latest known updates to this PDF c Steven,Felix,Suhendry (cid:13) ii Contents Forewords for CP4 vii Testimonials of CP1/2/3 xiii Preface for CP4 xv Authors’ Profiles xxvii Abbreviations xxix 1 Introduction 1 1.1 CompetitiveProgramming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 TheCompetitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 InternationalOlympiadinInformatics(IOI) . . . . . . . . . . . . . . 3 1.2.2 InternationalCollegiateProgrammingContests(ICPC) . . . . . . . . 4 1.2.3 OtherProgrammingContests . . . . . . . . . . . . . . . . . . . . . . 6 1.3 TipstobeCompetitive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3.1 Tip1: TypeCodeFaster! . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3.2 Tip2: QuicklyIdentifyProblemTypes . . . . . . . . . . . . . . . . . 8 1.3.3 Tip3: DoAlgorithmAnalysis . . . . . . . . . . . . . . . . . . . . . . 10 1.3.4 Tip4: MasterProgrammingLanguages. . . . . . . . . . . . . . . . . 15 1.3.5 Tip5: MastertheArtofTestingCode . . . . . . . . . . . . . . . . . 18 1.3.6 Tip6: PracticeandMorePractice . . . . . . . . . . . . . . . . . . . 21 1.3.7 Tip7: TeamWork(forICPC) . . . . . . . . . . . . . . . . . . . . . . 22 1.4 GettingStarted: TheEasyProblems . . . . . . . . . . . . . . . . . . . . . . 23 1.4.1 AnatomyofaProgrammingContestProblem . . . . . . . . . . . . . 23 1.4.2 TypicalInput/OutputRoutines . . . . . . . . . . . . . . . . . . . . . 23 1.4.3 TimetoStarttheJourney . . . . . . . . . . . . . . . . . . . . . . . . 26 1.4.4 GettingOurFirstAccepted(AC)Verdict . . . . . . . . . . . . . . . 27 1.5 BasicStringProcessingSkills . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.6 TheAdHocProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.7 SolutionstoNon-StarredExercises . . . . . . . . . . . . . . . . . . . . . . . 41 1.8 ChapterNotes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2 Data Structures and Libraries 53 2.1 OverviewandMotivation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.2 LinearDSwithBuilt-inLibraries . . . . . . . . . . . . . . . . . . . . . . . . 55 2.2.1 Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.2.2 SpecialSortingProblems . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.2.3 Bitmask . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.2.4 BigInteger(Python&Java) . . . . . . . . . . . . . . . . . . . . . . . 66 iii CONTENTS c Steven,Felix,Suhendry (cid:13) 2.2.5 LinkedDataStructures. . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.2.6 SpecialStack-basedProblems . . . . . . . . . . . . . . . . . . . . . . 71 2.3 Non-LinearDSwithBuilt-inLibraries . . . . . . . . . . . . . . . . . . . . . 78 2.3.1 BinaryHeap(PriorityQueue) . . . . . . . . . . . . . . . . . . . . . . 78 2.3.2 HashTable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 2.3.3 BalancedBinarySearchTree(bBST) . . . . . . . . . . . . . . . . . . 84 2.3.4 OrderStatisticsTree . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 2.4 DSwithOurOwnLibraries . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 2.4.1 Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 2.4.2 Union-FindDisjointSets . . . . . . . . . . . . . . . . . . . . . . . . . 99 2.4.3 Fenwick(BinaryIndexed)Tree . . . . . . . . . . . . . . . . . . . . . 104 2.4.4 SegmentTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 2.5 SolutiontoNon-StarredExercises . . . . . . . . . . . . . . . . . . . . . . . . 124 2.6 ChapterNotes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 3 Problem Solving Paradigms 129 3.1 OverviewandMotivation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 3.2 CompleteSearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 3.2.1 IterativeCompleteSearch . . . . . . . . . . . . . . . . . . . . . . . . 131 3.2.2 RecursiveCompleteSearch. . . . . . . . . . . . . . . . . . . . . . . . 135 3.2.3 CompleteSearchTips . . . . . . . . . . . . . . . . . . . . . . . . . . 139 3.2.4 CompleteSearchinProgrammingContests. . . . . . . . . . . . . . . 143 3.3 DivideandConquer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 3.3.1 InterestingUsagesofBinarySearch . . . . . . . . . . . . . . . . . . . 148 3.3.2 TernarySearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 3.3.3 DivideandConquerinProgrammingContests . . . . . . . . . . . . . 153 3.4 Greedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 3.4.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 3.4.2 GreedyAlgorithminProgrammingContests . . . . . . . . . . . . . . 161 3.5 DynamicProgramming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 3.5.1 DPIllustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 3.5.2 ClassicalExamples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 3.5.3 Non-ClassicalExamples . . . . . . . . . . . . . . . . . . . . . . . . . 184 3.5.4 DynamicProgramminginProgrammingContests . . . . . . . . . . . 187 3.6 SolutiontoNon-StarredExercises . . . . . . . . . . . . . . . . . . . . . . . . 190 3.7 ChapterNotes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 4 Graph 193 4.1 OverviewandMotivation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 4.2 GraphTraversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 4.2.1 OverviewandMotivation . . . . . . . . . . . . . . . . . . . . . . . . 195 4.2.2 DepthFirstSearch(DFS) . . . . . . . . . . . . . . . . . . . . . . . . 195 4.2.3 BreadthFirstSearch(BFS) . . . . . . . . . . . . . . . . . . . . . . . 197 4.2.4 FindingConnectedComponents(UndirectedGraph) . . . . . . . . . 198 4.2.5 FloodFill(Implicit2DGridGraph) . . . . . . . . . . . . . . . . . . 199 4.2.6 TopologicalSort(DirectedAcyclicGraph) . . . . . . . . . . . . . . . 200 4.2.7 BipartiteGraphCheck(UndirectedGraph) . . . . . . . . . . . . . . 202 4.2.8 CycleCheck(DirectedGraph) . . . . . . . . . . . . . . . . . . . . . . 203 4.2.9 FindingArticulationPointsandBridges(UndirectedGraph) . . . . . 205 4.2.10 FindingStronglyConnectedComponents(DirectedGraph). . . . . . 208 iv CONTENTS c Steven,Felix,Suhendry (cid:13) 4.2.11 GraphTraversalinProgrammingContests . . . . . . . . . . . . . . . 211 4.3 MinimumSpanningTree(MST) . . . . . . . . . . . . . . . . . . . . . . . . . 215 4.3.1 OverviewandMotivation . . . . . . . . . . . . . . . . . . . . . . . . 215 4.3.2 Kruskal’sAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 4.3.3 Prim’sAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 4.3.4 OtherApplications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 4.3.5 MSTinProgrammingContests . . . . . . . . . . . . . . . . . . . . . 221 4.4 Single-SourceShortestPaths(SSSP) . . . . . . . . . . . . . . . . . . . . . . 223 4.4.1 OverviewandMotivation . . . . . . . . . . . . . . . . . . . . . . . . 223 4.4.2 OnUnweightedGraph: BFS . . . . . . . . . . . . . . . . . . . . . . . 223 4.4.3 OnWeightedGraph: Dijkstra’s . . . . . . . . . . . . . . . . . . . . . 227 4.4.4 OnSmallGraph(withNegativeCycle): Bellman-Ford . . . . . . . . 234 4.4.5 SSSPinProgrammingContests . . . . . . . . . . . . . . . . . . . . . 237 4.5 All-PairsShortestPaths(APSP) . . . . . . . . . . . . . . . . . . . . . . . . 241 4.5.1 OverviewandMotivation . . . . . . . . . . . . . . . . . . . . . . . . 241 4.5.2 Floyd-WarshallAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . 242 4.5.3 OtherApplications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 4.5.4 APSPinProgrammingContests. . . . . . . . . . . . . . . . . . . . . 246 4.6 SpecialGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 4.6.1 DirectedAcyclicGraph. . . . . . . . . . . . . . . . . . . . . . . . . . 249 4.6.2 Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 4.6.3 BipartiteGraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 4.6.4 EulerianGraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 4.6.5 SpecialGraphsinProgrammingContests. . . . . . . . . . . . . . . . 263 4.7 SolutiontoNon-StarredExercises . . . . . . . . . . . . . . . . . . . . . . . . 267 4.8 ChapterNotes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 Bibliography 276 v CONTENTS c Steven,Felix,Suhendry (cid:13) vi Forewords for CP4 Bill Poucher Introduction In 1970, the Texas A&M UPE Honor Society hosted the first university competitive pro- gramming competition in the history of the ICPC. The first Finals was held in 1977 in AtlantainconjunctionwiththeWinterMeetingoftheACMComputerScienceConference. The ICPC International Collegiate Programming Contest hosted regional competitions at 643 sites in 104 countries for 59000 team members and their 5043 coaches from over 3400 universitiesthatspantheglobe. Thetop135teamsofthreewilladvancetotheICPCWorld FinalsinMoscowhostedbyMIPTscheduledforJune2021. ICPC alumni number over 400,000 worldwide, many playing key roles in building the globaldigitalcommunityformanydecades. TheICPCistherootofcompetitiveprogram- mingthatreachesoutthroughtheglobaldigitalcommunitytopersonsfromallculturesand inincreasingly-youngergenerations. TheUVaOnlineJudgeopenedthedoorsforonlinecompetitionandaccesstoICPCprob- lemsunderthedirectionofProfessorMiguelA´ngelRevilla. Threeofthestar-studdedteam areStevenHalim,FelixHalim,andSuhendryEffendy,authorsofCompetitiveProgramming 4, Book 1 and Book 2. Their work will be honored at the ICPC World Finals in Moscow hostedbyMIPTwithaspecialawardfromtheICPCFoundation. Competitive Programming Whatiscompetitiveprogrammingandwhyshouldyougetinvolved? Firstandforemost,it’s a mind sport. It more fully develops your algorithmic reasoning skills and bridges the gap between theory and application in bite-sized chunks. Full participation develops problem- solving intuition and competence. Get ready for the Digital Renaissance that will shape your world in the coming decades. To understand the landscape, it is important to shape yourmindbeyondaswarmofbuzzwords. Doitasateamsport. How do we get started? StartwithCompetitiveProgramming4,Book1andBook2. StartwithBook1first:). The authorsareseasonedcompetitiveprogrammingexpertswhohavededicateddecadesofwork tohelpatalllevelsofthesport. Inparallel,engageinaculturethatdevelopshabitsexcellence. Youarethefirstgenera- tionthathasneverbeendisconnected. Beingconnectedisbestwhenwebindourstrengths togetherincommoncause. Dothatandpreparetomeetthechallengesthatwilldefineyour generation. Lifeneedsyou. Weareborntocompete. Wecompetebestwhenwecompetetogether,in goodfaith,ingoodwill,andwithgooddeeds. Whenyoucometocollege,considertheICPC vii FOREWORDS BillPoucher andthenewprogramICPCUniversityCommonsthatwillprovideaspectrumofactivities thathappenoutsideoftheclassroom. Youcanvisithttps://icpc.globalfordetails. Why get started? Isdevelopingyourproblem-solvingskillsimportant? Yes. Ispreparingforafutureengaged in the global digital community important? Yes. Is following T.S. Elliot’s advice that to fullydevelopyoumustgotoofar? Yes. Dothatincompetitiveprogramming. Becarefulof pursuitsthatarenotreversible. Is competitive programming practical? Aristotle asserted that there is nothing more practical than engaging in mental activities and reflections which have their goal in them- selvesandtakepacefortheirownsake. Letmerecommendthatyouengageyourspiritin building a more beautiful world. In the immense scope of life, abundant small kindnesses makeadifference. Findfriendswithcommoninterestandembracethiscycle: Repeatforalifetime: Study;Practice;Rehearse;DressRehearse;Perform. Itworksforathletes. Itworksformusicians. Itworksforallperformancearts. Itwillworkforyou. Best,Bill Dr. WilliamB.“Bill”Poucher,Ph.D.,ACMFellow ProfessorofComputerScience,BaylorUniversity ExecutiveDirector,ICPCInternationalCollegiateProgrammingContest President,ICPCFoundation July13th,2020. viii FOREWORDS MiguelRevillaRodr´ıguez Miguel Revilla Rodr´ıguez Almost 20 years ago (on November 11th, 2003, to be precise), my father (Miguel A´ngel Revilla)receivedane-mailwiththefollowingmessage: “IshouldsayinasimplewordthatwiththeUVaSite, youhavegivenbirthto anewCIVILIZATIONandwiththebooksyouwrite(hemeant“Programming Challenges: TheProgrammingContestTrainingManual”[53],coauthoredwith StevenSkiena),youinspirethesoldierstocarryonmarching. Mayyoulivelong toservethehumanitybyproducingsuper-humanprogrammers.” What,inmyfather’swords,was“clearly an exaggeration”,causedsomethinking. Andit’s notasecretthatthoughtscaneasilyleadtodreams. Hisdreamwastocreateacommunity aroundtheprojecthehadstarted,aspartofisteachingjobattheUniversityofValladolid, Spain, that gathered people from all around the world working together towards the same ideal,thesamequest. Withalittlesearching,ontheprimitiveInternetofthefirstyearsof our century, a whole online community of excellent users and tools, built around the UVa site,cametolight. ThewebsiteMethodstoSolve1,createdbyaveryyoungstudentfromIndonesia,wasone ofthemostimpressiveamongthem. Therewastheresultofthehardworkofarealgenius ofalgorithmsandcomputerscience. Theseedwasplantedtobelievethatthedreamcould come true. Moreover, it was not only that the leaves of that growing tree were a perfect match, but the root of both projects were exactly the same: to serve the humanity. That youngstudent, theauthorofthee-mailandthewebsitethatputmyfathertodream, was StevenHalim. LaterhewoulddiscoverthatStevenwasnotaloneinhisquest,ashisyounger brother,Felix,sharedhisview,hisinterests,andhisextraordinarycapabilities. After15yearsoffruitfulcollaborationand,moreimportant,friendshipwithStevenand Felix, my father sadly passed away in 2018. His work, and his dreams, now belong to us, thenextgeneration. Thisbookisthelivingproofthatthedreamhasbecometrue. “Ican’timagineabettercomplementfortheUVaOnlineJudge”,aremyfather’swords. Now, with this fourth version of Competitive Programming in my hands, I can add that I can’timaginetheveryexistenceoftheOnlineJudgewithoutthisbook. Bothprojectshave grown in parallel and are, no doubt, perfect complements and companions to each other. Bypracticingandmasteringmostprogrammingexercisesinthisbook,thereadercanlearn how to solve hundreds of tasks and find a place in the top 500 best Online Judge coders. You have in your hands over 2000 (yes, two thousand!) selected, classified, and carefully commentedproblemsfromtheOnlineJudge. The authors, in the past two decades, have grown from contestants, to coaches and, finally, masters in the art of competitive programming. They perfectly know every curve and crossroad in that long path, and they can put themselves in the skins of the young IOI contestant, the ICPC newcomer or the seasoned coach, speaking to each in their own language. Thisbookis,forthatveryreason,theperfectreadingforallofthem. Nomatter if you are starting as a competitive programmer in your local IOI, or are coaching in the nextICPCWorldFinals,nodoubtthisISthebookforyou. 1Pleasevisithttps://cpbook.net/methodstosolve ix FOREWORDS MiguelRevillaRodr´ıguez Ilovemovies,Iadoreclassicmovies,andIknowthatwhatI’mwatchingisamasterpiece, when,afterthefilmends,Ican’twaittostartalloveragain. InStevenandFelixownwords “the book is not meant to be read once, but several times”. And you will find that same feeling,notonlybecausetheauthorsrecommendit,butbecauseyouwillbeanxioustoread andre-readitas,likeinthegreatestmovies,youwillfindsomethingnewandamazingeach time. Thisbookis,bythatlogic,amasterpiece. IalsohavethegreathonorofbeingtheSpanishlanguagetranslatorofthisbook. Trans- lating requires a very meticulous process of converting the words while keeping the spirit. You have to think as the author would think, and have to perfectly understand not only what the author is saying, but also what the author is meaning. It is a handcrafting exer- cise. Havinggoneforthandbackthroughthistexthundredsoftimes,Ihaveenjoyedevery concept,everynewidea,andeverytip,notonlybywhatiswritteninit,butalsobywhat it wants to achieve. The quest of making better programmers and, behind that, the quest ofservinghumanity. Thisbookis,indeed,atrulymasterpiece. Onceyou’vereadthisbookseveraltimes,youwillrealizehowmuchabetterprogrammer youarebut,believeitornot,youwillrealizethatyouarealsoahappierperson. MiguelRevillaRodr´ıguez(MiguelJr) OnlineJudgeManager https://onlinejudge.org July1st,2020,Valladolid. x