Omkar and Pies
Contest: Codeforces Global Round 10
Difficulty rating: 2900
Tags: bitmasks, dfs and similar, dp, math, shortest paths

Omkar has a pie tray with $$$k$$$ ($$$2 \leq k \leq 20$$$) spots. Each spot in the tray contains either a chocolate pie or a pumpkin pie. However, Omkar does not like the way that the pies are currently arranged, and has another ideal arrangement that he would prefer instead.

To assist Omkar, $$$n$$$ elves have gathered in a line to swap the pies in Omkar's tray. The $$$j$$$-th elf from the left is able to swap the pies at positions $$$a_j$$$ and $$$b_j$$$ in the tray.

In order to get as close to his ideal arrangement as possible, Omkar may choose a contiguous subsegment of the elves and then pass his pie tray through the subsegment starting from the left. However, since the elves have gone to so much effort to gather in a line, they request that Omkar's chosen segment contain at least $$$m$$$ ($$$1 \leq m \leq n$$$) elves.

Formally, Omkar may choose two integers $$$l$$$ and $$$r$$$ satisfying $$$1 \leq l \leq r \leq n$$$ and $$$r - l + 1 \geq m$$$ so that first the pies in positions $$$a_l$$$ and $$$b_l$$$ will be swapped, then the pies in positions $$$a_{l + 1}$$$ and $$$b_{l + 1}$$$ will be swapped, etc. until finally the pies in positions $$$a_r$$$ and $$$b_r$$$ are swapped.

Help Omkar choose a segment of elves such that the amount of positions in Omkar's final arrangement that contain the same type of pie as in his ideal arrangement is the maximum possible. Note that since Omkar has a big imagination, it might be that the amounts of each type of pie in his original arrangement and in his ideal arrangement do not match.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq m \leq n \leq 10^6$$$ and $$$2 \leq k \leq 20$$$)  — the number of elves, the minimum subsegment length, and the number of spots in Omkar's tray respectively.

The second and third lines each contain a string of length $$$k$$$ consisting of $$$0$$$s and $$$1$$$s that represent initial arrangement of pies and ideal arrangement of pies; the $$$j$$$-th character in each string is equal to $$$0$$$ if the $$$j$$$-th spot in the arrangement contains a chocolate pie and is equal to $$$1$$$ if the $$$j$$$-th spot in the arrangement contains a pumpkin pie. It is not guaranteed that the two strings have the same amount of $$$0$$$s or the same amount of $$$1$$$s.

$$$n$$$ lines follow. The $$$j$$$-th of these lines contains two integers $$$a_j$$$ and $$$b_j$$$ ($$$1 \leq a_j, b_j \leq k$$$, $$$a_j \neq b_j$$$) which indicate that the $$$j$$$-th elf from the left can swap the pies at positions $$$a_j$$$ and $$$b_j$$$ in the tray.

Output format:
Output two lines.

The first line should contain a single integer $$$s$$$ ($$$0 \leq s \leq k$$$) equal to the amount of positions that contain the same type of pie in Omkar's final arrangement and in Omkar's ideal arrangement; $$$s$$$ should be the maximum possible.

The second line should contain two integers $$$l$$$ and $$$r$$$ satisfying $$$1 \leq l \leq r \leq n$$$ and $$$r - l + 1 \geq m$$$, indicating that Omkar should pass his tray through the subsegment $$$l, l + 1, \dots, r$$$ to achieve a final arrangement with $$$s$$$ positions having the same type of pie as his ideal arrangement.

If there are multiple answers you may output any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the swaps will go like this:

- Swap $$$1$$$ and $$$3$$$: 11000 becomes 01100
- Swap $$$3$$$ and $$$5$$$: 01100 becomes 01001
- Swap $$$4$$$ and $$$2$$$: 01001 becomes 00011

In the second test case, the swaps will go like this:

- Swap $$$1$$$ and $$$3$$$: 11000 becomes 01100
- Swap $$$1$$$ and $$$5$$$: 01100 becomes 01100
- Swap $$$4$$$ and $$$2$$$: 01100 becomes 00110
- Swap $$$1$$$ and $$$5$$$: 00110 becomes 00110

Example input:
4 2 5
11000
00011
1 3
3 5
4 2
3 4

Example output:
5
1 3

Example input:
4 3 5
11000
00011
1 3
1 5
2 4
1 5

Example output:
3
1 4

Editorial:
Consider any two binary strings $$$u$$$ and $$$v$$$ of length $$$k$$$. Notice that if you swap the bits at positions $$$\alpha$$$ and $$$\beta$$$ in $$$u$$$ and also swap the bits at positions $$$\alpha$$$ and $$$\beta$$$ in $$$v$$$, then the amount of common bits in $$$u$$$ and $$$v$$$ remains the same. Furthermore, you can do this multiple times – i. e. applying the same sequence of swaps to $$$u$$$ and $$$v$$$ doesn't change their amount of common bits.
Let's apply this to the problem at hand. Assume that Omkar has selected the subsegment of elves between some $$$l$$$ and $$$r$$$. Let $$$s$$$ be Omkar's original binary string, let $$$s'$$$ be $$$s$$$ after applying the subsegment of swaps between $$$l$$$ and $$$r$$$ (inclusive) to it, and let $$$t$$$ be Omkar's ideal binary string. Now consider applying all the swaps in the subsegment from $$$1$$$ to $$$r$$$ (inclusive) to both $$$s$$$ and $$$t$$$, but in reverse – first we apply the $$$r$$$-th swap, then the $$$r - 1$$$-th swap, and so on, until we finally apply the $$$1$$$-st swap.
From our first observation, these new strings $$$s^{\prime\prime}$$$ and $$$t^{\prime\prime}$$$ have the same amount of common bits as $$$s'$$$ and $$$t$$$. We additionally notice that just as $$$t^{\prime\prime}$$$ is $$$t$$$ with the subsegment of swaps from $$$1$$$ to $$$r$$$ applied in reverse, $$$s^{\prime\prime}$$$ is actually $$$s$$$ with the subsegment of swaps from $$$1$$$ to $$$l - 1$$$ applied in reverse, as the subsegment of swaps from $$$l$$$ to $$$r$$$ that were applied to $$$s$$$ to create $$$s'$$$ has been undone.
Let us then define some more strings as follows: for all $$$j$$$ such that ($$$0 \leq j \leq n$$$), let $$$s_j$$$ be the result of applying the subsegment of swaps from $$$1$$$ to $$$j$$$ in reverse to $$$s$$$, and let $$$t_j$$$ be the result of applying the subsegment of swaps from $$$1$$$ to $$$j$$$ in reverse to $$$s$$$ (so $$$s_0 = s$$$ and $$$t_0 = t$$$). We now see that the amount of common bits that result from choosing a subsegment of swaps between $$$l$$$ and $$$r$$$ is equivalent to the amount of common bits between $$$s_{l - 1}$$$ and $$$t_r$$$, and so the problem is now simply to find two indices $$$j_1$$$ and $$$j_2$$$ such that $$$j_2 - j_1 \geq m$$$ and the amount of common bits between $$$s_{j_1}$$$ and $$$t_{j_2}$$$ is the maximum possible.
Here we make another observation: if $$$\omega$$$ is the amount of common bits between two binary strings $$$u$$$ and $$$v$$$ of length $$$k$$$, $$$\epsilon$$$ is the amount of bits set to $$$1$$$ in $$$u$$$, $$$\zeta$$$ is the amount of bits set to $$$1$$$ in $$$v$$$, and $$$\lambda$$$ is the amount of common bits set to $$$1$$$ in $$$u$$$ and $$$v$$$, then $$$\omega = 2\lambda + k - \epsilon - \zeta$$$. Since we are only comparing strings derived from performing swaps on $$$s$$$ to strings derived from performing swaps on $$$t$$$, and swaps don't change the overall amount of $$$1$$$ bits in a string, $$$\epsilon$$$ and $$$\zeta$$$, like $$$k$$$, are constants – $$$\epsilon$$$ is the amount of $$$1$$$ bits in $$$s$$$, and $$$\zeta$$$ is the amount of $$$1$$$ bits in $$$t$$$. This means that maximizing $$$\omega$$$, the amount of common bits in $$$u$$$ and $$$v$$$, is equivalent to maximizing $$$\lambda$$$, the amount of common $$$1$$$ bits in $$$u$$$ and $$$v$$$.
Therefore, we can now proceed with bitmask DP to finish the problem. For a binary string $$$\mu$$$ of length $$$k$$$, let $$$left_\mu$$$ be the smallest index $$$j$$$ such that $$$\mu$$$ is a subset of $$$s_j$$$ considering $$$1$$$ bits, and let $$$right_\mu$$$ be the largest index $$$j$$$ such that $$$\mu$$$ is a subset of $$$t_j$$$ considering $$$1$$$ bits. These DP values are straightforward to compute, and we can obtain our answer by choosing the subsegment of swaps from $$$left_\mu$$$ to $$$right_\mu$$$ for any $$$\mu$$$ with the largest amount of $$$1$$$ bits such that $$$left_\mu$$$ and $$$right_\mu$$$ both exist and $$$right_\mu - left_\mu \geq m$$$.