I was actually really surprised to see problem E in a mock contest. I have a feeling the desired solution for problem E is based on matrix exponentiation. It lets you solve linear recurrences and Fibonacci is the most obvious of them. Unfortunately we don’t have a tutorial on this topic yet on Toph, but you can google “matrix exponentiation” to find some good write-ups on this.
1 Like
There was problem in Dataset Of Problem B, which was updated later , O(n^2) solution wont pass the updated dataset. You need O(nlog n) solution to pass the updated dataset .
2 Likes
@hjr265
I have already found an O(log n) way to solve the problem.
And @backbencher16
I had already knew that after the dataset being updated, my solve will not be accepted ( i was surprised myself when the solution passed tc, cause (10e5)^2 = 10e10 which means an O(n) submission should not work.
And also I also know that the problem E was not meant to be solved in a O(n) way even without asking arround. Cause even the solves of other participants cannot be seen, the runtime can be. So, I kind of figured it out myself.
That is the reason of mentioning the problem setters so that if they would be kind enough to bestow me (or some of us) some knowledge. Cause it was clear that the problems created much havoc from them also. (after seeing the clarifications)
So, we will be very glad if you kindly explain the solves of problem B and E. (at least those who had problems solving these problems 
)
1 Like
@touhidur: Thanks for your interest in these problems. I and @backbencher16 have authored B, C and E problems of this contest. Actually, I was planning to write a tutorial about Divide and Conquer and I have created these three problems as an example of that.
Anyway, C can be solved using the trick named repeated squaring: https://www.algorithmist.com/index.php/Repeated_Squaring
B can be solved using Merge sort : Merge sort - Wikipedia or by using Fenwick Tree: Fenwick tree - Wikipedia
E can be solved using “Matrix Exponentiation” as @hjr265 has mentioned. This is a good example of Matrix Expo: http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html
In short, these three are three examples of divide and conquer paradigm, a powerful approach to solve difficult problems.
2 Likes
Please write your tutorial quickly and share the link with us.
1 Like
Can you please add my school “Kurigram Government High School, Kurigram”
Can you please add my school “Kurigram Government High School, Kurigram”
Added “Kurigram Government High School, Kurigram”
1 Like