 # Quick explanations of LTIME79 problems

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.

Happy coding.

4 Likes

I used the same approach for Problem 3 but I got WA on Subtask #2. Were there any edge cases?

Have you calculated factors properly

problem 4 was just combinatorics i see!
I brute forced both solutions but couldn’t optimise either >.<
do you have proof though?

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.

I hope that makes everything clear

1 Like

For those who didn’t understand the formula:
Let string be 001001,
Then as s=s,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

4 Likes

Combination of both that is my explanation and your explanation makes editorial for this problem.

I have simple elegant solution with some basic comments.

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

@mnithinkk
Hey, how are you, long time no see… it’s still not understandable atleast for me  1 Like

Hey bro, I’m good. Too much work. Just participating in contests only. How are you btw

1 Like

https://www.codechef.com/viewsolution/28540589
if u have any doubt you can reply;

1 Like

i simply can’t understand it. can you please refer me some detailed topics for this one?

1 Like

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)

1 Like

No topics it is based on bit of mathematics … and computations …
You willunderstand my code once u try…

thank you for your time. i think it wil take me a while to understand it 1 Like

thanx a lot…buddy…it really became easy to understand …

I think there is a chance of overflow in this problem even with long long, I used unsigned long long for that reason!