Why use hashing or trie, when you can use brute-force ? 
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- UXrsOo - Online C++0x Compiler & Debugging Tool - Ideone.com
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.
1 Like
So, how did it pass the test?
1 Like
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.
2 Likes
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