×

# CLONEME - Editorial

Author: Sidhant Bansal
Tester: Ajay Verma
Editorialist: Oleksandr Kulkov

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.

# RELATED PROBLEMS:

This question is marked "community wiki".

4★melfice
811837
accept rate: 0%

19.8k350498541

 0 Also add link to this editorial on the problem page. answered 22 Jul '17, 18:17 53●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,719
×1,755
×1,250
×149
×35
×33

question asked: 16 Jun '17, 11:15

question was seen: 812 times

last updated: 22 Jul '17, 18:17