TigranHakobyan's blog

Topcoder problem
By TigranHakobyan, history, 9 years ago, translation, In English

Hi, everyone.

Can someone, please, explain the solution for this problem ?

I really cannot understand what editorial wants to say.
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been translated by TigranHakobyan(original revision, translated revision, compare)

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

Sorry that I can't find editorial. I think you can sort all cars alphabetically and use DP to find maximum length. You have to sort cars to find first-alphabetical one easily.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    If you mean just sort a alphabetically, then if we consider {acbd, abcd, bda}. Using your idea we will get answer 2 but the answer is 3, isn't it ?
    P.S. editorial

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

      Probelm says, "The front end is the end with the letter that comes first in the alphabet", so you have to flip car "bda" into "adb".

      so in case {"acbd", "abcd", "bda"}, the answer is 1.

      and if the car A and car B can be linked, A.front <= A.back == B.front <= B.back, so sort like this.

      sort(cars.begin(),cars.end(),comp);

bool comp(string s1,string s2){
   if(s1.front() != s2.front()) return s1.front() < s2.front();
   if(s1.back() != s2.back()) return s1.back() < s2.back();
   return s1 < s2;
}

      ardiankp's code

      sorry about my English — I'm not good at it.

      → Reply