Why use hashing or trie, when you can use brute-force ?

# ENGLISH Video Editorial - (Without Using Trie)

Well, actually, I thought upon a little on this approach, and if we go by the constraints that the sum of all lengths of all strings is around 10^5, the number of distinct strings you can form is around 20k at max. Because then the sum of strings’ length will cross 10^5. So it’s a little higher than 10^8, technically it should give TLE for the time limit of 1 second. But if the TL was 2-3 seconds, this approach should’ve worked well within the TL.

Isn’t your time complexity is O(n^2 log(n^2)) because of sorting in worst case?

I tried implementing your method using C++, but not getting the desired output. Can you please look into this- https://ideone.com/UXrsOo

Well, let’s consider this case(easily generated with back-tracking)

All strings from “a” to “z”(26)

All strings from “aa” to “zz”(26^2)

All strings from “aaa” to “zzz”(26^3)

11473 strings with 4 letters

So N=26+26^2+26^3+11473=29751. There is absolutely no way on earth for the O(N^2) solution to pass this test. And as someone pointed out, there is also a sorting needed, so the complexity is O(N^2 log N) which is even worse.

So, how did it pass the test?

I guess, they didn’t make any test like this one

This logic passes coincidentally as complexity is

O(n^2log(n)) but i have a very good approach which i used in the contest. My approach uses O(nlog(n)).

Lets do it for subtask1 first.

Take n strings and sort them.

Now we can surely conclude that maximum beauty can only be obtained by selecting a consecutive pair.

So after getting pair with max beauty just remove it now we have n-2 strings left. Apply same operation on them also. I uses priority queue for storing beauty of any two consecutive strings with their indexes.

For subtask2 just make the string palindrome

Ex- s=abc

Modified string = acbbca

I hope u like my solution.

I am getting wrong answer in 1 test case in each subtask. Can anyone suggest counter exaple.

My code link:

https://www.codechef.com/viewsolution/29018283

If possible please give counter example.

Code logic:

add to map and count frequency.

match the same and add score to final_score add remaining will be added to vector v

calculate score of every pair from v and if score is >0 add to vector score along with ids of string

sort vector score based on scores

take pair by pair untill all is selected or all pairs are checked