You are not logged in. Please login at to post your questions!


CLONEME - Editorial



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




Persistent segment tree, polynomial hashes


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.


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.


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);
            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);
            return check(L[va], L[vb], L[vc], L[vd], 1, l, m);
        if(ch2 == 0 && any1)
            return 0;
        else if(any1)
            return check(L[va], L[vb], L[vc], L[vd], 2, l, m);
            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 solution will be updated soon.
Tester's solution will be updated soon.
Editorialist's solution will be updated soon.


This question is marked "community wiki".

asked 16 Jun '17, 11:15

melfice's gravatar image

accept rate: 0%

edited 12 Jul '17, 00:27

admin's gravatar image

0★admin ♦♦

Also add link to this editorial on the problem page.


answered 22 Jul '17, 18:17

ravibitsgoa's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 16 Jun '17, 11:15

question was seen: 812 times

last updated: 22 Jul '17, 18:17