الگوریتمستان

نوشته‌های یک علاقه‌مند به حوزه‌های برنامه‌نویسی، الگوریتم، حل مسئله و ریاضیات دوست داشتنی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
کتاب Competetive Programming - الگوریتمستان
الگوریتمستان

ویراست سوم کتاب برنامه‌نویسی رقابتی با نام کامل Competitive Programming 3: The New Lower Bound of Programming Contests با تلاش Steven Halim و Felix Halim از مربیان تیم‌های برنامه‌نویسی ACM-ICPC سنگاپور تالیف و  در سال ۲۰۱۳ منتشر شده است که امروزه به عنوان یکی از منابع مناسب برای آمادگی تیم‌های شرکت‌کننده در مسابقات برنامه‌نویسی الگوریتمی بویژه مسابقات برنامه‌نویسی ACM-ICPC توصیه می‌شود.

این کتاب شامل نکات تکنیکی برنامه‌نویسی در مسابقات ACM-ICPC و همینطور معرفی ساختمان داده‌ها و الگوریتم‌های پر کاربرد در ۹ فصل با جزئیات زیر است.

1 Introduction

    1.1 Competitive Programming

    1.2 Tips to be Competitive

        1.2.1 Tip 1: Type Code Faster!

        1.2.2 Tip 2: Quickly Identify Problem Types

        1.2.3 Tip 3: Do Algorithm Analysis

        1.2.4 Tip 4: Master Programming Languages

        1.2.5 Tip 5: Master the Art of Testing Code

        1.2.6 Tip 6: Practice andMore Practice

        1.2.7 Tip 7: TeamWork (for ICPC)

    1.3 Getting Started: The Easy Problems

        1.3.1 Anatomy of a Programming Contest Problem

        1.3.2 Typical Input/Output Routines

        1.3.3 Time to Start the Journey

    1.4 The Ad Hoc Problems

2 Data Structures and Libraries

    2.1 Overview and Motivation

    2.2 Linear DS with Built-in Libraries

    2.3 Non-Linear DS with Built-in Libraries

    2.4 Data Structures with Our Own Libraries

        2.4.1 Graph

        2.4.2 Union-Find Disjoint Sets

        2.4.3 Segment Tree

        2.4.4 Binary Indexed (Fenwick) Tree

3 Problem Solving Paradigms

    3.1 Overview and Motivation

    3.2 Complete Search

        3.2.1 Iterative Complete Search

        3.2.2 Recursive Complete Search3.2.3 Tips

    3.3 Divide and Conquer

        3.3.1 Interesting Usages of Binary Search

    3.4 Greedy

        3.4.1 Examples

    3.5 Dynamic Programming

        3.5.1 DP Illustration

        3.5.2 Classical Examples

        3.5.3 Non-Classical Examples

4 Graph

    4.1 Overview and Motivation

    4.2 Graph Traversal

        4.2.1 Depth First Search (DFS)

        4.2.2 Breadth First Search (BFS)

        4.2.3 Finding Connected Components (Undirected Graph)

        4.2.4 Flood Fill - Labeling/Coloring the Connected Components

        4.2.5 Topological Sort (Directed Acyclic Graph)

        4.2.6 Bipartite Graph Check

        4.2.7 Graph Edges Property Check via DFS Spanning Tree

        4.2.8 Finding Articulation Points and Bridges (Undirected Graph)

        4.2.9 Finding Strongly Connected Components (Directed Graph)

    4.3 Minimum Spanning Tree

        4.3.1 Overview and Motivation

        4.3.2 Kruskals Algorithm

        4.3.3 Prims Algorithm

        4.3.4 Other Applications

    4.4 Single-Source Shortest Paths

        4.4.1 Overview and Motivation

        4.4.2 SSSP on Unweighted Graph

        4.4.3 SSSP on Weighted Graph

        4.4.4 SSSP on Graph with Negative Weight Cycle

    4.5 All-Pairs Shortest Paths

        4.5.1 Overview and Motivation

        4.5.2 Explanation of Floyd Warshalls DP Solution

        4.5.3 Other Applications

    4.6 Network Flow

        4.6.1 Overview and Motivation

        4.6.2 Ford Fulkersons Method

        4.6.3 Edmonds Karps Algorithm

        4.6.4 Flow Graph Modeling - Part 1

        4.6.5 Other Applications

        4.6.6 Flow Graph Modeling - Part 2

    4.7 Special Graphs

        4.7.1 Directed Acyclic Graph

        4.7.2 Tree

        4.7.3 Eulerian Graph

        4.7.4 Bipartite Graph

5 Mathematics

    5.1 Overview and Motivation

    5.2 Ad Hoc Mathematics Problems

    5.3 Java BigInteger Class

        5.3.1 Basic Features

        5.3.2 Bonus Features

    5.4 Combinatorics

        5.4.1 Fibonacci Numbers

        5.4.2 Binomial Coefficients

        5.4.3 Catalan Numbers

        5.4.4 Remarks about Combinatorics in Programming Contests

    5.5 Number Theory

        5.5.1 Prime Numbers

        5.5.2 Greatest Common Divisor & Least Common Multiple

        5.5.3 Factorial

        5.5.4 Finding Prime Factors with Optimized Trial Divisions

        5.5.5 Working with Prime Factors

        5.5.6 Functions Involving Prime Factors

        5.5.7 Modified Sieve

        5.5.8 Modulo Arithmetic

        5.5.9 Extended Euclid: Solving Linear Diophantine Equation

        5.5.10 Remarks about Number Theory in Programming Contests

    5.6 Probability Theory

    5.7 Cycle-Finding

        5.7.1 Solution(s) using Efficient Data Structure

        5.7.2 Floyds Cycle-Finding Algorithm

    5.8 Game Theory

        5.8.1 Decision Tree

        5.8.2 Mathematical Insights to Speed-up the Solution

    5.8.3 Nim Game

6 String Processing

    6.1 Overview and Motivation

    6.2 Basic String Processing Skills

    6.3 Ad Hoc String Processing Problems

    6.4 String Matching

        6.4.1 Library Solutions

        6.4.2 Knuth-Morris-Pratts (KMP) Algorithm

        6.4.3 StringMatching in a 2D Grid

    6.5 String Processing with Dynamic Programming

        6.5.1 String Alignment (Edit Distance)

        6.5.2 Longest Common Subsequence

        6.5.3 Non Classical String Processing with DP

    6.6 Suffix Trie/Tree/Array

        6.6.1 Suffix Trie and Applications

        6.6.2 Suffix Tree

        6.6.3 Applications of Suffix Tree

        6.6.4 Suffix Array

        6.6.5 Applications of Suffix Array

7 (Computational) Geometry

    7.1 Overview and Motivation

    7.2 Basic Geometry Objects with Libraries

        7.2.1 0D Objects: Points

        7.2.2 1D Objects: Lines

        7.2.3 2D Objects: Circles

        7.2.4 2D Objects: Triangles

        7.2.5 2D Objects: Quadrilaterals

    7.3 Algorithmon Polygon with Libraries

        7.3.1 Polygon Representation

        7.3.2 Perimeter of a Polygon

        7.3.3 Area of a Polygon

        7.3.4 Checking if a Polygon is Convex

        7.3.5 Checking if a Point is Inside a Polygon

        7.3.6 Cutting Polygon with a Straight Line

        7.3.7 Finding the Convex Hull of a Set of Points

    7.4 Solution to Non-Starred Exercises

8 More Advanced Topics

    8.1 Overview and Motivation

    8.2 More Advanced Search Techniques

        8.2.1 Backtracking with Bitmask

        8.2.2 Backtracking with Heavy Pruning

        8.2.3 State-Space Search with BFS or Dijkstras

        8.2.4 Meet in theMiddle (Bidirectional Search)

        8.2.5 Informed Search: A* and IDA*

    8.3 More Advanced DP Techniques

        8.3.1 DP with Bitmask

        8.3.2 Compilation of Common (DP) Parameters

        8.3.3 Handling Negative Parameter Values with Offset Technique

        8.3.4 MLE? Consider Using Balanced BST asMemo Table

        8.3.5 MLE/TLE? Use Better State Representation

        8.3.6 MLE/TLE? Drop One Parameter, Recover It fromOthers

    8.4 Problem Decomposition

        8.4.1 Two Components: Binary Search the Answer and Other

        8.4.2 Two Components: Involving 1D Static RSQ/RMQ

        8.4.3 Two Components: Graph Preprocessing and DP

        8.4.4 Two Components: Involving Graph

        8.4.5 Two Components: InvolvingMathematics

        8.4.6 Two Components: Complete Search and Geometry.

        8.4.7 Two Components: Involving Efficient Data Structure

        8.4.8 Three Components

9 Rare Topics

    9.1 2-SAT Problem

    9.2 Art Gallery Problem

    9.3 Bitonic Traveling Salesman Problem

    9.4 Bracket Matching

    9.5 Chinese Postman Problem

    9.6 Closest Pair

    9.7 Dinics Algorithm

    9.8 Formulas or Theorems

    9.9 Gaussian Elimination Algorithm

    9.10 GraphMatching

    9.11 Great-Circle Distance

    9.12 Hopcroft Karps Algorithm

    9.13 Independent and Edge-Disjoint Paths

    9.14 Inversion Index

    9.15 Josephus Problem

    9.16 Knight Moves

    9.17 Kosarajus Algorithm

    9.18 Lowest Common Ancestor

    9.19 Magic Square Construction (Odd Size

    9.20 Matrix Chain Multiplication

    9.21 Matrix Power

    9.22 MaxWeighted Independent Set

    9.23 Min Cost (Max) Flow

    9.24 Min Path Cover on DAG

    9.25 Pancake Sorting

    9.26 Pollards rho Integer Factoring Algorithm

    9.27 Postfix Calculator and Conversion

    9.28 Roman Numerals

    9.29 Selection Problem

    9.30 Shortest Path Faster Algorithm

    9.31 Sliding Window

    9.32 Sorting in Linear Time

    9.33 Sparse Table Data Structure

    9.34 Tower of Hanoi

زبان برنامه‌نویسی استفاده شده در کتاب ++C است و از مجموعه سوالات UVA Online Judge و همینطور المپیاد کامپیوتر دانش‌آموزی برای آموزش یا تمرین استفاده‌ی فراوانی شده که در انتهای هر فصل پاسخ برخی از تمرین‌ها آمده است. همچنین می‌توان درستی پاسخ تمرین‌های کتاب را از طریق وب‌سایت uHunt بررسی کرد.

نسخه‌ی الکترونیکی ویراست سوم این کتاب از این پیوند قابل دریافت است که اصلاحات آن برای اعمال در ویراست چهارم در این پیوند آمده است.

مسعود اقدسی‌فام

مسعود اقدسی‌فام هستم.

یک معلم علاقه‌مند به تحقیق، تدریس و نوشتن در حوزه‌های برنامه‌نویسی، الگوریتم و حل مسئله :)

اشتراک‌گذاری نوشته
algs.ir/spcp3     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram     ارسال با WhatsApp
امتیاز به نوشته
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک:

وب‌سایت:

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14


• یک دوست
پنجشنبه، ۱۶ اردیبهشت ماه ۱۴۰۰، ساعت ۱۲:۰۰

عالی بود 01


• رضا جودی
جمعه، ۲۸ آبان ماه ۱۴۰۰، ساعت ۰۹:۱۹

0108


کمی آمار
  • عمر نوشته:  ۸۱۰ روز
  • تعداد امتیاز ثبت شده:  ۵ امتیاز
  • میانگین امتیازها:  ۵.۰۰ از ۵.۰۰
  • بازدید امروز:  ۶ بازدید
  • بازدید ۲۴ ساعت گذشته:  ۸ بازدید
  • بازدید ۷ روز گذشته:  ۷۵ بازدید
  • بازدید ۳۰ روز گذشته:  ۳۷۸ بازدید
  • بازدید ۱ سال گذشته: ۳۴۸۷ بازدید
  • کل بازدیدها: ۷۰۰۳ بازدید
برچسب‌ها
#آمادگی مسابقه برنامه‌نویسی  #آموزش الگوریتم  #مسئله‌های الگوریتمی  #برنامه‌نویسی ++C  #الگوریتم  #نمونه سوالات مسابقه برنامه‌نویسی  #حل مسئله‌‌ی الگوریتمی  #برنامه‌نویسی  #منبع آموزشی  #حل سوالات مسابقات برنامه‌نویسی  #الگوریتم‌های تقسیم و غلبه  #نمونه سوال مسابقه ACM  #آموزش ساختمان داده‌ها  #الگوریتم‌های بازگشتی  #الگوریتم‌های برنامه‌نویسی پویا  #کتاب الکترونیکی  #محاسبات ریاضی  #تکنیک‌های طراحی الگوریتم  #گراف  #دانلود کتاب  #حل سوالات ACM-ICPC  #الگوریتم‌های مرتب‌سازی  #سوالات مسابقات ACM-ICPC  #Python  #پیمایش گراف  #کتاب مسابقات برنامه‌نویسی  #درخت‌ها  #سوالات UVa Online Judge  #الگوریتم‌های گراف  #حل سوالات UVa Online Judge  #الگوریتم‌های مسیریابی  #الگوریتم‌های حریصانه  #ساختمان داده  #جستجوی اول سطح  #ماتریس  #الگوریتم‌های کوتاهترین مسیر  #درخت پوشا  #الگوریتم دایکسترا  #ویدئوی آموزشی  #معرفی وب‌سایت  #الگوریتم فلوید-وارشال  #مسئله‌ی کوله‌پشتی  #جستجوی اول عمق  #کتابخانه قالب استاندارد ++C  #صف  #سوالات مسابقات برنامه‌نویسی بیان  #الگوریتم‌های عقبگرد  #حل سوالات Timus Online Judge