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

×

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:

This question is marked "community wiki".

asked 16 Jun '17, 11:15

melfice's gravatar image

4★melfice
811837
accept rate: 0%

edited 12 Jul '17, 00:27

admin's gravatar image

0★admin ♦♦
19.8k350498541


Also add link to this editorial on the problem page.

link

answered 22 Jul '17, 18:17

ravibitsgoa's gravatar image

4★ravibitsgoa
534
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×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