ENGLISH Video Solution

editorial
,
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.

24

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.

25

ArmyOfMe please

26

Stay tuned, I’m working on it.

2 Likes
27

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

2 Likes
28

Has been posted here: ARMYOFME Video Solution

30

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)

31

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
32

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. :slight_smile:

1 Like
33

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

Any idea why?

1 Like
34

Thanks a lot

35

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. :slight_smile:

1 Like
36

No problem, glad that you learned

37

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.

38

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
39

Test cases were weak.

1 Like