marlonbymendes's blog

By marlonbymendes, history, 8 years ago, In English

For the following problem 543A - Пишем код, the jury's solution 11035704 optimize the DP solution explained in the contest's editorial http://mirror.codeforces.com/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.

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by marlonbymendes (previous revision, new revision, compare).

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by marlonbymendes (previous revision, new revision, compare).