### hippie's blog

By hippie, 5 years ago, ,

The only resource available on the internet regarding the application of matrix exponentiation to TWO-DIMENSIONAL dynamic programming problems is this :-

Though the author has covered the topic with nice examples, I have some doubts:-

1) Unlike solving linear recurrences (using matrix exponentiation), I cannot find any solid mathematics behind the steps (or how does it work mathematically) involved in this technique.

2) How are the base-states taken into account in this technique? After building the adjacency-matrix (as is explained in the quora-article), and exponentiating it, what all values do we have to sum up to get the final answer?

I am pretty vague about all these details so any help will be much appreciated.

• +11

By hippie, 5 years ago, ,

How exactly is the square root decomposition of queries (also sometimes referred to as Mo's Algorithm), used for offline processing of queries? If possible, please explain with an example.

NOTE :- I've gone over this post, but it lacks in covering the topic with an example and complexity analysis properly.

• +1

By hippie, 5 years ago, ,

Should a state in DP be viewed as

1) a description of current scenario (e.g. in knapsack problem -->I am on item 'i' with having filled the bag with 'j' units)

OR as

2) a separate sub-problem (e.g. in knapsack problem -->maximum value that can be attained with weight less than or equal to 'j' using items upto 'i' (first 'i' items) )

I have seen both the interpretations used many times and I would welcome some opinions regarding the same.

• +5

By hippie, 5 years ago, ,

Problem --> Interesting Array (CF Round 275): Div.1/B or Div.2/D

Tourist's code : http://ideone.com/c5dTmY

In this problem, for every set bit in query, we set the corresponding bit for all the numbers in the given range. I can't understand how he's doing that by:

s[from[k]][j]++; s[to[k] + 1][j]--;

Also, for calculating the number of set bits for a given bit position, for a given range of numbers, he's made some sort of cumulative array. Please explain its construction:

bal += s[i][j]; a[i][j] = (bal > 0); sum[i + 1][j] = sum[i][j] + a[i][j];