Understanding the Prime XOR edition - HackerRank
Disclaimer: This question includes content from the respective editorial. Thus, if you want to fix this problem yourself, I discourage you from reading this post. Also, my question is missing some of the details mentioned in the editorial, so please refer to the editorial board when you read my question.
Also, please remember that I do not intend to advertise HackerRank; furthermore, I do not take responsibility for the content of the editorial, the description of the issue, or any other material that is considered to be an infringement of the copyright of HackerRank or its affiliates).
Actual question :
I am trying to understand the edition of this issue. In particular, the part I'm confused about 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 dynamic programming solution with a O(N)
constant factor 8192
such that it dp[i][j]
will store the number of subsets that can be formed using the first elements such that the xor is the sum of the elements in the subset j
. "
It can be seen from the code that mem
in essence dp
, except I can't wrap my head around a function flag
- what is it flag
?. Also, I understand what 1 + (a[v[i - 1]])/2
corresponds to the number of Evens in [0, a [v [i-1]]] and (a[v[i - 1]] + 1) / 2
corresponds to the number of coefficients in the same interval, but I don't see how it is quite related to everything.
Thanks in advance for your efforts.
source to share
Explanation of the flag
This is the standard approach to reduce memory usage when using dynamic programming.
The idea is that often each row in a DP array depends only on the previous row. In this case, instead of storing the entire 2d DP [i] [j] array, you can simply use 2 lines of the array instead.
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, the last two lines of the complete DP array are saved.
Explanation of repetition
Suppose we have 5 duplicates of some value v. There are 1 + 5/2 ways to make xor of 0 (take either 0.2 or 4 copies). There are (1 + 5) / 2 ways to make xor v (take either 1.3 or 5 copies).
So, to create a new value for j, we can either start at j or add 0.2 or 4 copies of v, or start at j ^ v and add 1.3 or 5 copies.
source to share