WorstCoder45's blog

By WorstCoder45, history, 5 weeks ago,

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"

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

• 0

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by WorstCoder45 (previous revision, new revision, compare).
 » 5 weeks ago, # | ← Rev. 2 →   +1 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).