Resources for the Advanced Level in Certification

[admin]

Heaps (priority queue)

• https://www.cs.cmu.edu/~wlovas/15122-r11/lectures/15-priorqs.pdf
• http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdf
• http://www.geeksforgeeks.org/binary-heap/
• https://visualgo.net/en/heap
• https://www.iarcs.org.in/inoi/online-study-material/topics/heaps.php

Practice Problems

• https://www.codechef.com/JULY17/problems/IPCTRAIN Editorial: https://discuss.codechef.com/questions/105180/ipctrain-editorial
• https://www.codechef.com/problems/ANUMLA Editorial: https://discuss.codechef.com/questions/53529/anumla-editorial
• https://www.codechef.com/problems/KSUBSUM Editorial: https://discuss.codechef.com/questions/4018/ksubsum-editorial
• https://www.codechef.com/problems/RRATING Editorial: https://discuss.codechef.com/questions/1585/rrating-editorial
• https://www.codechef.com/problems/TSECJ05 Editorial: https://discuss.codechef.com/questions/103875/chef-and-his-software-tsecj05-editorial
• http://www.spoj.com/problems/WEIRDFN/
• https://www.codechef.com/problems/CAPIMOVE Editorial: https://discuss.codechef.com/questions/90266/capimove-editorial
• http://www.spoj.com/problems/RMID2/
• http://www.spoj.com/problems/LAZYPROG/
• http://www.spoj.com/problems/EXPEDI/
• http://acm.timus.ru/problem.aspx?space=1&num=1306
• https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=1221
• https://www.codechef.com/problems/MOSTDIST, Editorial: https://discuss.codechef.com/questions/56239/mostdist-editorial

---

Disjoint Set Union

• https://www.topcoder.com/community/data-science/data-science-tutorials/disjoint-set-data-structures/
• https://sites.fas.harvard.edu/~libcs124/CS/lec6.pdf
• http://web.cs.ucdavis.edu/~amenta/w10/trevisanNotes.pdf
• https://visualgo.net/en/ufds

Practice Problems

• https://www.codechef.com/problems/GALACTIK Editorial: https://discuss.codechef.com/questions/18004/galactik-editorial
• https://www.codechef.com/problems/DISHOWN Editorial: https://discuss.codechef.com/questions/47241/dishown-editorial
• https://www.codechef.com/problems/JABO Editorial: https://discuss.codechef.com/questions/3710/jabo-editorial
• https://www.codechef.com/problems/PARITREE Editorial: https://discuss.codechef.com/questions/79920/paritree-editorial
• https://www.codechef.com/problems/FILLMTR Editorial: https://discuss.codechef.com/questions/109357/fillmtr-editorial
• http://codeforces.com/problemset/problem/547/B
• http://codeforces.com/contest/151/problem/D
• https://www.codechef.com/problems/SETELE Editorial: https://discuss.codechef.com/questions/87909/setele-editorial
• https://www.codechef.com/problems/MAZE Editorial: https://discuss.codechef.com/questions/81591/maze-editorial
• https://www.codechef.com/problems/MAGICSTR Editorial: https://discuss.codechef.com/questions/77347/magical-strings-editorial
• https://www.codechef.com/problems/MTRWY Editorial: https://discuss.codechef.com/questions/66031/mtrwy-editorial
• https://www.codechef.com/problems/BIGOF01 Editorial: https://discuss.codechef.com/questions/68454/bigof01-editorial
• https://www.codechef.com/problems/FIRESC Editorial: https://discuss.codechef.com/questions/7269/firesc-editorial

---

Segment Trees

• http://wcipeg.com/wiki/Segment_tree
• https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Segment_Trees
• https://kartikkukreja.wordpress.com/2014/11/09/a-simple-approach-to-segment-trees/
• https://visualgo.net/en/segmenttree
• https://www.iarcs.org.in/inoi/online-study-material/topics/segment-tree.php

Practice Problems

• http://www.spoj.pl/problems/GSS1/
• http://www.spoj.pl/problems/GSS2/
• http://codeforces.com/blog/entry/15890 (Expert Level)
• http://www.spoj.pl/problems/IOPC1207/
• http://www.spoj.com/problems/ORDERSET/
• http://www.spoj.com/problems/HELPR2D2/
• http://www.spoj.com/problems/ANDROUND/
• http://www.spoj.com/problems/HEAPULM/
• http://www.spoj.com/problems/NICEDAY/
• http://www.spoj.com/problems/YODANESS/
• http://www.spoj.pl/problems/DQUERY/
• http://www.spoj.pl/problems/KQUERY/
• http://www.spoj.pl/problems/FREQUENT/
• http://www.spoj.pl/problems/GSS3/
• http://www.spoj.pl/problems/GSS4
• http://www.spoj.pl/problems/GSS5/
• http://www.spoj.pl/problems/KGSS/
• http://www.spoj.pl/problems/HELPR2D2/
• http://www.spoj.pl/problems/BRCKTS/
• http://www.spoj.pl/problems/CTRICK/
• http://www.spoj.pl/problems/MATSUM/
• http://www.spoj.pl/problems/RATING/
• http://www.spoj.pl/problems/RRSCHED/
• http://www.spoj.pl/problems/SUPPER/
• http://www.spoj.pl/problems/ORDERS/
• http://www.codechef.com/problems/LEBOBBLE
• http://www.codechef.com/problems/QUERY
• http://www.spoj.com/problems/TEMPLEQ
• http://www.spoj.com/problems/DISUBSTR/
• http://www.spoj.pl/problems/QTREE/
• http://www.spoj.pl/problems/QTREE2/
• http://www.spoj.pl/problems/QTREE3/
• http://www.spoj.com/problems/QTREE4/
• http://www.spoj.com/problems/QTREE5/

Problems on segment tree with lazy propogation

• http://www.spoj.com/problems/HORRIBLE (must do basic lazy propogation problem)
• http://www.spoj.com/problems/LITE/ (a nice lazy propogation problem)
• http://www.spoj.com/problems/MULTQ3/ (another nice lazy propogation problem)
• https://www.codechef.com/problems/CHEFD
• https://www.codechef.com/problems/FUNAGP (a difficult lazy propogation problem.)
• http://www.spoj.com/problems/RPAR/ (a difficult and nice lazy propogation)
• https://www.codechef.com/problems/ADDMUL
• http://www.spoj.com/problems/SEGSQRSS/ (a difficult lazy propogation problem)
• http://www.spoj.com/problems/KGSS/
• http://codeforces.com/contest/52/problem/C
• http://codeforces.com/contest/145/problem/E (must do hard problem on lazy propogation)
• http://codeforces.com/contest/558/problem/E
• http://codeforces.com/contest/446/problem/C (important problem to do, introduces some nice properties over lazy propogation)
• http://codeforces.com/contest/438/problem/D
• http://codeforces.com/contest/121/problem/E

---

Binary Index Tree (Fenwick tree)

• https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/
• https://www.iarcs.org.in/inoi/online-study-material/topics/binary-index-tree.php
• https://visualgo.net/en/fenwicktree

Practice problems
Please solve the problems mentioned in the above segment tree practice problems section. Note that usually, it’s difficult to do range updates in binary indexed trees. Mostly, it is used for for range query and point update. However, you can check the following article for checking how some simple specific kind of range updates can be peformed on binary indexed tree (http://petr-mitrichev.blogspot.in/2013/05/fenwick-tree-range-updates.html). Note that range updates on BIT is not a part of the syllabus.

• http://www.spoj.com/problems/INVCNT/
• http://www.spoj.com/problems/TRIPINV/

---

Trees (traversals)

• https://www.slideshare.net/ecomputernotes/traversal-of-a-binary-tree-10682319
• https://www.iarcs.org.in/inoi/online-study-material/topics/dp-trees.php
• https://people.eecs.berkeley.edu/~vazirani/s99cs170/notes/dynamic2.pdf

Practice Problems

• http://www.spoj.com/problems/TREEORD/

---

Finding Lowest Common Ancestors (O(log N) solution where N is number of nodes).

• https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/

---

Depth First Search, Breadth First Search (Finding connected components and transitive closures).

• http://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/
• http://www.geeksforgeeks.org/transitive-closure-of-a-graph/
• http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/
• https://www.iarcs.org.in/inoi/online-study-material/topics/graphs.php
• https://visualgo.net/en/dfsbfs
• https://sites.fas.harvard.edu/~libcs124/CS/lec4.pdf

Practice Problems

• https://www.codechef.com/problems/FIRESC, https://discuss.codechef.com/questions/7269/firesc-editorial
• http://www.spoj.com/problems/BUGLIFE/
• http://www.spoj.com/problems/CAM5/
• http://www.spoj.com/problems/GCPC11J/
• http://www.spoj.com/problems/KFSTB/
• http://www.spoj.com/problems/PT07Y/
• http://www.spoj.com/problems/PT07Z/
• http://www.spoj.com/problems/LABYR1/
• http://www.spoj.com/problems/PARADOX/
• http://www.spoj.com/problems/PPATH/ (must do bfs problem)
• http://www.spoj.com/problems/ELEVTRBL/ (bfs)
• http://www.spoj.com/problems/QUEEN/ (bfs)
• http://www.spoj.com/problems/SSORT/ (cycles in a graph)
• http://www.spoj.com/problems/ROBOTGRI/ (bfs)

---

Shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall)

• http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
• https://www.iarcs.org.in/inoi/online-study-material/topics/shortest-paths.php
• https://visualgo.net/en/sssp

Practice Problems

• https://www.codechef.com/problems/DIGJUMP Editorial: https://discuss.codechef.com/questions/44800/digjump-editorial
• https://www.codechef.com/AMR14ROS/problems/AMR14B Editorial: https://discuss.codechef.com/questions/61701/amr14b-editorial
• https://www.codechef.com/problems/INSQ15_F Editorial: https://discuss.codechef.com/questions/74790/insq15_f-editorial
• https://www.codechef.com/problems/SPSHORT Editorial: https://discuss.codechef.com/questions/64224/spshort-editorial (slightly dificult dijkstra’s problem.)
• https://www.codechef.com/problems/RIVPILE Editorial: https://discuss.codechef.com/questions/18188/rivpile-editorial
• http://www.spoj.com/problems/SHPATH/
• http://www.spoj.com/problems/TRAFFICN/
• http://www.spoj.com/problems/SAMER08A/
• http://www.spoj.com/problems/MICEMAZE/
• http://www.spoj.com/problems/TRVCOST/
• https://www.codechef.com/problems/PAIRCLST Editorial: https://discuss.codechef.com/questions/79923/pairclst-editorial

---

Bellman Ford Algorithm

• http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/
• https://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm/

**Practice Problems

• https://community.topcoder.com/stat?c=problem_statement&pm=10580
• http://codeforces.com/problemset/problem/346/D
• http://www.spoj.com/problems/ARBITRAG/ (Floyd Warshall)
• http://community.topcoder.com/stat?c=problem_statement&pm=10736 (Floyd Warshall)

---

Minimum spanning tree (Prim and Kruskal algorithms)

• http://algs4.cs.princeton.edu/lectures/43MinimumSpanningTrees.pdf
• https://www.iarcs.org.in/inoi/online-study-material/topics/spanning-trees.php
• https://visualgo.net/en/mst

Problems

• http://www.spoj.com/problems/MST/
• http://www.spoj.com/problems/NITTROAD/
• http://www.spoj.com/problems/BLINNET/
• http://www.spoj.com/problems/CSTREET/
• http://www.spoj.com/problems/HIGHWAYS/
• http://www.spoj.com/problems/IITWPC4I/
• https://www.codechef.com/problems/MSTQS https://discuss.codechef.com/questions/89653/mstqs-editorial
• https://www.codechef.com/problems/CHEFGAME https://discuss.codechef.com/questions/8119/chefgame-editorial
• https://www.codechef.com/problems/GALACTIK https://discuss.codechef.com/questions/18004/galactik-editorial
• https://www.codechef.com/problems/GOOGOL03 https://discuss.codechef.com/questions/70187/googol03-editorial
• http://www.spoj.com/problems/KOICOST/

---

Biconnectivity in undirected graphs (bridges, articulation points)

• https://e-maxx-eng.appspot.com/graph/bridge-searching.html
• https://www.iarcs.org.in/inoi/online-study-material/topics/articulation-points.php
• http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=fb1f19a9be617037cb419c5d454b184bead47e243

Practice Problems

• https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=251
• https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=722
• https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1140
• http://acm.tju.edu.cn/toj/showp1026.html
• http://www.spoj.com/problems/EC_P/
• http://www.spoj.com/problems/SUBMERGE/
• http://www.spoj.com/problems/POLQUERY/
• http://codeforces.com/problemset/problem/193/A

---

Strongly connected components in directed graphs

• https://www.iarcs.org.in/inoi/online-study-material/topics/scc.php

• http://theory.stanford.edu/~tim/w11/l/scc.pdf

• http://www.spoj.com/problems/ANTTT/

• http://www.spoj.com/problems/CAPCITY/

• http://www.spoj.com/problems/SUBMERGE/

• https://www.codechef.com/problems/MCO16405 Editorial: https://discuss.codechef.com/questions/91585/mco16405-editorial

• http://www.spoj.com/problems/BOTTOM/

• http://www.spoj.com/problems/BREAK/

• https://community.topcoder.com/stat?c=problem_statement&pm=8488&rd=11125

---

Topological Sorting

• http://www.geeksforgeeks.org/topological-sorting/

Practice Problems

• http://www.spoj.com/problems/TOPOSORT/
• http://codeforces.com/contest/510/problem/C
• https://www.codechef.com/problems/RRDAG Editorial: https://discuss.codechef.com/questions/47983/rrdag-editorial
• http://www.spoj.com/problems/RPLA/
• https://www.codechef.com/problems/CL16BF (topological sort with dp), Editorial: https://discuss.codechef.com/questions/85994/cl16bf-editorial
• http://www.spoj.com/problems/MAKETREE/

---

Euler path, tour/cycle.

• https://www.math.ku.edu/~jmartin/courses/math105-F11/Lectures/chapter5-part2.pdf

Practice Problems

• http://www.spoj.com/problems/WORDS1/
• https://www.codechef.com/problems/CHEFPASS Editorial: https://discuss.codechef.com/questions/2096/chefpass-editorial
• https://www.codechef.com/problems/TOURISTS Editorial: https://discuss.codechef.com/questions/90320/tourists-editorial
• http://codeforces.com/contest/500/problem/D
• http://codeforces.com/contest/475/problem/B
• https://www.codechef.com/problems/PEOPLOVE
• http://codeforces.com/contest/508/problem/D
• http://codeforces.com/contest/723/problem/E
• http://www.spoj.com/problems/GCPC11C/
• http://www.spoj.com/problems/MAKETREE/

---

Modular arithmetic including division, inverse

• https://discuss.codechef.com/questions/20451/a-tutorial-on-fast-modulo-multiplication-exponential-squaring
• https://discuss.codechef.com/questions/3869/best-known-algos-for-calculating-ncr-m (only for expert level)

---

Amortized Analysis

• https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/lecture-notes/MIT6_046JS12_lec11.pdf
• https://en.wikipedia.org/wiki/Amortized_analysis
• http://www.iiitdm.ac.in/old/Faculty_Teaching/Sadagopan/pdf/ADSA/amortized-analysis.pdf

---

Divide and Conquer

• http://www.cs.cmu.edu/afs/cs/academic/class/15210-s12/www/lectures/lecture02.pdf
• http://www.geeksforgeeks.org/category/divide-and-conquer/

Practice Problems

• https://www.codechef.com/problems/MRGSRT Editorial: https://discuss.codechef.com/questions/70773/mrgsrt-editorial
• http://www.spoj.com/problems/HISTOGRA/
• https://www.codechef.com/problems/TASTYD https://discuss.codechef.com/questions/15957/tastyd-editorial
• https://www.codechef.com/problems/RESTPERM https://discuss.codechef.com/questions/86763/restperm-editorial
• https://www.codechef.com/problems/ACM14KP1 https://discuss.codechef.com/questions/56980/acm14kp1-editorial

---

Advanced Dynamic Programming problems (excluding the dp optimizations which are added in expert level, Please go through the basic DP resources and problems mentioned in foundation level resource.)

• http://apps.topcoder.com/forums/?module=Thread&threadID=697369&start=0
• http://apps.topcoder.com/forums/?module=Thread&threadID=700080&start=0
• http://apps.topcoder.com/forums/?module=Thread&threadID=697925&start=0
• http://codeforces.com/blog/entry/337

Problems for Advanced DP

• http://www.spoj.com/problems/HIST2/ (dp bitmask)
• http://www.spoj.com/problems/LAZYCOWS/ (dp bitmask)
• http://www.spoj.com/problems/TRSTAGE/ (dp bitmask)
• http://www.spoj.pl/problems/MARTIAN/
• http://www.spoj.pl/problems/SQRBR/
• http://www.spoj.pl/problems/ACMAKER/
• http://www.spoj.pl/problems/AEROLITE/
• https://www.spoj.pl/problems/BACKPACK/
• http://www.spoj.pl/problems/COURIER/
• http://www.spoj.pl/problems/DP/
• http://www.spoj.pl/problems/EDIST/
• http://www.spoj.pl/problems/KRECT/
• http://www.spoj.pl/problems/GNY07H/
• http://www.spoj.pl/problems/LISA/
• http://www.spoj.pl/problems/MINUS/
• http://www.spoj.pl/problems/NAJKRACI/
• http://www.spoj.pl/problems/PHIDIAS/
• http://www.spoj.pl/problems/PIGBANK/
• http://www.spoj.pl/problems/PT07X/
• http://www.spoj.pl/problems/VOCV/
• http://www.spoj.pl/problems/TOURIST/
• http://www.spoj.pl/problems/MKBUDGET
• http://www.spoj.pl/problems/MMAXPER
• http://www.spoj.pl/problems/ANARC07G
• http://www.spoj.pl/problems/MENU
• http://www.spoj.com/problems/RENT/ (dp with segment tree/BIT)
• http://www.spoj.com/problems/INCSEQ/ (dp with segment tree/BIT)
• http://www.spoj.com/problems/INCDSEQ/ (dp with segment tree/BIT)
• You can solve some advanced problems from http://codeforces.com/blog/entry/325

---

Sieve of Eratosthenes

• https://discuss.codechef.com/questions/54846/please-proofread-the-atricle-for-tutorial-section-on-sieve-methods

Practice Problems

• http://www.spoj.com/problems/TDKPRIME/
• http://www.spoj.com/problems/TDPRIMES/
• http://www.spoj.com/problems/ODDDIV/ (sieve + binary search)
• http://www.spoj.com/problems/NDIVPHI/ (\mathcal{O}(\sqrt{N}) prime testing algorithm)
• http://www.spoj.com/problems/DIV/ (divisor sieve)
• https://www.codechef.com/problems/LEVY Editorial: https://discuss.codechef.com/questions/8115/levy-editorial
• https://www.codechef.com/problems/PRETNUM Editorial: https://discuss.codechef.com/questions/28909/pretnum-editorial
• https://www.codechef.com/problems/KPRIME Editorial: https://discuss.codechef.com/questions/17915/kprime-editorial
• https://www.codechef.com/problems/DIVMAC Editorial: https://discuss.codechef.com/questions/84917/divmac-editorial-unofficial (segment tree with sieve)
• https://www.codechef.com/problems/PPERM Ediotorial: https://discuss.codechef.com/questions/2555/pperm-editorial (a bit advanced sieve application)