PROBLEM LINK:
Author: Sidhant Bansal
Tester: Ajay Verma
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Persistent segment tree, polynomial hashes
PROBLEM:
You are given array of n integers and q queries. For each query you have to check if sorted elements from [a;b] and [c;d] have at most one mismatch on pairwise comparison.
QUICK EXPLANATION:
Use persistent segment tree to maintain hashes of elements which occur on each prefix. Then check if there is exactly one mismatch of hash values.
EXPLANATION:
In this particular problem we want to check similarity of sets of numbers so it is good idea to mark set of numbers with polynomial hash \sum\limits_i x^{a_i}. Since we want to check equality of hashes from subsegments, it would be useful to use well-known technique used in k^{th} order statistics or order of key on segment queries. We maintain persistent segment tree in such way that tree built over first m elements of array contains number occ_ix^i in i^{th} leaf. Where occ_i is the number of occurences of number i on m^{th} prefix. Now when we maintained such segment tree, we have to check whether occ_i for [a;b] and [c;d] differ in either zero or two consequent positions:
/*
Checks if occ[l..r] for [a;b] matches with occ[l..r] for [c;d].
mod = 0: two consequent mismatches allowed
mod = 1: single mismatch on suffix allowed
mod = 2: single mismatch on prefix allowed
va, vb = vertices of occ[l;r] for (a;b]
vc, vd = vertices of occ[l;r] for (c;d]
*/
bool check(int va, int vb, int vc, int vd, int mod = 0, int l = 0, int r = maxn)
{
if(r - l == 1) // single mismatch allowed
return abs((occ[vb] - occ[va]) - (occ[vd] - occ[vc])) <= 1;
int m = (l + r) / 2;
bool ch1 = (hash[L[vb]] - hash[L[va]]) == (hash[L[vd]] - hash[L[vc]]); // is full match on left
bool ch2 = (hash[R[vb]] - hash[R[va]]) == (hash[R[vd]] - hash[R[vc]]); // is full match on right
bool any1 = (hash[L[vb]] - hash[L[va]]) || (hash[L[vd]] - hash[L[vc]]); // any non-null on left
bool any2 = (hash[R[vb]] - hash[R[va]]) || (hash[R[vd]] - hash[R[vc]]); // any non-null on right
if(mod == 0)
{
if(ch1 == 0 && ch2 == 0)
return check(L[va], L[vb], L[vc], L[vd], 1, l, m) &&
check(L[va], L[vb], L[vc], L[vd], 2, m, r);
else if(ch1 == 0)
return check(L[va], L[vb], L[vc], L[vd], 0, l, m);
else
return check(R[va], R[vb], R[vc], R[vd], 0, m, r);
}
else if(mod == 1)
{
if(ch1 == 0 && any2)
return 0;
else if(any2)
return check(R[va], R[vb], R[vc], R[vd], 1, m, r);
else
return check(L[va], L[vb], L[vc], L[vd], 1, l, m);
}
else
{
if(ch2 == 0 && any1)
return 0;
else if(any1)
return check(L[va], L[vb], L[vc], L[vd], 2, l, m);
else
return check(R[va], R[vb], R[vc], R[vd], 2, m, r);
}
}
As you can see, the code above finds both mismatch positions in O(\log C).
The other elegant idea to simplify the solution is to maintain sum of elements and sum of squared elements on prefixes. Then, assuming that arrays differ in numbers p and q, we can get p-q and p^2-q^2 which will give us an opportunity to find p and q and then simply check by hashes that corresponding segments are equal if we disregard p and q.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be updated soon.
Tester’s solution will be updated soon.
Editorialist’s solution will be updated soon.