returnA's blog

By returnA, history, 17 months ago, In English

Given two strings A and B(binary string) of size n, and an Integer K. Two types of operation available-

  1. Choose two indices i and j, flip both A[i], A[j]. Cost of this is K.

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
17 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Minimum no of operation...

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.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      getting wrong :)

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      n = 6 , K = 2 A = 101011 B = 010010

      Output: 3

      n = 4, k = 3 A = 1010 B = 0001

      Output: -1

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I mean, if we just focus on two index $$$i, j$$$, there're 2 ways to flip:

        • flip $$$(i, j)$$$ directly, costing $$$K$$$;
        • flip $$$(i, i+1), (i+1, i+2), \cdots, (j-1, j)$$$, costing $$$j-i$$$

        I suppose there is no better way to fix the two positions.

        And the problem is, this method is only partial right.

    • »
      »
      »
      17 months ago, # ^ |
      Rev. 2   Vote: I like it +4 Vote: I do not like it
      #include <bits/stdc++.h>
      using namespace std;
      void f()
      {
          int n;
          cin >> n;
          int x;
          cin >> x;
          string A, B;
          cin >> A >> B;
          int cnt = 0;
          for (int i = 0; i < n; i++)
          {
              if (A[i] != B[i])
                  cnt++;
          }
          if (cnt & 1)
          {
              cout << -1 << '\n';
              return;
          }
          int cost = 0;
          vector<int> a;
          for (int i = 0; i < n; i++)
          {
              if (A[i] != B[i])
                  a.push_back(i);
          }
          int k = a.size();
          for (int i = 0; i < k / 2 - 1; i++)
          {
              cost += min(x, a[2 * i + 1] - a[2 * i]);
              cost += min(k, a[k] - a[1]);
          }
          cout << cost << '\n';
      }
      
      signed main()
      {
          int t = 1;
          cin >> t;
          while (t--)
              f();
      }
      

      What is wrong here, can you pls help me to fix

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Can anyone fix it?

        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.

        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          No, brother, Why sorry.

          You even tried to help me a lot.

          Thanks

»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

This problem seems to be pretty much equivalent to 1733D2 - Zero-One (Hard Version).