Sunday, 23 June 2013

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.
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,
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 : (Heavy Light implementation). (Heavy Light implementation).


SRM 310 -> Floating Median

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:

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:


SGU Problems :  269273304317356396445447458489494 (dp + trie) Very Hard.
Game (IOI 2008, Practice session)

Graph Theory: