PROBLEM LINK:
Practice
Contest, div. 1
Contest, div. 2
Author: Alexey Zayakin
Tester: Ildar Gainullin
Editorialist: Oleksandr Kulkov
DIFFICULTY:
EASY
PREREQUISITES:
Basic binary operations
PROBLEM:
Consider the following function written in pseudo-code:
function add(A, B):
while B is greater than 0:
U = A XOR B
V = A AND B
A = U
B = V * 2
return A
You’re given binary numbers A and B and have to tell the number of times inner loop is repeated.
QUICK EXPLANATION:
Calculate the length of the longest carry chain.
EXPLANATION:
Basically this representation means that U is digit-wise sum and V is carry. We may interpret the whole process as if we simultaneously started addition in all points and carried excessive bits in all places at the same time. We can get the whole time of the process by some case-work. Let’s simulate simple addition with carry. Let’s look closely on the number carry_i + A_i + B_i.
- If it’s equal to 0 or 1 then it won’t affect the carrying process.
- If it’s equal to 2 then we either initiate carrying process with A_i=B_i=1 or continue it with having carry=1 and either of A_i and B_i being equal to 1.
- Finally, if it’s equal to 3 then carrying process will start from scratch as after first xor there will be 0 on i-th place and carry_i will simply drop here, while some new carry from A_i + B_i will go on (i+1)-th bit.
Thus, the answer to the problem can be obtained by carefully simulating the process. You should also take an extra look on B=0 case.
void solve() {
// Aligning and reversing bits of A and B
string A, B;
cin >> A >> B;
reverse(begin(A), end(A));
reverse(begin(B), end(B));
while(A.size() < B.size()) A += "0";
while(B.size() < A.size()) B += "0";
A += "0"; B += "0";
// actual solution is below
int carry = 0, ans = 0, cur = 0;
for(size_t i = 0; i < A.size(); i++) {
carry = carry + (A[i] - '0') + (B[i] - '0');
if(carry > 1) {
cur++;
} else {
cur = 0;
}
carry /= 2;
ans = max(ans, cur);
}
cout << ans + (B.find('1') != string::npos) << endl;
}
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.