Can Anyone please help me as to how to formula used in this submission came about :
https://www.codechef.com/viewsolution/28546835
Proof/Explaination of the above would be appreciated.
I derived the formula as above,
you need to observe that during Nc2 pairs, many consecutive pairs remain the same or gets changed.
So, i came up with following consider the size of your string is n and index starts from 0 to
n -1(including).
So, there are four cases, you need to consider for every consecutive pair, i.e i and i + 1’th.
-all the pairs ending at i - 1’th.(Therefore, both characters remain same) = Summation of i.
-all the pairs ending at i’th.(Therefore, first character swaps and second remains same) = i + 1
-all the pairs in which both i and i + 1 index are swapped.(THerefore, both character gets swapped) = (i + 1) * (n - i - 1)
-all the pairs starting from i +2’th.(Therefore, both characters remain same) =
id = max( 0LL, n - ( i + 2LL));
afteri = id * (id + 1) / 2;
You can get the above formula’s by checking yourself on pen and paper taking an example.
And then you can make two cases of if both characters are the same or not and add the above four cases respectively.
Here is my submission implementing the above idea -CodeChef: Practical coding for everyone