Блог пользователя TigranHakobyan

Автор TigranHakobyan, история, 9 лет назад, По-русски

Hi, everyone.

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

I really cannot understand what editorial wants to say.
  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем TigranHakobyan (предыдущая версия, новая версия, сравнить).

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

    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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      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.