Hi guys, I’m trying to solve this problem. I can understand the purpose of the suffixes and prefixes but I don’t understand how we can know how long they should be and I also don’t understand what is the purpose of keeping the total sum of the interval % 3. In the editorial I see someone posted a solution where they keep the prefixes and suffixes = 3 so why 3 I don’t understand this.
In editorial this is the example code given which I don’t understand the logic behind.
for i = 0 to 2:
for j = 0 to 2:
//if adding suffix of node1 with modulo i
//to prefix of node2 with modulo j
//gives us a subarray divisible by 3
if (i + j) % 3 == 0:
//all pairs of valid indexes are valid subarrays
node3.ans += node1.count2[i] * node2.count1[j]
The logic behind the above code is :-
We store number of prefixes of interval which modulo 3 give i in count1 array and number of suffixes of interval which modulo 3 give i in count2 array.
So suppose we have to merge two nodes n1,n2 into n3,now if we iterate through all possible values of i in n1(i.e. 0,1,2) and j in n2(i.e. 0,1,2) and check (i + j) % 3 == 0 we would get the number of substrings which modulo 3 would yield 0 (suppose that there is only one suffix in node n1 which modulo 3 would yield 2 and there are two prefix in node n2 which modulo 3 would yield 1 then if we combine any of these suffix and prefix we would get a substring which modulo 3 would yield 0)if the condition is true then we can form n1.count2[i] * n2.count1[j] substrings which modulo 3 would yield 0 (since we can combine any suffix of n1 which modulo 3 would yield i and any prefix of n2 which modulo 3 would yield j).
Example=>
Lets say n1 contains string=>“11” and n2 contains string=>“10”.So if we merge n1 and n2 our new string will be “1110”.Now in n1 suffix which mod 3 give 2 is “11”,suffix which mod 3 gives 1 is “1” and there are no suffixes in n1 which mod 3 would give 0,on the other hand in n2 prefixes which mod 3 give 1 are “1” and “10”.So when we combine both the strings there are two substrings which mod 3 gives 0 =>“111” and “1110” (notice that we combine suffix of n1 and prefix of n2).
pls define prefix and suffix in your example.
when does the prefix end and when does the suffix start, is it at n/2?
Lets say you have one range [L,R]. Then, construction of segment tree is centered about the middle value in this range. But suffix and prefix ranges may be any, not necessarily start or end at n/2. They can be any subset of the range [L,R] since their combination will give us the subsequence we want.