ENGLISH Video Solution

editorial
,
1

Here it is: ENGLISH Solution - CodeChef January Long Challenge 2020 - YouTube
Commented code: CodeChef: Practical coding for everyone
Trie:
Trie | (Insert and Search) - GeeksforGeeks
Comments, questions, requests, criticism, are all welcome!

24 Likes
2

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
3

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

3 Likes
4

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

5

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
6

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.

8

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

9

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: CodeChef: Practical coding for everyone

10

Your solution fails in the test case below:

abca should be paired with ada

2 Likes
13

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

14

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
15

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

I think the best answer is 30.

3 Likes
16

Now, I got it. Thanks for help.

17

no problem

1 Like
18

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;
}
19

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.

2 Likes
20

Solved using heavy implementation! Nice editorial learnt a lot

1 Like
21
22

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
23

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.