SCB-PA Inter School and College Programming Contest 2019 Mock Contest 1

@ashish_code
I also want to add my school Sylhet Govt. Pilot High School :smiley:

@hjr265
Thanks for adding :slight_smile:

1 Like

Contest start dile “Forbidden” message ashtece

thanks a lots,…

@Guardian1284 It shows that you are in the arena already. Let me know if you are facing any other issue.

how to join as a team?

Please use a regular account for now. Our team functionality is a work in progress and is not quite ready yet for today’s contest.

1 Like

I have already solved all the problems.
Now, if someone have solved the last problem,
Can you discuss about how you have solved it with me?
[Note: I am just interested how others have solved it, knock me at Toph messages. link.]

UPDATE 1: Please share your thoughts with me after the end of the contest.

Discussion while contest is running is not recommended. Please discuss when its ended. Thanks.

2 Likes

Just got excited a little bit.
Thanks.
I have updated the post.

I have somehow or other solved problem B with O( n^2 ) complexity and problem E with O( n ) complexity.
Can anyone share more efficient codes for them? e.g. @hjr265

And also,
@oasis.cse @backbencher16 @TarifEzaz and @whoisshihab
can the problems be explained?
I meant can the solves for all problems be published?

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 :sweat_smile:)

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