HolkinPV's blog

Codeforces Beta Round #33. Разбор B
By HolkinPV, 14 years ago, translation, In English
It was assumed a such solution. Firstly, if the lengths of strings were not equal, obviously the answer is -1. In the other case for all positions we search for all letters and try to make changes to the current letter. To make it quick, we will precalc a matrix Z[26][26], in which the сell (i, j) - is the minimum cost of change of i-th the letter of the alphabet to j-th. It can be done for example by Floyd algorithm. If at some position there is no possible letter, the answer is -1. In the other case, we should sum the answer for all positions and write the resulting string.
  • Vote: I like it
  • +5
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I created a 2d Graph and did a simple Floyed to relax all the edges as explained .. then looped on the Strings and every time I found two characters don't match I try to find Min(graph[a][k]+graph[b][k]), where 0<=k<=25 ,and 'a' ,'b' is the character in the first ,second String respectively. 

However I'm getting a TLE on case 26 :/ .. 

any clue ? .. 

here's my code : 
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Use StringBuilder to construct the final result. Usage of += with the String is a slow operation.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Accepted ! :) .. amazing yet frustrating :S :/ :/ ..

      Thanks alot :)..
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    My friends had TL on case 26 but because of the different string error.
    He used C-style strings char* and in the loop he wrote strlen(s).
    Don't do this because this operation costs O(length of the string).
    C++-style strings are more convenient for this case and s.size() is OK.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Or just store the strlen(s) in a variable.
      Char array is faster than the C++ string, so I suggest you to use it when you can.
      → Reply