ENGLISH Video Solution

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

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.

41

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


[/quote]
42

Exactly

43

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

44

Isn’t your code O(n^2)?