Hello,
I found this weird dynamic programming solution to the following Hackerearth problem.
The problem setter's solution uses network flow to solve the task and I was able to understand that after reading the editorial. On the other hand, I am unable to come up with a proof of correctness for the dp solution which I have linked above. This has been in my TODO list for over a month now and it feels as if I am not getting anywhere near the proof.
To be honest, it feels counter intuitive that a task that uses network flow can be solved with dynamic programming but I could not come up with a counter example either.
However, I was able to prove the following lemma that hints that the dp solution might be correct but this is about as far as I reached —
If for each index 1 ≤ i ≤ n we can generate a segment that starts at i using the given queries then your opponent can discover the parity of each element from i = 1 to n
Any kind of help will be appreciated :)
Each given [l, r] segment can be represented as a linear equation in Z2: a1x1 + a2x2 + ... + anxn = c
with ai = 0 if i < l or i > r, and ai = 1 if l ≤ i ≤ r, c = 0 or 1.
We must find the minimum number of equations to be erased so that the system of remaining equations can not be solved.
The solution you mentioned simply calculate Gauss Elimination of given system of equations over Z2. If you can not find a pivot at some step of Gauss Elimination, you can't solve the system of equations, so that solution find number of vectors that can be picked as pivot and erase them all.
I don't think it can be called DP, it's just using array to count vectors. And that solution is just another approach beside the minimum cut approach to this problem.
That makes sense! Thanks for the explanation! Had I not seeked help I would have been misguided by variable naming forever :P