MarioYC's blog

SPOJ UNTITLED
By MarioYC, 14 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

»
14 years ago, hide # |
← 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
»
14 years ago, hide # |
← 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
  • »
    »
    14 years ago, hide # ^ |
     
    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
»
14 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

read the solution to ceoi 2011 Matching

→ Reply
»
7 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Since the original problem is solved using KMP, and now we have multiple patterns, naturally we should solve this problem using the generalization of KMP to multiple strings, which is Aho–Corasick.

How to implement
→ Reply