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 .
You can split this sequence on k chains, where s(0)=s(k)=s(2k)..., s(1) = s(k+1) = ..., s(k-1) = s(2k-1) = ... Then s(0) xor s(1) xor ... xor s(k-1) should be true. Denote cost(i, j) — number of steps to obtain all j-s in the i-th chain. Assume you have all zeroes at first and your answer is cost(0, 0) + cost(1, 0) + ... cost(k-1, 0). Then you should choose odd number of elements with maximum cost(i, 1) — cost(i, 0). You can sort by this value and then solve this problem. Edit: sorry with minimum cost(i, 1) — cost(i, 0).