CLONEME - Editorial

PROBLEM LINK:

Practice
Contest

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.

RELATED PROBLEMS:

1 Like

Also add link to this editorial on the problem page.

1 Like

When you use

, how do you check that p and q are on consecutive positions?

In the part
if(mod == 0)
if(ch1 == 0 && ch2 == 0)

The second check() should use the array R[] instead of L[] right?