# ENGLISH Video Solution

Also, you need to change

int dfs(int node, int len){

into

ll dfs(int node, ll len){

As the answer could exceed the maximum of int.

Stay tuned, Iâm working on it.

2 Likes

Itâs a feast for all coders
Youâre making long challenge video solutions
Erichtoâs making amazing YT content
Tourist just had his first stream / YT?
Good times

2 Likes

Has been posted here: ARMYOFME Video Solution

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.

Let me know if itâs not clear.

1 Like

Hello @nuttela. Hereâs a possible bug:

`@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.

Hope this helps.

1 Like

Thank you for your effort.
One more fact, my answer always differs by a single digit.

Any idea why?

1 Like

Thanks a lot

Your answer does deviate by more than 1 for many testcases.

Here's an example
``````17
zlewcmdpbqlpzfqr
mvjmmpd
lyypkitmvzlol
mdlwerinizd
g
gokpjyeuxfrynemcnu
xuuonpcdgpbp
nfizvnpg
b
dfsvrk
nslrjqonevvlthlrn
ldlydienecbv
gsikg
snztrequzmwwfcstjmd
nxmxksckdpwdjdobdg
sztmmeokbjou
kaz
``````

your program produces: `1`
correct response: `3`

Unfortunately, the usage of sorting and filtering in the program is not entirely right.

Let's consider the following testcase
``````4
vqfa
zwuol
vxqtkll
vl
``````

I tried to print the contents of `v` and `rv` in every iteration of the `while` loop in `main`.

This is what I found
``````Iteration 0
v:
vl
vqfa
vxqtkll
zwuol

rv:
afqv
llktqxv
louwz
lv

Iteration 1
v:
vl
vqfa
vxqtkll

rv:
afqv
llktqxv
louwz

Iteration 2
v:
vl
vqfa

rv:
afqv
llktqxv

``````

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.

1 Like

No problem, glad that you learned

I thought its greedy so i solved without using trie https://www.codechef.com/viewsolution/28843345 . But i loved the use of trie and modification of string in a way which helps.

https://www.codechef.com/viewsolution/29015440
this approach is totally brute force but accepted.

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.

1 Like

Test cases were weak.

1 Like

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.

the solution is O(n^2) complexity, still it is accepted?[quote=âsom_s_mukherji, post:21, topic:49928, full:trueâ]

[/quote]

Exactly

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

Isnât your code O(n^2)?