MarioYC's blog

XOI POI — A Horrible Poem
By MarioYC, 11 years ago, In English

Hi everyone, I've been trying this problem: http://main.edu.pl/en/archive/oi/19/okr

I'm getting 67/100 using hashing, and the fact that the hash of a string of the form xxx..xx (repetead K times) can be calculated in O(lgK) once you have the hash for x.

But I don't know how to improve to get 100 points. Any hint?

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use periodicity lemma and factorization with sieve of Eratosthenes.

→ Reply
»
11 years ago, # |
← Rev. 9   Vote: I like it 0 Vote: I do not like it

Consider the problem when we have only one query (1, n) i.e. we have to find a period (not full period) of entire poem. Period of "bcabc" is "bca" because "bcabc" is a prefix of "bcabca"("bca"+"bca"). Using hashing we can compare(equal or not) any substrings in O(1). So entire problem can be solved in O(n log(n) ). Just bruteforce lentgh k of repeated prefix and check all string in O(n / k). Remember all n * log(n) results of comparsions (do not break comparions if you already have not equal substrings). Now, for each query (a, b), we have to check only divisors of a number (b — a + 1). Check for specified lenght k can be done in O(1) using hash and an array of prefix sums over an array of comparsions for each value of k.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 8   Vote: I like it 0 Vote: I do not like it

    consider a string "aaxabcababcabcabc".
    for k=1, we have an array A1 of lentgh n [1, 0, 0, ... 0]
    for k=2, we have an array A2 of lentgh n/2 [0, 0, .. 0]
    for k=3, we have an array A3 of lentgh n/3 [0, 1, 1, ... 1]
    ...

    now we have an query (8, 16). check all divisors of (16 — 8 + 1)=9.
    k=1: fail
    k=3:
    1) check for equals prefix and suffix (or doubled prefix and suffix) it's ok
    2) check that substring ((a / k + 1) * k, (b / k) * k — 1) is periodic with period of k i.e. an array Ak in posiotions (a / k + 1) * k, (a / k + 1) * k + 1, (a / k + 1) * k + 2, ... , (b / k) * k ) has only ones. i.e. PA(k)[(b / k — 1)] — PA(k)[a/k — 1] == (b / k — 1) — (a / k — 1). PA(k) is prefix sums array of array Ak. PA(k)[i] = PA(k)[i-1]+ "a[i*k,i*k+k)==a[i*k+k, i*k+k+k)". There can be many errors in the formulas above use +-1 and your brain to correct them.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can see many solutions here(but not editorial in English) :http://oi.edu.pl/ ,though sometimes the variables or comments are written in Polish.

→ Reply