The great game of Galia

Nov. 11, 2017

Introduction

It is the first medium algorithm of Morgan Stanley Campus Codeathon 2017. Now it is 7:38 PM, Saturday evening. I like to spend some time to work on the first medium algorithm.

I like to make this algorithm as simple as possible. Let the fun begin.

Now it is Nov. 12, 2017. It is 12:22 Am. I fully understand the problem statement, and also I like to code something for my contest.

Since the contest will end in Sunday morning 10:00 am, I am better to go to sleep and get up early at 6:00 AM to work on the contest. Now it is 12:47 AM, better to sleep on this algorithm.

Next step 

I woke up 6:30 AM, but I enjoyed the long stay on the bed with music and wechat reading. Now it is 9:32 AM. The contest will end in an hour. I need to work on something.

Read quickly on the algorithm leaf node count on binary search tree. The link is here.

These are steps:
1. Find all sequences
2. Construct binary search tree
3. Count leaf node
4. Add to the sum
5. Evaluate the algorithm time complexity and space complexity
6. Try to optimize

There is timeout issue. So I have to use dynamic programming, using combinatorics, and build a recurrence formula. So the code should be very easy.

Now it is 9:56 AM, the contest is extended to 10:30 AM.

I like to show my worksheet, and it is my way to push myself to work hard on algorithm, no matter how hard it is.