Problem: khajiit (2019 finals)

The far-off land of Tamriel is brimming with opportunity! Opportunity for
adventure, politics, romance... and, perhaps most importantly of all,
commerce.

A group of Khajiit merchants, traditionally known for roaming the countryside
selling their wares, have recently set up permanent bazaars in a number of
towns. Having gotten their cat-like paws on a large supply of raw amber and
bronze, they're prepared to strategically work together to maximize their
profits selling it!

One bazaar has been set up in each of **N*****M**+1 towns. The towns are
numbered from 0 to **N*****M**, inclusive, and are connected by roads in a
hub-and-spokes arrangement, with town 0 in the center and **N** lines of **M**
towns each arranged around it. The _i_th such line consists of towns
**M***(_i_-1)+1 to **M***_i_, inclusive, connected together in order by
**M**-1 roads (with one between towns **M***(_i_-1)+1 and **M***(_i_-1)+2,
another between towns **M***(_i_-1)+2 and **M***(_i_-1)+3, and so on). For
each line _i_, there is furthermore a road connecting its first town
(**M***(_i_-1)+1) to town 0. Note that each of the **N*****M** roads may be
travelled in either direction, and that each town may be reached from each
other town by following a sequence of roads.

For example, if **N**=4 and **M**=2, the arrangement of towns and roads would
look as follows:

![]({{PHOTO_ID:291992558607686}})

Initially, the bazaar in each town _i_ is stocked with either amber (if **Xi**
= "A") or bronze (if **Xi** = "B"). However, in order to satisfy demand, it
should end up stocked with a potentially different ware, either amber (if
**Yi** = "A") or bronze (if **Yi** = "B"). It's guaranteed that the number of
bazaars initially stocked with amber is equal to the number of bazaars which
should end up stocked with amber (consequently, the same holds true for
bronze).

In order to accomplish their goal, the Khajiit merchants may repeatedly select
a pair of towns which are directly connected by a road, and swap their
bazaars' wares. Please help them determine the minimum number of such swaps
required for all **N*****M**+1 bazaars to end up stocked with the required
wares! This is guaranteed to be possible for every possible valid input.

### Input

Input begins with an integer **T**, the number of Khajiit groups.  
For each group, there is first a line containing the space-separated integers
**N** and **M**.  
Then follows a line with the length-(**N** * **M** \+ 1) string **X**, the
characters **X0** through **XN*M**.  
Then follows a line with the length-(**N** * **M** \+ 1) string **Y**, the
characters **Y0** through **YN*M**.

### Output

For the _i_th group, print a line containing "Case #_i_: " followed by one
integer, the minimum number of swaps required to stock all of the bazaars with
the required wares.

### Constraints

1 ≤ **T** ≤ 80  
1 ≤ **N**, **M** ≤ 1,000,000  
1 ≤ **N** * **M** ≤ 1,000,000  

The sum of **N** * **M** across all **T** test cases is no greater than
10,000,000.

### Explanation of Sample

In the first case, no swaps are required.

In the second case, bazaars 1 and 2 should swap their goods.

In the third case, the bazaars are initially set up as follows (with ones
carrying amber marked in yellow, and ones carrying bronze marked in orange):

![]({{PHOTO_ID:266243124686458}})

The following sequence of 3 swaps could then be performed to arrive at the
required configuration:

![]({{PHOTO_ID:637978470132709}})  
![]({{PHOTO_ID:950762542025264}})  
![]({{PHOTO_ID:635336360404128}})  



Sample input:
7
1 1
AB
AB
1 1
AB
BA
2 2
BBAAA
AABAB
3 2
AABBABB
BBABBAA
4 4
BBBAAABABAABAABAA
AAAABBABAABBBAAAB
5 8
ABBAAABABBABBABABAAABABABBAABBBAAAAABBBAB
AAABBABAABBBABABABAAAABBBAABBBBBAABBABAAA
8 7
BBBAABAABAABBBBAABBABAAAAABBBBBAAABAABBBABABBBBBAABBAAAAA
ABBBAAAABBBBBBBBAAAABBABBABABAAABABBBBBBAABBAAAAAAAABAABB


Sample output:
Case #1: 0
Case #2: 1
Case #3: 3
Case #4: 6
Case #5: 13
Case #6: 36
Case #7: 54



Code: // Khajiit
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x < 0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x * x); }
string plural(string s) { return(Sz(s) && s[Sz(s) - 1] == 'x' ? s + "en" : s + "s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int& x) {
	char c, r = 0, n = 0;
	x = 0;
	for (;;) {
		c = GETCHAR();
		if ((c < 0) && (!r))
			return(0);
		if ((c == '-') && (!r))
			n = 1;
		else if ((c >= '0') && (c <= '9'))
			x = x * 10 + c - '0', r = 1;
		else if (r)
			break;
	}
	if (n)
		x = -x;
	return(1);
}

bool ReadLL(LL& x) {
	char c, r = 0, n = 0;
	x = 0;
	for (;;) {
		c = GETCHAR();
		if ((c < 0) && (!r))
			return(0);
		if ((c == '-') && (!r))
			n = 1;
		else if ((c >= '0') && (c <= '9'))
			x = x * 10 + c - '0', r = 1;
		else if (r)
			break;
	}
	if (n)
		x = -x;
	return(1);
}

#define MOD 1000000007
#define LIM 1000005

int N, M;
char X[LIM], Y[LIM];

LL Solve(int s) {
	int i;
	LL sum = 0;
	int hasA = 0, needsA = 0;
	FoxR(i, M) {
		if (X[s + i] == 'A')
			hasA++;
		if (Y[s + i] == 'A')
			needsA++;
		sum += Abs(hasA - needsA);
	}
	return(sum);
}

int main() {
	if (DEBUG)
		freopen("in.txt", "r", stdin);
	// vars
	int T, t;
	int i;
	// testcase loop
	Read(T);
	Fox1(t, T) {
		// input
		Read(N), Read(M);
		scanf("%s%s", &X, &Y);
		// handle each spoke
		LL ans = 0;
		Fox(i, N)
			ans += Solve(i * M + 1);
		// output
		printf("Case #%d: %lld\n", t, ans);
	}
	return(0);
}