TWOSTRS - Editorial

editorial
, , , , , ,
41

@sharepo Thanks for the explanation. The step 3 in your explanation intends to count the sum of beauties of all occurrences of strings from S in the suffix B[i…∣B∣−1]. I think it should be noted that your implementation additionally counts the sum of beauties of any string from S that ends in the suffix B[i…∣B∣−1] but doesn’t start in it. This works because whenever you have to use the value of suffBSum[i], you would have most definitely included the previous 25 characters before i. Thus, all strings from S that end in the suffix B[i…∣B∣−1] also need to be counted.

42

Thankyou! @sharepo
How could I miss that…
But that explains my last two days of codechef long XD

43

Thanks, fixed.

44

can someone please find error in my implementation. My code is based on editorial. I tried my best to find but could not do it. Please Help

code

45

The setter’s solution is so simple and clear.
I have commented what I have understood. Just posting here so that it will be helpful for someone. Kindly please point out if there are any misunderstanding.

https://www.codechef.com/viewsolution/33075686

3 Likes
46

The error is in calculating suf_sum array.

Change this 
rep(i,0,sr)
{
	ll cur = 0;
	rep(j,i,sr)
	{
		cur = go(cur,r[j]-'a');
		suf_sum[i]+=process_node(cur);
	}
}
to this 
rep(i,0,sr)
{
	last = go(last,r[i]-'a');
	suf_sum[i]+=process_node(last);
}
for (int i = sr - 2; i >= 0; i--) suf_sum[i] += suf_sum[i + 1];

similar to my slution.

1 Like
47

Thanks for the reply man. and yeah you are correct, I got AC after that change and also understood what was wrong with my code. Thanks

48

https://www.codechef.com/viewsolution/33113113

can someone please have a look at my code and point out the mistake? I computed the prefSum and SuffixSum arrays. then i am adding pref[i-25] and suff[j+25]. from (i-24) to (j+24) , i am moving along the automaton.

49

Have a look at this comment above.

50

i did, the test is not working. i have not accounted for substrings inside the set S. thanks for pointing out

51

for(k=1; k<=25; k++){

    for(i=0; i<=(int)B.length()-k; i++){
        struct Node *node = A_trie.get_node(B, i+k-1, k, -1);

        for(j=0; j<A.length(); j++){
            bridge_answers[j][i] += A_trie.get_value(node, A, j, min(26-k, 12), -1);
        }
    }
}

why dont we run 1st loop from k=14. stucked in this logic for few days.

52

1
aaaaaaaaaaaaaaa
bbbbaaaaaaaaaaa
1
aaaaaaaaaaaaaaaaaaaaaaaaaa 200
this case shows 0 as of this code. but ans is 200.
dude stucked is this code for 6-8 days almost. atlast find out why i stucked. brother please fix the code and please elaborate the logic a bit more, hopefully anyone will help.
sorry for my bad english

1 Like
53

@mehe
Ooooopsie! It looks like my code is not working correctly for this and some similar inputs. My code’s output does not match the tester’s output. I think you are correct in what you have pointed out. I did spend a lot of time to write the piece of code that you have quoted. I also faced a lot of confusion and failure to pass all test cases despite multiple attempts.
I am really sorry but since now I know that my code’s logic is still not 100% correct, I don’t think it’s worth explaining it. And I will also have to put considerable effort into remembering my flawed logic.
I would advise you to understand the high-level logic and try developing the code yourself. I hope you could do it better than me.
Good job finding the mistake in my code.
I am sorry for the inconvenience that you had to face because of my incorrect code. That must have been really frustrating.

1 Like
54

your approach is very nice. anyway if you solve this later please attach your code. thanks for sharing your idea.

55

@better_sleep bro could u show me show your complexity is
|A|*|B|*26^2
and also your code plz
I thought like this…
We do this for all pairs of prefix and suffix of A and B respectively
Then considering one particular prefix and suffix we concatenate them…
let it be S
Then i perform kmp on each of the N query strings with S as the text and query string as the pattern
Then the complexity becomes
T * 1000 * 1000 * (N * 1000)
which is way too high
considered 1000 for |A|,|B| and |new pattern(KMP)|

56

Can someone point out the improvement in my code. It is very similar to setter’s code and I am getting TLE in last subtask. Any help will be appreciated.
Sol link : CodeChef: Practical coding for everyone
Thanks in advance