MarioYC's blog

SPOJ UNTITLED
By MarioYC, 12 years ago, In English

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.

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

»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

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.

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

    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.

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

read the solution to ceoi 2011 Matching

→ Reply