MULTIPLE CHOICE QUESTION BANK IN COMPUTER SCIENCE FOR COMPETITIONS

By STEVEN ANDERSON

CONTENTS INTRODUCTION WHAT IS COMPETITIVE PROGRAMMING? PROGRAMMING CONTESTS TIPS FOR PRACTICING ABOUT THIS BOOK CSES PROBLEM SET OTHER RESOURCES REFERENCES PROGRAMMING TECHNIQUES LANGUAGE FEATURES INPUT AND OUTPUT WORKING WITH NUMBERS SHORTENING CODE RECURSIVE ALGORITHMS GENERATING SUBSETS GENERATING PERMUTATIONS BACKTRACKING BIT MANIPULATION BIT OPERATIONS REPRESENTING SETS REFERENCE EF?CIENCY TIME COMPLEXITY CALCULATION RULES COMMON TIME COMPLEXITIES ESTIMATING EF?CIENCY FORMAL DE?NITIONS ALGORITHM DESIGN EXAMPLES MAXIMUM SUBARRAY SUM TWO QUEENS PROBLEM CODE OPTIMIZATION COMPILER OUTPUT PROCESSOR FEATURES SORTING AND SEARCHING SORTING ALGORITHMS BUBBLE SORT MERGE SORT SORTING LOWER BOUND COUNTING SORT SORTING IN PRACTICE SOLVING PROBLEMS BY SORTING SWEEP LINE ALGORITHMS SCHEDULING EVENTS TASKS AND DEADLINES BINARY SEARCH IMPLEMENTING THE SEARCH FINDING OPTIMAL SOLUTIONS DATA STRUCTURES DYNAMIC ARRAYS VECTORS ITERATORS AND RANGES OTHER STRUCTURES SET STRUCTURES SETS AND MULTISETS MAPS PRIORITY QUEUES POLICY-BASED SETS EXPERIMENTS SET VERSUS SORTING MAP VERSUS ARRAY PRIORITY QUEUE VERSUS MULTISET DYNAMIC PROGRAMMING BASIC CONCEPTS WHEN GREEDY FAILS FINDING AN OPTIMAL SOLUTION COUNTING SOLUTIONS FURTHER EXAMPLES LONGEST INCREASING SUBSEQUENCE PATHS IN A GRID KNAPSACK PROBLEMS FROM PERMUTATIONS TO SUBSETS COUNTING TILINGS GRAPH ALGORITHMS BASICS OF GRAPHS GRAPH TERMINOLOGY GRAPH REPRESENTATION GRAPH TRAVERSAL DEPTH-FIRST SEARCH BREADTH-FIRST SEARCH APPLICATIONS SHORTEST PATHS BELLMAN-FORD ALGORITHM DIJKSTRA’S ALGORITHM FLOYD-WARSHALL ALGORITHM DIRECTED ACYCLIC GRAPHS TOPOLOGICAL SORTING SUCCESSOR GRAPHS FINDING SUCCESSORS CYCLE DETECTION MINIMUM SPANNING TREES KRUSKAL’S ALGORITHM UNION-FIND STRUCTURE PRIM’S ALGORITHM ALGORITHM DESIGN TOPICS BIT-PARALLEL ALGORITHMS HAMMING DISTANCES COUNTING SUBGRIDS REACHABILITY IN GRAPHS AMORTIZED ANALYSIS TWO POINTERS METHOD NEAREST SMALLER ELEMENTS SLIDING WINDOW MINIMUM FINDING MINIMUM VALUES TERNARY SEARCH CONVEX FUNCTIONS MINIMIZING SUMS RANGE QUERIES QUERIES ON STATIC ARRAYS SUM QUERIES MINIMUM QUERIES TREE STRUCTURES BINARY INDEXED TREES SEGMENT TREES ADDITIONAL TECHNIQUES TREE ALGORITHMS BASIC TECHNIQUES TREE TRAVERSAL CALCULATING DIAMETERS ALL LONGEST PATHS TREE QUERIES FINDING ANCESTORS SUBTREES AND PATHS LOWEST COMMON ANCESTORS MERGING DATA STRUCTURES ADVANCED TECHNIQUES CENTROID DECOMPOSITION HEAVY-LIGHT DECOMPOSITION MATHEMATICS NUMBER THEORY PRIMES AND FACTORS SIEVE OF ERATOSTHENES EUCLID’S ALGORITHM MODULAR EXPONENTIATION EULER’S THEOREM SOLVING EQUATIONS COMBINATORICS BINOMIAL COEF?CIENTS CATALAN NUMBERS INCLUSION-EXCLUSION BURNSIDE’S LEMMA CAYLEY’S FORMULA MATRICES MATRIX OPERATIONS LINEAR RECURRENCES GRAPHS AND MATRICES GAUSSIAN ELIMINATION PROBABILITY WORKING WITH EVENTS RANDOM VARIABLES MARKOV CHAINS RANDOMIZED ALGORITHMS GAME THEORY GAME STATES NIM GAME SPRAGUE–GRUNDY THEOREM FOURIER TRANSFORM WORKING WITH POLYNOMIALS FFT ALGORITHM CALCULATING CONVOLUTIONS GUESSING FORMULAS USING OEIS FINDING POLYNOMIALS ADVANCED GRAPH ALGORITHMS STRONG CONNECTIVITY KOSARAJU’S ALGORITHM 2SAT PROBLEM COMPLETE PATHS EULERIAN PATHS HAMILTONIAN PATHS MAXIMUM FLOWS FORD–FULKERSON ALGORITHM DISJOINT PATHS MAXIMUM MATCHINGS PATH COVERS DEPTH-FIRST SEARCH TREES BICONNECTIVITY EULERIAN SUBGRAPHS MINIMUM COST FLOWS MINIMUM COST PATHS ALGORITHM MINIMUM WEIGHT MATCHINGS IMPROVING THE ALGORITHM GEOMETRY GEOMETRIC TECHNIQUES COMPLEX NUMBERS POINTS AND LINES POLYGON AREA DISTANCE FUNCTIONS INTERSECTION POINTS CLOSEST PAIR PROBLEM CONVEX HULL PROBLEM STRING ALGORITHMS BASIC TOPICS TRIE STRUCTURE STRING HASHING POLYNOMIAL HASHING COLLISIONS AND PARAMETERS Z-ALGORITHM CONSTRUCTING THE Z-ARRAY SUF?X ARRAYS PRE?X DOUBLING METHOD FINDING PATTERNS LCP ARRAYS STRING AUTOMATA REGULAR LANGUAGES PATTERN MATCHING AUTOMATA SUF?X AUTOMATA ADDITIONAL TOPICS SQUARE ROOT TECHNIQUES SUBALGORITHMS INTEGER PARTITIONS MO’S ALGORITHM SEGMENT TREES REVISITED LAZY PROPAGATION DYNAMIC TREES DATA STRUCTURES IN NODES TWO-DIMENSIONAL TREES TREAPS SPLITTING AND MERGING IMPLEMENTATION DYNAMIC PROGRAMMING OPTIMIZATION CONVEX HULL TRICK DIVIDE AND CONQUER OPTIMIZATION KNUTH’S OPTIMIZATION BACKTRACKING TECHNIQUES PRUNING THE SEARCH TREE HEURISTIC FUNCTIONS MISCELLANEOUS MEET IN THE MIDDLE COUNTING SUBSETS PARALLEL BINARY SEARCH DYNAMIC CONNECTIVITY PYTHON IN COMPETITIVE PROGRAMMING GENERATING COMBINATIONS LIST STRUCTURES HASH STRUCTURES COPING WITHOUT BINARY SEARCH TREES EXAMPLE PROBLEM RECURSIVE FUNCTIONS CACHE DECORATOR FINDING PRIMES COUNTING PERMUTATIONS PYTHON AS A TOOL GENERATING TESTS STRESS TESTING PREPARING FOR IOI CONTEST OVERVIEW HISTORY SCHEDULE TASKS MEDALS BEFORE THE CONTEST GETTING ON THE TEAM PRACTICING FLEXIBILITY CONTEST WEBSITE TECHNICAL SKILLS COMMAND LINE KEYBOARD LAYOUTS DEBUGGING TOOLS TASK INTERFACE DURING THE CONTEST PRACTICE SESSION TIME USAGE SUBTASKS FEEDBACK PSYCHOLOGICAL FACTORS FUTURE OF COMPETITIVE PROGRAMMING GENERATIVE AI WHAT WILL HAPPEN NEXT? INTRODUCTION THIS CHAPTER SHOWS WHAT COMPETITIVE PROGRAMMING IS ABOUT, OUTLINES THE CONTENTS OF THE BOOK, AND DISCUSSES ADDITIONAL LEARNING RESOURCES SECTION 11 GOES THROUGH THE ELEMENTS OF COMPETITIVE PROGRAMMING, INTRODUCES A SELECTION OF POPULAR PROGRAMMING CONTESTS, AND GIVES ADVICE ON HOW TO PRACTICE COMPETITIVE PROGRAMMING SECTION 12 DISCUSSES THE GOALS AND TOPICS OF THIS BOOK, AND BRIE?Y DESCRIBES THE CONTENTS OF EACH CHAPTER SECTION 13 PRESENTS THE CSES PROBLEM SET, WHICH CONTAINS A COLLECTION OF PRACTICE PROBLEMS SOLVING THE PROBLEMS WHILE READING THE BOOK IS A GOOD WAY TO LEARN COMPETITIVE PROGRAMMING SECTION 14 DISCUSSES OTHER BOOKS RELATED TO COMPETITIVE PROGRAMMING AND THE DESIGN OF ALGORITHMS 11 WHAT IS COMPETITIVE PROGRAMMING? COMPETITIVE PROGRAMMING COMBINES TWO TOPICS: THE DESIGN OF ALGORITHMS AND THE IMPLEMENTATION OF ALGORITHMS DESIGN OF ALGORITHMS THE CORE OF COMPETITIVE PROGRAMMING IS ABOUT INVENTING EF?CIENT ALGORITHMS THAT SOLVE WELL-DE?NED COMPUTATIONAL PROBLEMS THE DESIGN OF ALGORITHMS REQUIRES PROBLEM SOLVING AND MATHEMATICAL SKILLS OFTEN A SOLUTION TO A PROBLEM IS A COMBINATION OF WELL-KNOWN METHODS AND NEW INSIGHTS MATHEMATICS PLAYS AN IMPORTANT ROLE IN COMPETITIVE PROGRAMMING ACTUALLY, THERE ARE NO CLEAR BOUNDARIES BETWEEN ALGORITHM DESIGN AND MATHEMATICS THIS BOOK HAS BEEN WRITTEN SO THAT NOT MUCH BACKGROUND IN MATHEMATICS IS NEEDED THE APPENDIX OF THE BOOK REVIEWS SOME MATHEMATICAL CONCEPTS THAT ARE USED THROUGHOUT THE BOOK, SUCH AS SETS, LOGIC AND FUNCTIONS, AND THE APPENDIX CAN BE USED AS A REFERENCE WHEN READING THE BOOK