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 :)