returnA's blog

Need help in this problem || Can we do it without DP ?
By returnA, history, 18 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

»
18 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.

→ Reply
  • »
    »
    18 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?

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

      getting wrong :)

      → Reply
    • »
      »
      »
      18 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

      → Reply
    • »
      »
      »
      18 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].

      → Reply
      • »
        »
        »
        »
        18 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.

        → Reply
    • »
      »
      »
      18 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

      → Reply
      • »
        »
        »
        »
        18 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.

        → Reply
        • »
          »
          »
          »
          »
          18 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

          → Reply
»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

This problem seems to be pretty much equivalent to 1733D2 - Ноль-один (сложная версия).

→ Reply