Problem 3 div2
Quick explanation:-This is very easy to solve just get all factors of m in sqrt m time and these all factors are your value of d now you got d you have a and m then you can calculate all valid n.
Problem 4 :-
(Just 10 lines of code)
ans=0;
n= length of string.
Traverse the string a from 0 to n-2 index (0 based index) if a[i]==a[i +1] then do ans +=((n*(n-1))/2 -n that is to include all ranges including both the characters
And if (a[i ] !=a[i +1] ) then simply do ans +=n; that is to include all substrings not including both of these two adjacent indices.
hey…can you explain me your approach to the problem EVIPRO…i have seen many submissions…using the same formula as…yours…I wanted to ask…how do we get this formula…in a brief…!..thanx in advanced.
Hey yeah I figured it out that’s why I deleted my post. I’ll put an in depth explanation in few hours trying to figure out other problems and then will collectively put it
See that if in the string it contains characters like 01 or 10 that is a[I]!=a[I+1] then you have to update all the substrings not containing both of the characters simultaneously that is for example your string is 11011 and currently you consider character at index 3 and 4(0 and 1) then you can get either 0 at 3 or 1 at 4 by updating all substrings starting with index 4 and ending at any index further and similarly you can do for the other half of substrings to get 11 in middle but when you will update substrings say 2 to 5 or 1 to 5 then you will not get desired answer that is it will become 10 again which will be of no use .
Similarly we can go for other part when both adjacent characters are equal and thus you update all substrings containing both the characters.
For those who didn’t understand the formula:
Let string be 001001,
Then as s[0]=s[1],Then this contribute 1 to our answer if they alway get covered by L and R as 11 after flip will give one or never covered by L and R as 00 is also contributing one.
Covering both
L=0 and R={1,2,3,4,5}
Uncovering both
L=2 and R={2,3,4,5}
L=3 and R={3,4,5}
L=4 and R={4,5}
L=5 and R={5}
that’s n*(n-1)/2 contribution always…
Similarly do if(a[i]!=a[i+1]):
All ranges that cover a[i] and not a[i+1]+All ranges that cover a[i+1] and not a[i]=n
I have maintained three arrays…
x which is for a[i]=a[i+1]
b for l and f for r
for every range l and r…
if we are flipping the l to r th digit…
then we should check l-1 with l; This will be done with back array(b).
then r with r+1; This will be done with forward array(f)
