ICPC Dhaka 2020: B. Password Shuffling

icpc_dhaka_20_b.cc

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define FastIO ios::sync_with_stdio(false); cin.tie(0);
#define all(x) (x).begin(), (x).end()

const int inf = 0x3f3f3f3f;
const ll INF = 2e18;

vector<int> pos[128];

#define has(mask, x) ((mask) & (1ll << (x)))

int res = inf;
string src, des;
int n;

void ba(int idx, ll mask, int gr, int pre_en) {
	if(idx == n) {
		res = min(res, gr);
		return ;
	}

	if(gr >= res) return ;

	for(int p : pos[des[idx]]) {
		if(!has(mask, p) or p == pre_en + 1) continue;
		
		ll nmask;
		int k;
		int klim = min(n - idx, n - p);
		for(k = 0, nmask = mask; k < klim and has(mask, p+k) and src[p + k] == des[idx + k]; ++k) {
			nmask ^= (1ll << (p + k));
			ba(idx + k + 1, nmask, gr + 1, p + k);
		}
	}
}

int main() {
	FastIO;

	int t, tc = 0;
	cin >> t;
	cerr << "T: " << t << "\n";

	while(t--) {
		cin >> src >> des;
		n = src.size();

		for(int i=0; i<128; ++i) pos[i].clear();
		for(int i=0; i<n; ++i) pos[src[i]].push_back(i);

		res = n;
		ba(0, (1ll << n) - 1, 0, -5);
		cout << "Case " << ++tc << ": " << res << "\n";
	}

	return 0;
}