Double or NOTing Solution Code Jam 2021

Table of Contents

Problem

You are given a starting non-negative integer SS and an ending non-negative integer EE. Both SS and EE are given by their binary representation (that is, they are given written in base 22). Your goal is to transform SS into EE. The following two operations are available to you:

Double your current value.
Take the bitwise NOT of your current value. The binary representation of your current value is taken without unnecessary leading zeroes, and any unnecessary leading zeroes produced by the operation are dropped. (The only necessary leading zero is the one in the representation of 00).

For example, by using the double operation, 66 becomes 1212, 00 becomes 00, and 1010 becomes 2020. By using the NOT operation, 00 becomes 11, 11 becomes 00, 3=1123=112 becomes 00, 14=1110214=11102 becomes 11, 10=1010210=10102 becomes 5=10125=1012, and 5=10125=1012 becomes 2=1022=102. (X2X2 means the integer whose binary representation is XX).

You can use these operations as many times as you want in any order. For example, you can transform S=100012S=100012 to E=1112E=1112 using the NOT operation first, then using the double operation twice, and then another NOT operation:100012⟹NOT11102⟹×2111002⟹×21110002⟹NOT1112.100012⟹NOT11102⟹×2111002⟹×21110002⟹NOT1112.

Determine the smallest number of operations needed to complete the transformation, or say it is impossible to do so.

Input

The first line of the input gives the number of test cases, TT. TT test cases follow. Each consists of a single line containing two strings SS and EE, the binary representations of the starting and ending integers, respectively.

Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is IMPOSSIBLE if there is no way to transform SS into EE using the two operations. Otherwise, yy is the smallest number of operations needed to transform SS into EE.

Limits

Time limit: 10 seconds.
Memory limit: 1 GB.
1≤T≤1001≤T≤100.
Each character of SS is either 0 or 1.
The first digit of SS can be 0 only if the length of SS is 11.
Each character of EE is either 0 or 1.
The first digit of EE can be 0 only if the length of EE is 11.

Test Set 1 (Visible Verdict)

1≤1≤ the length of S≤8S≤8.
1≤1≤ the length of E≤8E≤8.

Test Set 2 (Hidden Verdict)

1≤1≤ the length of S≤100S≤100.
1≤1≤ the length of E≤100E≤100.

Sample

Sample Input

6
10001 111
1011 111
1010 1011
0 1
0 101
1101011 1101011

Sample Output

Case #1: 4
Case #2: 3
Case #3: 2
Case #4: 1
Case #5: IMPOSSIBLE
Case #6: 0

Sample Case #1 is the example shown in the main part of the statement.

These are possible optimal ways of solving Sample Cases #2, #3, and #4, respectively:10112⟹NOT1002⟹×210002⟹NOT1112,10112⟹NOT1002⟹×210002⟹NOT1112,10102⟹×2101002⟹NOT10112, and10102⟹×2101002⟹NOT10112, and02⟹NOT12.02⟹NOT12.

In Sample Case #5, it is not possible to get from 0202 to 10121012 with any sequence of operations.

In Sample Case #6, we do not need to perform any operations because S=ES=E.

Solution:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5, inf = 1e9;
int T, n, m;
char s[maxn + 10], t[maxn + !0];
int a[maxn + 10], acnt, ans;

void solve(int p, int d) {
acnt = 0;
for (int i = 1; i <= n; ++i) a[++acnt] = s[i] == ‘1’;

for (int i = n – p + 2; i <= m; ++i) a[++acnt] = (t[i] == ‘1’) ^ d;

int L = 1, R = n; bool rev = 0;

if (L == p && R == acnt && rev == d) { ans = min(ans, 0);

return;

}

for (int f = 1; f <= 500; ++f) { if (R < acnt && a[R + 1] == rev && a[L] != rev)

{ ++R;

}

else

{ while (a[L] != rev && L < R)

++L;

rev ^= 1; } if (L > p)

return;
if (L == p && R == acnt && rev == d)

{
ans = min(ans, f); return;
}
}
}

int main() {
scanf(“%d”, &T);
for (int cas = 1; cas <= T; ++cas)

{ scanf(“%s%s”, s + 1, t + 1);

n = strlen(s + 1);

m = strlen(t + 1); ans = inf;

for (int i = 1; i <= n + 1; ++i)

{ int cnt[2] = {0, 0};

if (n – i + 1 > m) continue;
for (int j = i; j <= n; ++j)
++cnt[s[j] != t[j – i + 1]];
if (cnt[1] == 0) solve(i, 0);
if (cnt[0] == 0) solve(i, 1);
}
printf(“Case #%d: “, cas);
if (ans < inf) printf(“%d\n”, ans);
else puts(“IMPOSSIBLE”);
}
}