For the following problem [problem:543A], the jury's solution↵
[submission:11035704] optimize the DP solution explained in the contest's editorial http://codeforces.me/blog/entry/17773.↵
↵
I understood the approach explained in the editorial, but what's the intuition behind the optimization and how it works? Specially the lines with bitwise operations:↵
↵
↵
~~~~~↵
int i = it & 1;↵
...↵
z[i][j][k] = z[i ^ 1][j][k];↵
...↵
ans += z[n & 1][bl][i];↵
...↵
~~~~~↵
↵
Just to be clear: I'm not asking about the bitwise operations alone, but also how the original solution in the editorial translated to the jury's code. For example, if you maintain only the two last rows of the DP, how are you going to construct the problem's solution (output)?↵
Thanks.
[submission:11035704] optimize the DP solution explained in the contest's editorial http://codeforces.me/blog/entry/17773.↵
↵
I understood the approach explained in the editorial, but what's the intuition behind the optimization and how it works? Specially the lines with bitwise operations:↵
↵
↵
~~~~~↵
int i = it & 1;↵
...↵
z[i][j][k] = z[i ^ 1][j][k];↵
...↵
ans += z[n & 1][bl][i];↵
...↵
~~~~~↵
↵
Just to be clear: I'm not asking about the bitwise operations alone, but also how the original solution in the editorial translated to the jury's code. For example, if you maintain only the two last rows of the DP, how are you going to construct the problem's solution (output)?↵
Thanks.
