ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1713. Key Substrings

WA test 2
Posted by andrei parvu 16 Sep 2010 22:39
Can somebody tell me how they passed test nr. 2 (or give me some good test cases)?

I have a solution in O(N*M*log(N*M)) using suffix array and I can't find the bug.

Thanks

Edited by author 16.09.2010 22:39
Re: WA test 2
Posted by VC15 (Orel STU) 25 Jun 2012 18:40
I've got absolutely the same problem. I use suffix and lcp arrays.

I use the following algo:
for i = 1 to LENGTH_OF_ALL_WORDS
  l = the closest preceding suffix that belong to another word
  r = the closest succeeding suffix that belong to another word
  v = max(lcp(l, i), lcp(i, r)) + 1;
  w = the word that contains suffix i;
  if (v < ans[w]) ans[w] = v;

I've tried lots of tests but can't find what's wrong.
Strange AC
Posted by VC15 (Orel STU) 26 Jun 2012 16:39
There is something strange with this problem. I hasn't written suffix array building on my own, I used a reference implementation. Looking for a bug I replaced it with code that builds suffix array in the naive way (i.e. literally sorting suffixes). I got AC!
So there are 2 results:
- The reference implementation I used is wrong :)
- The test data seems to be weak because naive suffix and LCP arrays building gets AC.
Re: WA test 2
Posted by caiweiwenjs 29 Jun 2012 13:46
TO VC15 (Orel STU)
max(lcp(l, i), lcp(i, r)) + 1 may longer than the word‘s length

Edited by author 29.06.2012 13:49
Re: WA test 2
Posted by VC15 (Orel STU) 30 Jun 2012 13:29
Yes, it could be. In this case I don't change the answer for the word.