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.

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.

ArmyOfMe please

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

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){
```

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

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

```
4
vqfa
zwuol
vxqtkll
vl
```

I tried to print the contents of `v`

and `rv`

in every iteration of the `while`

loop in `main`

.

```
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)?