Sunday, 23 June 2013

700 problems to understand you complete algorithmic programming.

1. Segment Tree:

To Read :
http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static
http://ronzii.wordpress.com/2011/07/08/segment-tree-tutorial/
http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html
http://olympiad.cs.uct.ac.za/presentations/camp3_2007/interval_trees.pdf
http://codeforces.com/blog/entry/6281
http://apps.topcoder.com/forums/?module=Thread&threadID=651820&start=0&mc=2#1146133
http://www.algorithmist.com/index.php/Segmented_Trees
http://letuskode.blogspot.in/2013/01/segtrees.html
http://wcipeg.com/wiki/Heavy-light_decomposition
http://discuss.codechef.com/questions/5960/rnestescape-from-the-mines
http://ideone.com/dPS5N (Heavy Light implementation).
https://sites.google.com/site/indy256/algo/heavy_light (Heavy Light implementation).

Problems:

http://www.spoj.com/problems/GSS1
http://www.spoj.com/problems/GSS2
http://www.spoj.com/problems/GSS3
http://www.spoj.com/problems/GSS4
http://www.spoj.com/problems/GSS5
http://www.spoj.com/problems/GSS6
http://www.spoj.com/problems/GSS7
http://www.spoj.com/problems/ANDROUND/
http://www.spoj.com/problems/BRCKTS/
http://www.spoj.com/problems/DQUERY/
http://www.spoj.com/problems/FREQUENT/
http://www.spoj.com/problems/HEAPULM/
http://www.spoj.com/problems/HELPR2D2/
http://www.spoj.com/problems/KGSS/
http://www.spoj.com/problems/MKTHNUM/
http://www.spoj.com/problems/NICEDAY/
http://www.spoj.com/problems/YODANESS/
http://www.spoj.pl/problems/INCSEQ/
http://www.spoj.pl/problems/INCDSEQ/
http://www.spoj.pl/problems/KQUERY/
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/
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.spoj.com/problems/MULTQ3/
http://www.spoj.com/problems/RPAR/
http://www.spoj.com/problems/PATULJCI/
http://www.spoj.com/problems/DISUBSTR/
http://www.spoj.com/problems/HORRIBLE
http://www.spoj.pl/problems/IOPC1207/
http://www.spoj.com/problems/SEGSQRSS/
http://www.spoj.com/problems/ORDERSET/
http://www.spoj.com/problems/HELPR2D2/
http://www.spoj.com/problems/TEMPLEQ
http://www.codechef.com/problems/QTREE
http://www.codechef.com/problems/LEBOBBLE
http://www.codechef.com/problems/DGCD
http://www.codechef.com/problems/QUERY
http://codeforces.com/problemset/problem/280/D
http://codeforces.com/problemset/problem/117/E
http://codeforces.com/problemset/problem/167/D
http://codeforces.com/problemset/problem/266/E
http://codeforces.com/problemset/problem/145/E
http://codeforces.com/problemset/problem/226/E
http://codeforces.com/problemset/problem/311/C
http://codeforces.com/problemset/problem/276/E
http://codeforces.com/problemset/problem/221/D
http://codeforces.com/problemset/problem/174/C
http://codeforces.com/problemset/problem/301/D
http://codeforces.com/problemset/problem/61/E
http://codeforces.com/problemset/problem/103/D
http://codeforces.com/problemset/problem/165/D
http://codeforces.com/problemset/problem/52/C
http://codeforces.com/problemset/problem/85/D
http://codeforces.com/problemset/problem/242/E
http://codeforces.com/problemset/problem/111/B
http://codeforces.com/problemset/problem/220/B
http://codeforces.com/problemset/problem/195/E
http://codeforces.com/problemset/problem/219/E
http://codeforces.com/problemset/problem/281/D
http://codeforces.com/problemset/problem/121/E
http://codeforces.com/problemset/problem/86/D
http://codeforces.com/problemset/problem/182/C
http://codeforces.com/problemset/problem/19/D
http://codeforces.com/problemset/problem/258/E
http://codeforces.com/problemset/problem/190/E
http://codeforces.com/problemset/problem/295/E
http://codeforces.com/problemset/problem/160/E
http://codeforces.com/problemset/problem/163/E
http://codeforces.com/problemset/problem/192/E
http://codeforces.com/problemset/problem/316/E3
http://codeforces.com/problemset/problem/280/E
http://codeforces.com/problemset/problem/238/D

SRM 310 -> Floating Median
http://acm.pku.edu.cn/JudgeOnline/problem?id=1986
http://acm.pku.edu.cn/JudgeOnline/problem?id=2374
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2045
http://acm.pku.edu.cn/JudgeOnline/problem?id=2763
http://www.spoj.pl/problems/QTREE2/
http://acm.uva.es/p/v109/10938.html
http://acm.sgu.ru/problem.php?contest=0&problem=155

2. BIT (also called Fenwick Tree).
Mostly problems of BIT can also be solved by Segment Tree. But it is shorted and faster to code. Hence it is sometimes very easy.

To Read:

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
http://p--np.blogspot.in/2011/04/binary-indexed-tree.html
http://www.algorithmist.com/index.php/Fenwick_tree
http://en.wikipedia.org/wiki/Fenwick_tree
http://pavelsimo.blogspot.in/2012/09/counting-inversions-in-array-using-BIT.html
http://petr-mitrichev.blogspot.in/2013/05/fenwick-tree-range-updates.html

Problems:
http://community.topcoder.com/stat?c=problem_statement&pm=10976
And try some earlier problems which are solvable by this data structure to practice more.
Try mobile problem of IOI. 2D BIT.

3. Dynamic Programming (DP):

To Read:

http://en.wikipedia.org/wiki/Edit_distance
http://www.codechef.com/wiki/tutorial-dynamic-programming

Problems:

SGU Problems :  269273304317356396445447458489494
http://www.spoj.com/problems/SAMER08D/
http://acm.sgu.ru/problem.php?contest=0&problem=199
http://www.spoj.com/problems/MDOLLS/
http://www.spoj.com/problems/MSTICK/
http://www.spoj.com/problems/MCARDS/
http://www.spoj.com/problems/MIXTURES/
http://www.spoj.com/problems/SCUBADIV/
http://z-trening.com/tasks.php?show_task=5000000355
http://z-trening.com/tasks.php?show_task=5000000286
http://z-trening.com/tasks.php?show_task=5000000465
http://z-trening.com/tasks.php?show_task=5000000310
http://z-trening.com/tasks.php?show_task=5000000778
http://z-trening.com/tasks.php?show_task=5000000363
http://z-trening.com/tasks.php?show_task=5000001024
http://www.spoj.com/problems/VOCV/
http://www.spoj.com/problems/PT07F/
http://www.spoj.com/problems/PT07X/
http://z-trening.com/tasks.php?show_task=5000000070
http://z-trening.com/tasks.php?show_task=5000000569
http://z-trening.com/tasks.php?show_task=5000000441
http://z-trening.com/tasks.php?show_task=5000000050
http://www.spoj.com/problems/RENT/
http://www.spoj.com/problems/INCSEQ/
http://www.spoj.com/problems/INCDSEQ/
http://z-trening.com/tasks.php?show_task=5000000624
http://z-trening.com/tasks.php?show_task=5000000742
http://z-trening.com/tasks.php?show_task=5000000749
http://z-trening.com/tasks.php?show_task=5000001044
http://www.spoj.com/problems/SEQ/
http://www.spoj.com/problems/SPP/
http://z-trening.com/tasks.php?show_task=5000000078
http://z-trening.com/tasks.php?show_task=5000000543
http://z-trening.com/tasks.php?show_task=5000000718
http://z-trening.com/tasks.php?show_task=5000000237
http://z-trening.com/tasks.php?show_task=5000000311
http://www.spoj.com/problems/MORSE/ (dp + trie) Very Hard.
http://www.spoj.com/problems/MPOLY/
http://www.spoj.com/problems/CVXPOLY/
http://www.spoj.com/problems/MTRIAREA/
http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=2222
http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1122
http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1122
http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1125
Game (IOI 2008, Practice session)
http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static



Graph Theory:
http://community.topcoder.com/stat?c=problem_statement&pm=10736
http://www.spoj.com/problems/TRAFFICN/
http://www.spoj.com/problems/PA06ANT/
http://www.spoj.com/problems/PT07Z/
http://www.spoj.com/problems/EXPLOSN/
http://www.spoj.com/problems/BUGLIFE/
http://www.spoj.com/problems/SSORT/
http://www.spoj.com/problems/ARBITRAG/
http://www.spoj.com/problems/CODE/
http://www.spoj.com/problems/FROGGER/
http://www.spoj.com/problems/GCPC11C/
http://www.spoj.com/problems/GCPC11J/
http://www.spoj.com/problems/GHOSTS/
http://www.spoj.com/problems/MAKETREE/
http://www.spoj.com/problems/PARADOX/
http://www.spoj.com/problems/QTREE/
http://www.spoj.com/problems/QTREE2/
http://www.spoj.com/problems/QUEEN/
http://www.spoj.com/problems/ROBOTGRI/
http://www.spoj.com/problems/ELEVTRBL/
http://www.spoj.com/problems/TRIPINV/
http://www.spoj.com/problems/CAPCITY/
http://www.spoj.com/problems/KOICOST/

9 comments:

  1. Thanks for the prolems...............

    ReplyDelete
  2. _/\_
    Kahan se banaya ye mega collection :O

    ReplyDelete
  3. Sir,may I get your solution of spoj.com/problems/SPP???

    I am unable to form transformation matrix for this question...

    ReplyDelete
  4. Anybody who has solved CODE problem on SPOJ, could you please guide me? I cannot think of anything :(

    ReplyDelete
  5. in the to read section of dp... add the below mit 6.006 fall 2011 video lectures also...
    These are actually very helpful to understand an approach to dp solutions.
    look out for lectures 19,20,21,22 in the below link.

    http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/

    ReplyDelete
  6. Thanks for the comprehensive list

    ReplyDelete
  7. bhai ek number...dua lagegi meri !!

    ReplyDelete