Given two strings A and B(binary string) of size n, and an Integer K. Two types of operation available-
Choose two indices i and j, flip both A[i], A[j]. Cost of this is K.
Choose any adjacent pairs(A[i], A[i+1]) and flip both. Cost is 1.
Minimum no of operation to convert A to B. If not possible print Not possible.
I suppose you mean 'cost' instead of 'operation'. Here I may get a solution by intuition.
It's clear that if there are odd number of positions $$$i$$$ that satisfy $$$A_i \not = B_i$$$, it's impossible to convert.
Otherwise, find all the different positions, with indices $$$a_1, a_2, ..., a_k$$$(ascending). To fix two positions $$$a_i, a_{i+1}$$$, we need to cost $$$\min(K, a_{i+1} - a_i)$$$.
So I think the answer is $$$\sum_{i=1}^{k/2} \min(K, a_{2i} - a_{2i - 1})$$$, because any indirect serie of options seem to be meaningless.
If there's sth wrong with my sol, pls inform me.
update: sorry, it has problem because $$$\sum_{i=1}^{k/2 - 1} \min(K, a_{2i + 1} - a_{2i}) + \min(K, a_k - a_1)$$$ can also be the final answer, which make the sol complex. Can anyone fix it?
getting wrong :)
n = 6 , K = 2 A = 101011 B = 010010
Output: 3
n = 4, k = 3 A = 1010 B = 0001
Output: -1
I had one doubt. Why min(K, Ai+1 — Ai) ? since if we are at index 'i' and if it is possible to flip it with 'i+1' then the cost is 1, if the index we are choosing is greater than 'i+1' then the cost will be K. So We might have one possibility of fliping with adjacent element or else find any index 'j' which is greater than 'i+1' such that the index 'j' also not matches with B[j].
I mean, if we just focus on two index $$$i, j$$$, there're 2 ways to flip:
I suppose there is no better way to fix the two positions.
And the problem is, this method is only partial right.
What is wrong here, can you pls help me to fix
It seems that you didn't get my point. I've said, it's a wrong method.
If you think I waste your time, I'm sorry.
No, brother, Why sorry.
You even tried to help me a lot.
Thanks
This problem seems to be pretty much equivalent to 1733D2 - Zero-One (Hard Version).