hagu's blog

TIMUS 1713 : Key Substring
By hagu, 10 years ago, In English

I was trying this question and i got WA at case 3. Problem Link:- http://acm.timus.ru/problem.aspx?space=1&num=1713

My approach includes constructing a suffix array on string formed by concatenating all the strings(commands) given in the input.

Then for each index belonging to the command i am calculating the max value of LCP that can be formed using other indexes belonging to other commands. For doing that i am calculating the closest indexes to that index not belonging to the same command using the Array sorted in order of suffixes.

For any command the answer of that command will be the smallest value of LCP of indexes belonging to that command described as above .

I am unable to find any bug . So please Help ......

This is my code :- http://ideone.com/8veKxE

This is my first post , so kindly ignore any mistakes .

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You can write any easy-to-code solution, generate some small random test cases and compare the answers. This should help you to find your bug.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Do you know any solution better than for O(107)?

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks a lot for the suggestion. I was able to figure out my mistake by generating random cases . :)

    → Reply