Блог пользователя MarioYC

SPOJ UNTITLED
Автор MarioYC, 12 лет назад, По-английски

Could anyone give me a hint on how to solve this problem?

I solved POJ 3167 in which the problem was based using a modified KMP, but i couldn't come up with anything that solves UNTITLED.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
12 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

I can`t understend why answer is "1 2 3".

1 because {1}={2}, 2 because {3,1}={10,1}, and what is 3?

UPD. understood

→ Ответить
»
12 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Maybe in KMP:

a[0]...a[i]...a[j]...a[k]

a[0]...a[i]==a[j]...a[k] if a[0]...a[i-1]==a[j]...a[k-1] and a[i]==a[k].

a[i]==a[k] if and only if count of numbers which greather then a[i] in a[0]..a[i-1] is equal to count of numbers which greather then a[k] in a[j]..a[k-1].

We can use the struct like segment tree, which help us get this count in O(log(400000)) (just +1 to a[i] when we add number a[i] ans -1 else). If we get suffix(a[j]..a[k-1]) we don't forget to decrease all values which don't include to this suffix (it's a[j]..a[h], if a[j]..a[k-1]=a[j]..a[h]a[h+1]..a[k-1]). And first we should decrease all numbers as it possibly in any sequence because numbers are in the range 1..2^32 (then we can use a segment tree).

I don't know is it correct solution, but maybe.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes, I did something like that for POJ 3167, using a BIT. But in that problem we only need to match one pattern. In SPOJ UNTITLED you need to match many patterns.

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

read the solution to ceoi 2011 Matching

→ Ответить