ritik_patel05's blog

C:Two Array. How to optimize my code?
By ritik_patel05, history, 5 years ago, In English

Problem : https://mirror.codeforces.com/contest/1288/problem/C

My solution: https://mirror.codeforces.com/contest/1288/submission/68821660

Can anyone tell while I calculate dp[pos][i][j], I am using O(n*n) to calculate for each pair. Can I optimize by using some precalculated sum array, as we do in 1D case to get the sum for a particular range in an array?

In my code, I have written this, //to calculate dp[pos][i][j] //using dp[pos — 1][previ][prevj]

How can I do this in O(1) to fit in timelimit?

I am thinking about this optimization for a long time, but I got to nowhere.

It would be great if there is any way to do it.

Thank you :)

Have a great day!

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Yes, you can use precalculated sum for matrix.

Let be $$$p_{ij}$$$ sum of all elements whose indices less than $$$i$$$ and $$$j$$$. This can be calculated as follows:

int a[n][m]; // initail matrix
int p[n + 1][m + 1]; //sum matrix

for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= m; ++j){
        //use inclusion-exclusion principle for calculate sum
        p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i - 1][j - 1];
    }
}

Sum of all elements specified by indices $$${x_1, y_1}$$$ and $$${x_2, y_2}$$$ (0-indexing) can be calculated:

//inclusion-exclusion principle
sum = p[x2 + 1][y2 + 1] - p[x1][y2 + 1] - p[x2 + 1][y1] + p[x1][y1];

In problem you can calculate sum elements use only array dp.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Sometimes we can remove some loops by changing our transitions.

You can think that we will change $$$i$$$ and $$$j$$$ in all possible ways before using dp of $$$pos-1$$$.

$$$dp[pos][i][j] = dp[pos-1][i][j] + dp[pos][i+1][j] + dp[pos][i][j-1]$$$

But there is a problem with this. The state $$$[pos][i+1][j-1]$$$ can be reached in two different ways($$$[pos][i+1][j] => [pos][i+1][j-1]$$$ and $$$[pos][i][j-1]=>[pos][i+1][j-1]$$$) and it is overcounted. However, it is always two ways so we can easily remove one.

$$$dp[pos][i][j] = dp[pos-1][i][j] + dp[pos][i+1][j] + dp[pos][i][j-1] - dp[pos][i+1][j-1]$$$

And the answer is just $$$dp[m][1][n]$$$.

It's possible improve it further by normalizing $$$i$$$ and $$$j$$$ so that always $$$i = 1$$$. Now that $$$i$$$ is constant, it can be removed from our states. The dp becomes:

$$$dp[pos][j] = dp[pos-1][j] + dp[pos][j-1] + dp[pos][j-1] - dp[pos][j-2]$$$

And the answer is $$$dp[m][n]$$$.

→ Reply