ENGLISH Video Solution

Here it is: https://youtu.be/zTYKA3E84Kc
Commented code: https://www.codechef.com/viewsolution/28947001
Trie:
https://www.geeksforgeeks.org/trie-insert-and-search/
Comments, questions, requests, criticism, are all welcome!

22 Likes

Its so amazing to see one question being solved by multiple different approaches.
World of problem solving is so interesting .
I used a different approach, but yours is pretty awesome.

3 Likes

would u mind sharing ur approach? i think i can learn from it as well :slight_smile:

2 Likes

Wow, better use of Trie. But I solved using Hashing

Instead of converting into combination of reversed pair .
I picked the first word from the list then made two separate lists, first containing those words having common first and last character as of selected first word.
Second list containing words different from first selected word.
For example. if words are abcd,abc,abb, aecd
list1= [‘abcd’,‘aecd’] , list2=[‘abc’,‘abb’]
this process is repeated till there are only 2 words left in the container, then just calculating the values for those 2 words and adding it to entire sum.
Also for those lists left with just single word, those words are reused in the process in each iteration.

I mean its kind of like your approach since this also separates each words and collect similar words but I suppose it is little bit different.

1 Like

Also there exists an integer value “repeat” for each depth denoting the similarities of two words, so that way I avoided calculating same thing again and again for each recurrsive call.

This approach is also works!
https://www.codechef.com/viewsolution/28926789

I tried to solve first half of the problem ( strings are palindrome).
As I assumed, that all strings are palindrome,
I can sort the array of strings.
[A B C] where A,B,C are palindrome strings in sorted order.
Then for maximum output, i should include either (A,B) or (B,C) pair. Because they are the closest to each other.
However, It is not working completely.

Help me to find my mistake.
Solution link: https://www.codechef.com/viewsolution/28802134

Your solution fails in the test case below:

abca should be paired with ada

1 Like

Thanks for reply.
But I am trying to solve first half of the problem where all strings are palindrome.
And abca is not palindrome.

One more…I solved it recursively. I basically tried to pair up strings of min common prefixes/suffixes. At first I checked for first letter of prefix. Then i divide all given strings into an array of 26 based on first alphabet. Then again checked for first letter of suffix and divide them further. Whenever any array has only 2 strings then were the one having most score. I also kept track of strings whose score has been calculated till now during the recursion.
mysol - https://www.codechef.com/viewsolution/28881842

1 Like

Sorry, I misunderstood you.
Here’s another case in which all strings are palindromes.


I think the best answer is 30.

2 Likes

Now, I got it. Thanks for help.

no problem

But this implementation which is similar to your approach is giving TLE

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxl=1e5+3;
int nodes, trie[maxl][676], cnt[maxl];
int dfs(int node, int len){
	ll res=0;
	for(int i=0; i<676; i++){
		if(trie[node][i]){
			res+=dfs(trie[node][i], len+1);
			cnt[node]+=cnt[trie[node][i]];
		}
	}
	while(cnt[node]>1){cnt[node]-=2; res+=len*len;}
	return res;
}
int main(){
	int t; scanf("%d", &t); while(t--) {
		memset(trie,0,sizeof(trie)); memset(cnt,0,sizeof(cnt)); nodes=1;
		int n; scanf("%d", &n);
		for(int i=0;i<n;i++){
			string word, rev; cin>>word; rev=word;
			reverse(rev.begin(), rev.end()); vector<int> v(word.length());
			for(int i=0;i<word.length();i++){
				v[i]=(word[i]-'a')*26+(rev[i]-'a');
			}
			int node=0;
			for(int i=0; i<v.size(); i++){
				if(!trie[node][v[i]]) trie[node][v[i]]=nodes++;
				node=trie[node][v[i]];
			}
			++cnt[node];
		}
		printf("%d\n",dfs(0,0));
	}
	return 0;
}

I think this problem had weak testcases, as I have seen a lot of O(n^2) solutions that are having an AC verdict. This hasn’t been the first time this happened. Many problems have weak test cases which leads to people optimising the brute solution instead of arriving at the intended one.

1 Like

Solved using heavy implementation! Nice editorial learnt a lot

1 Like

The recursion in your solution is actually similar to my dfs on the trie, just thought of in a different way :slight_smile:

1 Like

For each test case, you do:

memset(trie,0,sizeof(trie)); memset(cnt,0,sizeof(cnt));

That can make your code TLE. Only reset the nodes which you have used.