MotaSanyal's blog

By MotaSanyal, history, 4 weeks ago, In English,

Hi everyone!

I was trying to solve this problem which came in last year ICPC Gwalior-Pune Onsite Round.

My approach :

I first checked whether C is present either in A or in B, if so, then answer will be length(A) + length(B) Otherwise , found the longest prefix of C that occurs as a suffix of A (say, X) and longest suffix of C that occurs as prefix of B (say, Y). Then if X+Y <= length(C), answer will be length(A) + length(B) + (length(C) — (X+Y)) , else if X+Y > length(C), then answer is length(A) + length(B) + (length(C) — max(X,Y)).

The verdict I am getting is Wrong Answer. Can anyone please point out where am I going wrong?

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

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

This test case should be wrong answer:

1
aab 
bbb 
abb

Because C may not be composed of the greater suffix of A or the greater prefix of B, however, C may be composed of a piece of A plus some string plus a piece of B

In this case the best solution would be to take the suffix of size 2 of A and the prefix of size 1 of B

The problem can be solved by calculating all possible suffixes of A where C can begin and all prefixes of B where C can end

After you have these sizes, separate the suffixes of A and the prefixes of B into two sets and then order them

Then by binary search or the two pointers method you can search for each suffix of A the largest prefix of B such that the suffix of A plus the prefix of B are less than or equal to the size of C

The answer must then be size of A plus size of B plus size of C minus the highest value of the specific above

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

    Thanks a lot for the test case and for pointing out my mistake. Thanks a lot :)