ANGSPLIT - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Utkarsh Gupta
Tester: Aryan Choudhary
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Binary Search

PROBLEM:

Given two binary strings A and B of length N which are not anagrams. Find if there exists an index 1 \leq i \leq N, such that both conditions are fulfilled:

  • A[1,i - 1] and B[1,i - 1] are anagrams.
  • A[i + 1, N] and B[i + 1, N] are anagrams.

You are allowed to ask atmost 35 queries. In each query the judge returns the value |f(A, l, r) - f(B, l, r)|.

  • f(S, l, r) = frequency of 1 in substring S[l, r] (both inclusive).

EXPLANATION:

What is an Anagram?

GIven two binary strings A and B of length N, we say that they are anagrams if any permutation of B is equal to A. Formally, we can say that the frequency of 1 as well as the frequency of 0 in both the strings is the same.

In terms of this problem, if two strings A and B are anagrams, |f(A, 1, N) - f(B, 1, N)| = 0.

When is the answer -1?

Let us assume that the answer exists at index i, this means that for the index i:

  1. |f(A, 1, i - 1) - f(B, 1, i - 1)| = 0.
  2. |f(A, i + 1, N) - f(B, i + 1, N)| = 0.

The possible values of (A[i], B[i]) would be:

Case 1 - (A[i], B[i]) = (0, 0) : In this case, the frequency of 1 in both strings is the same. This makes the strings anagrams. Since we are given that the strings cannot be anagrams, this case cannot be true.

Case 2 - (A[i], B[i]) = (0, 1) : In this case, the frequency of 1 in string B is one greater than that of string A.

Case 3 - (A[i], B[i]) = (1, 0) : In this case, the frequency of 1 in string A is one greater than that of string B.

Case 4 - (A[i], B[i]) = (1, 1) : Similar to case 1, this is also impossible as it would lead to strings A and B being anagrams.

Thus, for a solution to exist, |f(A, 1, N) - f(B, 1, N)| = 1 must hold true. In other words, we say that if, |f(A, 1, N) - f(B, 1, N)| != 1, the answer is -1.

Finding an i, if the answer is not -1.

For the sake of simplicity, let us assume that f(A, 1, N) = f(B, 1, N) + 1. This won’t affect the result as the proof is symmetric for the other case.

Let us look at the function f(A, 1, i) - f(B, 1, i). We know that, at i = N, the value of this function is 1. Let us keep decreasing the value of i, until we reach a point such that, f(A, 1, i) - f(B, 1, i) = 1 and f(A, 1, i - 1) - f(B, 1, i - 1)1.

In other words, we want to find the smallest prefix such that f(A, 1, i) - f(B, 1, i) = 1. Since one index can change the value of the function by atmost 1, the value of f(A, 1, i - 1) - f(B, 1, i - 1) = 0. Also, since, f(A, 1, i - 1) - f(B, 1, i - 1) = 0 and f(A, i, i) - f(B, i, i) = 1, we get f(A, i + 1, N) - f(B, i + 1, N) = 0.

This implies that there exists a possible answer at index i.

Using the given query format, we need to search for an i, which satisfies the required conditions. We want the smallest prefix with |f(A, 1, i) - f(B, 1, i)| = 1, thus our queries would be of the form \texttt{? 1 i} or \texttt{? i+1 N}.

Since the maximum number of queries we can ask is 35, we cannot find the result by checking for all possible values of i. We need to use binary search for this.
For some given i, let us assume that the result of the query \texttt{? 1 i} is x and that of \texttt{? i+1 N} is y.

Case x>y:

  • f(A, 1, i) = f(B, 1, N) + x and f(A, i + 1, N) = f(B, i + 1, N) + y : This implies that f(A, 1, N) = f(B, 1, N) + x + y. Since x + y = 1 and x > y, the only possibility is x = 1 and y = 0. In this case, the answer lies in the range [1, i].
  • f(A, 1, i) = f(B, 1, N) + x and f(B, i + 1, N) = f(A, i + 1, N) + y : A possible answer can exist in both directions.
    Consider A = 11001 and B = 00110. For i = 2, x = 2 and y = 1. Possible answers in this case are index 1 (≤ 2) and index 5 (≥ 2).
  • f(B, 1, i) = f(A, 1, N) + x and f(A i + 1, N) = f(B, i + 1, N) + y : This is symmetric to the second case. We can possibly move in any direction for this case.
  • f(B, 1, i) = f(A, 1, N) + x and f(B, i + 1, N) = f(A, i + 1, N) + y : This is symmetric to the first case. In this case, the answer lies in the range [1, i].
    Overall, we can say that an answer always exists in the range [1, i].

Case x<y:

  • f(A, 1, i) = f(B, 1, N) + x and f(A, i + 1, N) = f(B, i + 1, N) + y : This implies that f(A, 1, N) = f(B, 1, N) + x + y. Since x + y = 1 and x < y, the only possibility is x = 0 and y = 1. Since we need the opposite, the answer lies in the range [i, N].
  • f(A, 1, i) = f(B, 1, N) + x and f(B, i + 1, N) = f(A, i + 1, N) + y : A possible answer can exist in both directions.
    Consider A = 10011 and B = 01100. For i =3, x = 1 and y = 2. Possible answers in this case are index 1 (≤ 2) and index 5 (≥ 2).
  • f(B, 1, i) = f(A, 1, N) + x and f(A i + 1, N) = f(B, i + 1, N) + y : This is symmetric to the second case. We can possibly move in any direction for this case.
  • f(B, 1, i) = f(A, 1, N) + x and f(B, i + 1, N) = f(A, i + 1, N) + y : This is symmetric to the first case. In this case, the answer lies in the range [i, N].
    Overall, we can say that an answer always exists in the range [i, N].

Case x=y:
This case never exists. Check for all combinations and figure out, why?

Conclusion
  • If |f(A, 1, N) - f(B, 1, N)|1, the answer is -1.
  • If |f(A, 1, i) - f(B, 1, i)| > |f(A, i+1, N) - f(B, i+1, N)|, the answer exists in the range [1, i].
  • If |f(A, 1, i) - f(B, 1, i)| < |f(A, i+1, N) - f(B, i+1, N)|, the answer exists in the range [i, N].

TIME COMPLEXITY:

The time complexity is O(log(N)) per test case.

SOLUTION:

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

int n;

int query(int l, int r){
	if(l > r) 
        return 0;
	cout<<"? "<<l<<" "<<r<<endl;
	int diff;
    cin>>diff;
    return diff;
}

void ans(int a){
	cout<<"! "<<a<<endl;
}

void solve()
{
    cin>>n;
    int possible = query(1, n);
	if(possible != 1){
		ans(-1);
		return;
	}

	int l = 0, h = n;
	while(h - l > 1){
		int mid = (l + h)/2;
		if(query(1, mid) > query(mid + 1, n))
			h = mid;
		else 
            l = mid;
	}
	ans(h);
}

int32_t main()
{

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    sync;
    int t = 1;
    cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}