Lakh's blog

Need help in a hashing+query problem
By Lakh, history, 6 years ago, In English

I am solving this problem http://codeforces.net/gym/101804/problem/J.

Here we are given the alphabet size N (N<=26). So if N=4 ,then the alphabet set is=[A,B,C,D] . Now we are given a permutation of the above alphabet. The permutation represents the encoded value of an alphabet . For e.g. if permutation is [D,C,A,B] then A changes to D, B changes to C , C changes to A and so on. Now Q (Q<=10^5) queries are there of three types:

  1. 1 s: Add string s to the list. (|s|<5*10^5)
  2. 2: For all the strings currently in list , encode them according to given permutation.
  3. 3 s: Check if s is prefix of some string in the current list. (|s|<5*10^5)

Sum of length of strings over all queries is<5*10^5.

My approach : Here whenever a string is added , I computed all the N encodings of the string as maximum cycle length can be N after which strings will be repeated and stored them in N maps. I stored the hash of prefixes of the string in a map. For type 2 since all strings are encoded so i just took a counter and increment it to (counter+1)%N. For type 3 query i just checked if hash of s is present in map of current counter. however i am getting TLE. Please suggest some optimization to the approach or some other method to solve this. I also implemented this problem with trie but got MLE.

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

Comments Comments (6)
| Write comment?
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Implement trie using map. It will have O(n) memory so you probably won't get MLE.

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

I think what you can do is keep a track of all changes using a separate array(ar).

For query of type 2 : Just make the changes to ar.

For query of type 1 : Apply changes to the string and insert the new string

For query of type 3 : Apply changes to the string s and query it.

For this a single trie is sufficient and hence your MLE problems are also solved.

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

    sdssudhu I didn't get you. I used map for trie which resolved MLE problem but now getting TLE. Can you explain a bit more??

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

      What I say is just have a track of the permutations for each query for type 2 in an array.

      Now, the permutation of the letters is known after each query of type 2 (apply the permutations to the already changed array).

      Now for insertion of a string apply all the changes to the string that is since you know the permutation of the letters encrypt the given string and insert it into the trie.

      For search query what you can do is similarly encrypt the string you have and use it for searching in the trie.

      Upd: For encryption of the string it will take O(n). And for searching in trie it is the same. Since you are using a single trie I can you won't have both MLE and TLE.

      What I mean by keeping track of permutations is that consider : k = CAB and alphabet is {A,B,C}

      Now first time when query 2 happens alphabet will be {C,A,B}.

      Next time when query 2 happens alphabet is {B,C,A}.

      So just encrypt the given strings according to this modified permutation and perform insertion or search.

      P.S i didn't try this solution yet and I got this by intuition. So let me know if this works.

      → Reply