Lakh's blog

By Lakh, history, 4 months ago, In English,

I am solving the following problem:

Given T (T<=75) testcases . Each testcase consists of N (N<=10^4) strings and Q (Q<=10^4) queries. In each query you are given a number X.The task is to find the most common suffix of length X among the given strings and you need to print how common it is. Sum of length of all strings in a testcase is<=10^5.

Link to problem: http://codeforces.com/gym/101502/problem/G

E.g. Input :

1
5 4

abccba
abddba
xa
abdcba
aneverknow

1
2
4
3

Output:

4
3
1
2

I am inserting the given strings in a trie and storing a variable count in each node to find number of strings along the given path with suffix of length K. Now for all possible length of suffixes I am updating the ans[] array which stores the result for a given suffix of length K. and hence answering queries in O(1) but I am geting TLE. I am not able to optimize it further . How to solve this problem?? My code: https://ideone.com/fNAWjb

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Lakh (previous revision, new revision, compare).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Lakh (previous revision, new revision, compare).

»
4 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

I approached it the same way and yeah, time limit is pretty tight. Try this:

#pragma GCC optimize("O3")
#pragma GCC optimize("expensive-optimizations")

Then I did some small optimizations and it passed after 779 ms.

Edit: It also passes without the above pragmas. You may implement the trie using simple array and don't re-initialize everything in each test case. Instead, keep track of the current test case and ignore trie entries from older test cases.

Submission: https://lpaste.net/2405931179027988480.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    neutron-byte Have you implemented static trie or the dynamic one??

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    neutron-byte I have implemented the above problem using array here
    https://ideone.com/9DAlEB Can you please check it as my complexity is O(N*STRING_LENGTH) for inserting string and computing the ans[] array for each test case and have used fast i/o but still TLE. Not able to understand reason behind this??

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you need to answer the queries online?

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    ___tutis___ No. Please suggest some approach for this problem.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hashing the prefixed might work :)

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can increase the length of the strings paralelly and maintain the occurency count of each hash in some data structure.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hmmm, my program passes within 217ms :D Solution

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for the reply. Mine passes within 436 ms. I missed the ios_sync statement . Can you please suggest some implementation or idea regarding the hashing of strings that is not affected by anti-hash test?? I read the blog on the same but was not able to find a convincing implementation.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Use multiple big enough random prime moduli.

»
4 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

I used hashing and unordered_map.It passed within 577 ms. My code

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my code without hashings and maps, just easy trie )