Gaajvi's blog

Trie problem
By Gaajvi, history, 11 years ago, In English

Can someone help me to solve this problem ? I try trie with sets in each vertex. It is TLE. how to reduce time?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Maybe ternary search trie instead of a normal trie. Note I did not read the problem.

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

from what I tried:

  • non-recursive segment tree (/blog/entry/18051): per query, AC with time 1.9s (TL 2s)
  • segment tree with fractional cascading: , TLE
  • persistent segment tree: , AC, 0.9s
  • persistent trie: , TLE
→ Reply
  • »
    »
    11 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +3 Vote: I do not like it

    Persistent trie: per query, AC, 0.61s

    → Reply
  • »
    »
    11 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it +5 Vote: I do not like it

    It's clear how to solve using segment tree storing sorted arrays in each vertex in O(n·log(n)) memory and O(log2(n)·log(maxX)) time per query.

    But I haven't a clue how to solve it using persistent segment tree, can you explain please?

    → Reply
»
11 years ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

Non persistent trie , AC, 0.75s

Used vectors in each vertex instead of sets.

→ Reply