wa in SSTORY suffix arrays

general
,
21

i solved it with suffix arrays, only thing is you need to look more than just adjacent cells to find the required answer.

CodeChef: Practical coding for everyone :smiley:

22

My code handles this case as well. But still, got WA.
Here’s the link to my code: wct7zH - Online C++ Compiler & Debugging Tool - Ideone.com

23

generate some random test cases & then generate output from ac code & then check your code by yourself :slight_smile:

24

Thanks …

25

Wow, that actually works? I thought that approach would TLE, I overlooked the overall complexity. Nice work!

26

But still, the problem can be solved with Suffix Arrays, in many different ways. So apart from the late regrades, this problem turned out well, because it can have diverse solutions, totally different from the setter’s.

1 Like
27

Thanks!
Yes it will work because of the trade off between length of lcs and number of lcs. If there are more number of lcs (higher k) then length of lcs is less and construction takes less time. And if length of lcs is high then there are lesser lcs (lower k) and matching takes less time. So overall the solution passes the time limit.

28

I found the length of the LCS say ‘k’ using SA and LCP. Now the task was to find the minimum index ‘i’ in s2 s.t. s2[i…(i+k-1)] is also the longest common substring. So what I did was I again iterated over LCP array and found the minimum such index in all valid windows. I define a valid window as [i…j] s.t. k<=LCP[s] for s \in [i,j] and LCP[i-1]<k and LCP[j+1]<k and there is q1 in [i,j] s.t. SA[q1] starts in s1 and there is a q2 s.t. SA[q2] starts in s2. You can look at my function algo() in my [solution][1] .
[1]: CodeChef: Practical coding for everyone

1 Like
29

Generating substrings can become O(N^2) in the worst case. How does this pass?

Isn’t the complexity for std::erase() O(N) where N = length of the string?

30

Try this test case: “fagehe”,“fhfgfg”. Your code gives WA for this test case

31

@tinchy_stryder have a look at my solution where I generate all substrings in O(n)

32

Hi, I was able to discover this trick during the contest. I modified my code to handle this trick as well but I still kept on getting WAs. Can you or someone else provide me a case where my code fails? Link to my code → CodeChef: Practical coding for everyone

You may add printf(“Index: %d\n”,Ind-M-1); before if(Len>0) statement to verify correctness.

33

Thanks a lot. Really helped!