How to solve this Xor Based problem ?

Revision en2, by WorstCoder45, 2020-10-28 17:04:48

Link to the problem : https://www.codechef.com/AGPR2020/problems/ALPR2005

Statement :

Given a binary sequence of length $$$n$$$, find the minimum number of changes needed so that bitwise-xor of every subarray of size $$$k$$$ is exactly 1 .

1<=n,k<=100000 .

A change operation is defined as : "You can change "1" to "0" , vice-versa"

Similar problem : https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/

The only thing I could decipher till now is that the answer mainly depends on the first subarrays of size k .

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English WorstCoder45 2020-10-28 17:04:48 81
en1 English WorstCoder45 2020-10-28 17:03:19 511 Initial revision (published)