Understanding the Editorial for Prime XOR - HackerRank

Question

Disclaimer: This question involves content from the corresponding editorial. Thus, if you want to attempt this problem on your own, I discourage you from reading this post. Also, my question leaves out some details mentioned in the editorial, so please do refer to the editorial as you read my question.

Also, please bear in my mind that it is not my intention to advertise for HackerRank; furthermore, in no way, am I taking credit for the content on the editorial, problem description, or any other material that would be deemed a copyright infringement by HackerRank or affiliated parties).

---

Actual Question:

I'm trying to understand the editorial for this problem. Specifically, the part that I'm getting confused over is the following piece of code:

...
for(int i=1;i<=k;i++) {
    for(int j=0;j<8192;j++) {
        mem[flag][j] = (mem[flag^1][j]*(1+(a[v[i-1]])/2))%mod + (mem[flag^1][j^v[i-1]]*((a[v[i-1]]+1)/2))%mod;
        if(mem[flag][j]>=mod)
            mem[flag][j]%=mod;
    }
    flag = flag^1;
}

The editorial states that "...Using this property, we can write a O(N) dynammic programming solution with 8192 constant factor such that dp[i][j] would store the count of subsets that can be formed with the first elements such that the xor-sum of the elements in the subset is j."

From the code, it appears that mem is essentially dp, except I can't wrap my head around the function of flag -- what is flag?. Also, I get that 1 + (a[v[i - 1]])/2 corresponds with the number of evens in [0, a[v[i - 1]]] and (a[v[i - 1]] + 1) / 2corresponds with the number of odds in that same interval, but I don't see how it quite ties in with everything.

Thanks in advance for your efforts.

Answer 1

Explanation of Flag

This is a standard approach to reduce memory usage when using dynamic programming.

The idea is that often each row of a DP array only depends on the previous row. In this case, instead of storing the whole 2d DP[i][j] array, you can instead just use 2 rows of the array.

In other words, DP[i][j] is stored in mem[0][j] if i is even, and in mem[1][j] if i is odd. The mem array is reused multiple times and after each iteration holds the most recent two rows of the full DP array.

Explanation of recurrence

Suppose we have 5 duplicates of a certain value v. There are 1+5/2 ways of making an xor of 0 (take either 0,2 or 4 copies). There are (1+5)/2 ways of making an xor of v (take either 1,3 or 5 copies).

So to make the new value j, we can either start with j and add 0,2 or 4 copies of v, or start with j^v and add 1,3 or 5 copies.