Digit Dynamic Programming problem

We will solve a DP problem today.

dp state is (index, tight).
where index is the position where we currently are (consider the process of constructing solution from left to right).
where tight is a variable which states the number which we have constructed up to now, is strictly less/greater or equal. Tight is false, means it has become less or greater. but true when equal.

Ex. 1. http://www.spoj.com/problems/SQAMOD/
find no of binary numbers less than a given n digit number S which have sum of squares of digits modulo 3 to be zero,
Solution:
1. dp (index, int sumModulo3, int tight):
      So let us see the transitions to different states. You can understand that by reading the code.

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 :  269, 273, 304, 317, 356, 396, 445, 447, 458, 489, 494
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/