Need help in this problem || Can we do it without DP ?

→ Обратите внимание

До соревнования
Educational Codeforces Round 173 (Rated for Div. 2)
33:30:51
Зарегистрироваться »

→ Трансляции

aryanc403

До начала 35:40:50

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	151

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя returnA

Need help in this problem || Can we do it without DP ?

Автор returnA, история, 18 месяцев назад, По-английски

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.

dp, string

returnA
18 месяцев назад
10

Комментарии (10)

Написать комментарий?

Lice-wx

18 месяцев назад, # |

← Rev. 3 →

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.

→ Ответить

Lice-wx

18 месяцев назад, # ^ |

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?

→ Ответить

returnA

18 месяцев назад, # ^ |

getting wrong :)

→ Ответить

returnA

18 месяцев назад, # ^ |

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

Output: 3

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

Output: -1

→ Ответить

Jack_sparrow_06

18 месяцев назад, # ^ |

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

→ Ответить

Lice-wx

18 месяцев назад, # ^ |

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.

→ Ответить

returnA

18 месяцев назад, # ^ |

← Rev. 2 →

#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

→ Ответить