Help on CF Mex Sequences

Problems and Contests
#1

Hi, I need help with this problem. Specifically, I need help understanding the \texttt{DP} transitions in the editorial. I don’t understand how this can only be solved in O(n) memory (the editorial isn’t clear on this). I got the observations on the two possible sequences that could work, and got to the \texttt{DP}, but idk how to reduce the DP to linear time and memory.

#2

It’s pretty clear that the editorial code takes O(n) time and memory.

#3

I don’t really understand the editorial transitions.

      dp1[x + 1] = add(dp1[x + 1], dp1[x + 1]);
      dp1[x + 1] = add(dp1[x + 1], dp1[x]);
      if (x > 0) dp2[x - 1] = add(dp2[x - 1], dp2[x - 1]);
      if (x > 0) dp2[x - 1] = add(dp2[x - 1], dp1[x - 1]);
      dp2[x + 1] = add(dp2[x + 1], dp2[x + 1]);

I don’t really understand any of these transitions. Could you explain these to me?