MAKE_AB_SAME - Editorial

Authors: gunpoint_88
Testers: iceknight1093, tabr
Editorialist: iceknight1093

TBD

None

PROBLEM:

You have two binary arrays A and B.
In one move, you can pick three indices 1 \leq i \lt j \lt k \leq N, and set A_j := A_i \mid A_j \mid A_k.
Find out whether A can be made equal to B.

EXPLANATION:

The operation we perform has the following properties:

• It cannot turn a 1 into a 0 (if A_j = 1, then no matter what i and k we choose A_i\mid A_j \mid A_k = 1 will hold).
• To turn a 0 into a 1, the array must itself contain a 1 somewhere (if A_j = 0, then for A_i \mid A_j \mid A_k = 1 to hold, either A_i = 1 or A_k = 1 must be true).
• It cannot change A_1 and A_N, since j is strictly larger than 1 and strictly less than N.

This gives us a set of checks for when making A cannot be made equal to B:

• If A_1 \neq B_1 or A_N \neq B_N, the answer is â€śNoâ€ť.
• If A_i = 1 and B_i = 0 for some i, the answer is â€śNoâ€ť.
• If A_i = 0 and B_i = 1 for some i, and A doesnâ€™t contain any ones, the answer is â€śNoâ€ť.

If the number of ones in A is computed first, this check can be done in \mathcal{O}(1) for each index, leading to \mathcal{O}(N) time overall.

If none of the â€śNoâ€ť conditions trigger, the answer is â€śYesâ€ť.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 'Yes'
ones = a.count(1)
for i in range(n):
if a[i] > b[i]: ans = 'No'
elif a[i] < b[i] and ones == 0: ans = 'No'
if a[0] != b[0] or a[-1] != b[-1]: ans = 'No'
print(ans)

1 Like

Hi

if A = 0 0 0 0 1
B = 0 0 1 0 1

then the answer will be no because when you try to convert A[2] = 0 to A[2] = 1 using the last element of A then A[3] will be converted to 1. Now A[3] can not be converted to 0 so the answer will be no but your code is returning yes.

a corner case is not check here , when B[i] is 0 and A[i] is also 0 we need to check if a 0 is present in the array A before the index and also after the index , if not present we have to return NO but it is not checked , please clarify

@kl902828 I think itâ€™s not mandatory to apply this operation to every index. So, if they are already same, we can skip.

1 Like

hey please tell why my solution is wrong
https://www.codechef.com/viewsolution/92814570

Choose i=0 or 1, j=2, k=4. Applying Aj = Ai|Aj|Ak operation, you can get A = 0 0 1 0 1.
The indices i, j, and k do not have to be consecutive.

Can we get WA failed test cases available for this problem?
Also, can anyone please tell me where this code fails?
https://www.codechef.com/viewsolution/92823080

1
3
1 1 1
1 0 1

1 Like

Java Solution:

/* package codechef; // donâ€™t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be â€śMainâ€ť only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner s = new Scanner(System.in);
long t = s.nextLong();
while(t-- > 0){
long n = s.nextLong();
int countA=0;

	    long[] arrA = new long[(int)n];
for(long i=0; i<n; i++){
arrA[(int)i] = s.nextLong();
if(arrA[(int)i] == 1){
countA++;
}
}

long[] arrB = new long[(int)n];
for(long i=0; i<n; i++){
arrB[(int)i] = s.nextInt();
}

boolean flag = true;
for(long i=0; i<n; i++){
if(arrA[0] != arrB[0]  || arrA[(int)n-1] != arrB[(int)n-1]){
flag = false;
}else if(arrA[(int)i] == 1 && arrB[(int)i] == 0){
flag = false;
}else if(arrA[(int)i] == 0 && arrB[(int)i] == 1 && countA == 0 ){
flag = false;
}
}
if(flag){
System.out.println("YES");
}else{
System.out.println("NO");
}

}
}


}

C++ Solution explained, intuition is simple.

        ll n;
cin >> n;
vector<char> a(n, '0'), b(n, '0');
bool flag = false;
// a
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
// b
for (int i = 0; i < n; i++)
{
cin >> b[i];
// check if a is 1 and b is 0, as we can't change 1 to 0 using or
if (a[i] == '1' && b[i] == '0')
{
flag = true;
}
}
if (flag)
{
cout << "NO\n";
continue;
}
// checking for corner as there will no i for 0th position and k for nth position and if in that case a and b are different then no
if ((b[n - 1] == '1' && a[n - 1] == '0') || (b[0] == '1' && a[0] == '0'))
{
cout << "NO\n";
continue;
}
// storing numbers of ones for front and back fashion so that we know for every position that there is ones available in front or back to convert it into 1.
vector<int> ones_f(n, 0), ones_b(n, 0);
for (int i = n - 1; i >= 0; i--)
{
if (a[i] == '1')
{
ones_b[i] = 1;
ones_f[i] = 1;
}
}
for (int i = 1; i < n; i++)
{

ones_f[i] += ones_f[i - 1];
}
for (int i = n - 2; i >= 0; i--)
{
ones_b[i] += ones_b[i + 1];
}
for (int i = 0; i < n; i++)
{
if (a[i] == '0' && b[i] == '1' && ones_f[i] == 0 && ones_b[i] == 0)
{
flag = true;
break;
}
}
if (flag)
{
cout << "NO\n";
}
else
{
cout << "YES\n";
}


Fuck I missed this.

Thanks