Can anyone provide a test case in which my solution fails?
Code : here
I have taken the array of strings and sorted them.
Both from front and back.
Now, I try to match them with the string next to it,
For example :
a → 1
aaaa-> 1
aba-> 3
aba-> 0
In the example, a and aaaa has 1 as result, aaaa and aba has 1, aba and aba has 3
I consider them if the the number associated to it is greater than the next, we consider it.
We keep doing this, till we have a single string.
We do the same process for reversed strings as well.
The result is the maximum.
I have done the reverse, because of cases like this:
aaa
aab
aba
Note : I got a partial 50 pts using this approach (sub task 1)
Here is another very similar approach.
Use a special trie, in this trie each edge is labelled using a digram(2 letters instead of one).
Now let’s say we wish to insert abcde in the trie:
From root follow edge ae then follow edge bd, Finally follow edge cc.
Do a DFS on this trie, the number of strings at the deepest level get combined first and strings with less common parts get combined later.
@lines 48, 56 - @lines 50, 58 when k = m1 - 1 and k = m2 - 1, you’re trying to access elements v[m1] and rv[m2] whereas v and rv are m1 and m2 in size. Maybe you meant:
for (int k=0;k<m1-1;++k){
for (int k=0;k<m2-1;++k){
Here's a random testcase for which your program produces an incorrect output
9
zlvqv
mn
uzeskzil
dvvarlgvsq
i
efqisjyse
zsidjoj
zbmutdryj
vwj
correct response: 1
incorrect response: 0
EDIT: This submission of yours did not get a partial 50. This did and it too fails in producing the correct output to the same testcase I mentioned above.
You see, whenever we sort the filtered contents of v and rv, the only 2 words capable of forming pairs (i.e., vxqtkll and vl in this case) have at least 1 word in the way. Hence, when you’re pairing them (greedily) by considering only adjancent strings you’re missing their contribution.
I thought its greedy so i solved without using trie CodeChef: Practical coding for everyone . But i loved the use of trie and modification of string in a way which helps.
But during contest i thought that this approach should give tle when all elements are distinct (duplicate strings are not there). So i don’t tried this.
I think setter should give this type of test case,so that everyone should try this question by only by trie.
Yea, the case with all distinct strings is really important for any problem.
Either that, or the constraints were a bit small. Each word has to be on average 4 characters long in order for all words to be distinct. This means that you only get around 25000 distinct words. Although some O(n^2) solutions might pass, I don’t think the solution above seems optimized enough.
I’ve tried this during the competition and I don’t understand why there are some RE and TLE tasks. Can I improve this solution in any way? Thanks in advance! My solution
