WorstCoder45's blog

By WorstCoder45, history, 4 years ago, In English

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 .

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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