Blog

First of all, we are talking about Mathematics. Not Induction in Physics and Logic, although the latter is related to Mathematical Induction to some extent.

So what is Mathematical Induction? Induction here means to argue the proposition for a small case and then reuse it for a more complex case. To be precise an “Induction” proof must be done in a specific format. But in a very vague sense, you are proving by using simple cases inductively (in literal meaning) to argue the final goal statement. Let’s explore the example below.

Consider a chessboard and an L-shaped domino. How can you place some dominos onto the chessboard so that there is 1 specific uncovered cell (i.e. others fix one random cell which you cannot cover it)? It is trivial as you can place the domino in whatever position and it automatically leaves only 1 empty cell.

Then how about a chessboard? Can you place some dominos onto the chessboard so that there is only 1 uncovered cell too? You can try to do this in your own way. But here we want to do it in a more systematic way so that we can “reuse” the logic in the latter part. We can divide the board into 4 equal parts, that is 4 boards. As we know whenever we have a chessboard with 1 specific empty cell, we can still cover the remaining 3 cells with an L-shaped domino. Therefore, we can cover the middle with an L-shaped domino, then we have 3 chessboards with 1 blocked cell near the centre (blue crosses) and 1 chessboard with 1 preassigned empty cell (red cross).

Then how about a chessboard? We can reuse the logic as above. If we can do so for a chessboard, then for a chessboard, we can divide the board into 4 chessboards. Then we cover the centre with an L-shaped domino. It leaves us 3 chessboards with 1 blocked cell near the centre and 1 chessboard with 1 preassigned blocked cell, which all of them can be covered by some combinations of L-shaped dominos, as we can do it for any board as we assumed.

So why the proof is already complete? It is because we have proved for the case of (i.e. a chessboard), then by above, as whenever we can cover any chessboard with 1 specific empty cell (i.e. the case for ), we can cover a chessboard with 1 specific empty cell (i.e. the case for ).

In other words, if we have the case for , then we know the case for is also true.

Therefore, we can do it for the case of , and hence the case of , and so on for .

Hopefully, you can see this method is powerful to prove any statements related to positive integers. Formally, the principle of Mathematical Induction is as follows.

A statement is true for all positive integers if

1. that statement is true for (base case) and,
2. assuming that statement is true for , then that statement is true for (inductive step).

It is often described as the domino effect. To use only the base case and then repeat the inductive step, the statement is shown to be true for and so on.

The standard example of using such a principle is to show for all positive integers . If you are new to induction, you can try to follow the following steps.

1. Show the statement is true for (base case):
   Verify
2. Assuming that statement is true for , Show that the statement is true for (inductive step):
   It is given . If we add onto both sides, can we verify ?

It is too standard that you can even Google the answer directly. But it is always good to try it yourself first.

Although Mathematical Induction often associates with natural numbers, you can use it for negative numbers (by replacing by ) or even rational numbers in some cases (by using the base case and the inductive step from to ).

There are also different versions of Mathematical Induction, such as “Strong Induction” and “Backward Induction”. You can search these terms for more information.

It is very useful when you want to argue statements with discrete variables in Mathematics as well as Competitive Mathematics. Let’s do 2 examples.

Problem 1

Find a function which with . (Note that represents the set of all natural numbers. For the context here, we assume it means all positive numbers.)

To use induction to prove a formula, we need to first guess a plausible formula for . For a valid formula, it must be able to produce a after the squaring (and then multiplying by 2). One of such expression may be , which you may recognise similar technique in a question like “Find the value of if “.

However, . To transform to , we use and get .

Now, to make the form become and become , we employ the exponential function, namely substituting , we indeed get with .

To find , by , we need . By solving, we get . Hence, .

Finally, we get .

You may wonder what is the role of Induction here. The answer is simple, after getting the formula, as we just guess the answer, we must show that the expression is really valid for the condition. Induction is the formal way to go, which is left as an exercise for readers.

Problem 2 (Source: https://math.stackexchange.com/questions/850377/for-every-positive-number-n-there-exists-a-n-digit-number-having-all-odd-di)

Prove that for every positive integer , there exists an -digit number which is divisible by  and all digits are odd.

You can try it for some small numbers. You should get , which all you need to get the next number is to add an extra digit in front of the previous number.

It is a strong signal that we can really use induction here. For , it is trivial as the number 5 is an (only) example. Now assume the statement is true for , where is a positive integer. Namely, we have a -digit number where all digits are odd. To add an extra digit, we add , where = 1, 3, 5, 7 or 9. (Note: This is the ^th digit, not ^th) We want to make the number divisible .

Therefore, we have . As 5 is a prime, we have . It is the same as solving the linear congruence equation in mod 5, for known numbers of . We know that such odd always exists by the Bézout’s identity.

We have seen some examples showing that time Induction is useful. But do not abuse it. We will see why in a future blog.

Supposed that we are tasked with designing a SORTracker system that can stores collection of name and attractive score. The attrativeness score of a location will determine it’s ranking in the system, if two location have same score, then will compare lexicographical order to determine the order. The system support two operation.

1. Adding: scenic locations, one at a time.
2. Quering the ith best locaion of all locations already added

In order to effciently implement the above class, we may need a data structure that store scenic data, and with a way for ranking the existing data also support with dynamically add new location, then lastly, it needed to be effciently looked up as well.

We may examine the existing tools we had in C++ library,

1. vector, a dynamic array. Clearly we unable to use due to linear complexity for inserting new element.
2. set, a balanced tree. Support adding, while c++ do not support look up indexed element in set
3. unordered_set, hash map. Unordered, not able to provide a rank for each element.
4. priority_queue, heap. Support O(1) adding but also do not support look up indeded element.
5. queue, stack, not so much useful neither.

As we can see from the above analysis, none of the C++ native container can fulfill the requirement of this system. While there do exist more advanced data structure that is able to accompoish the same task, the implementation time would be a significant concern, would be a deal breaker for a competitive programmer in a contest.

We can observe the native container, suppose that we have implemented a balanced tree our own, it should be an easy task for us to quering the ith element. This is where policy-based data structure come in handy, they are powerful tool that can customize the existing behaviour of standard container in c++. One of such example is the “ordered set” that while keeps the unique elements in sorted state, additionally suipport two log(n) operation as below

1. order_of_key(k): number of element strictly smaller than k
2. find_by_order(k): the kth element in a set.

In order to use Policy Based Data Strcuture, we first include the necessary header

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;

The assoc_container adds more flexibility and customization to native class such as set and map, while tree_policy define policies for customizing behaviour of tree-based container. For example, “whether to allow duplicates, and nodes count stored in tree node”. The namespace is just requirement by pbds.

The policy for ordered_set is tree_order_statistics_node__update. The detail of implementation isn’t so important to understand, as we only interest in the above two index looking functions. In short, this can be achieve by storing the children nodes countf as node’s attribute in a balanced tree, is will enable fast looking up for the k-th element, (log(n) time). It would very simple binary search operation and left for reader to think about how to do so given the node count.

typedef tree<
  int ,
  null_type,   
  less<int>,   // Customizable
  rb_tree_tag, // Red-black tree used in underlying implementation
  tree_order_statistics_node_update
> ordered_set;

And a possible use scenrio would be like

ordered_set Set;
set.insert(3);
set.insert(5);
set.insert(1);

// order_of_key(x) returns the number of items in a set that are strictly smaller than x; or equivlently, the index of the first item greater or equal to x
Set.order_of_key(nums[i]);

// find_by_order(k) returns an iterator to the k-th largest element (counting from zero), 
Set.find_by_order(nums[i]);

As the end, if you are python coder, then there is ordered_set. (Yea you prob dont need to read this article).

Here are some useful link, if want investigate more

• The official documentation: https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/
• A tutorial on Codeforces: https://codeforces.com/blog/entry/11080

A factor of a positive integer is another positive integer which divides . A relatively simple concept, yet one that has fascinated and tormented mathematicians for centuries. How can we quickly factorise a number?

One practical method is trial division: given an integer we want to factorise, we loop from to and repeatedly check if its a factor: if so, we divide by the number as many times as possible, add it to our list of factors and continue. In the worst case, we must search every number up to (if is prime): this can be improved by only checking numbers up to (an exercise for the reader!).

There are other deterministic methods for factorising integers (i.e. ones which will definitely return all factors within a finite amount of time). However, there are also probabilistic methods for computing factors which, although do not guarantee factors, generally fare much better than deterministic ones as they are much likelier to return factors.

Let’s take a look at Fermat’s little theorem for a moment: it states that for any prime and integer which is not a multiple of , (check out CPMSoc’s number theory workshop slides to see a proof of this!). Further note that for any integer ,

Our goal now is to somehow generate an integer which is a multiple of for some prime factor , so that we can guarantee . We can then use the Euclidean algorithm to find a common divisor between and (this was also covered in CPMSoc’s number theory workshop), and thus generate a factor! One important requirement is that should not be divisible by all of the prime factors, otherwise which is not new information. Something to be aware of is that some integers can result in being a multiple of a prime even though is not a multiple of . This is OK, and in fact means we can return a factor even earlier if we find such a ! A practical implementation of this is shown below in Python:

from math import gcd
import random
import sympy

# WLOG we want factorise to return a nontrivial
# factor of n (we then recursively call factorise
# on this number)
def factorise(n):
    if n == 1 or sympy.isprime(n):
        return [n]
    while True:
        a = random.randint(2, n - 1)
        g = gcd(a, n)
        if g != 1: # we've already found a factor of n
            return factorise(g) + factorise(n // g)

        x = a
        # our v is generated with a factorial
        # i.e. we check gcd(a**(b!) - 1, n)
        for b in range(2, n):
            a = pow(a, b, n) # exponentiation to factorial (mod n)
            common_divisor = gcd(a - 1, n)
            if common_divisor == n: # bad value of a, or another issue...
                break
            elif common_divisor != 1: # found factor of n
                return factorise(common_divisor) + factorise(n // common_divisor)
        else:
            return [n]
    
n = int(input("Enter your number: "))
print(f"Factors of {n}: {factorise(n)}")

This is Pollard’s p – 1 algorithm (most implementations, however, limit the factorial up to a certain integer, called the “smoothness bound”). There are some issues, however. For one, because we generate with a factorial, there are some annoyances: for integers where, for each prime factor , all have the same largest prime factor, call this , then when , , making it a lot less likely for a not equal to to be achieved earlier. A more prominent issue concerns time complexity: for integers where the largest prime factor of is not easily attainable via a factorial, this algorithm takes too long to generate an appropriate . Perhaps we can find a structure different to exponentiation?

Well it turns out considering finite elliptic curves helps us! Elliptic curves are equations of the form , and finite elliptic curves are such equations but studied under a modulus.

Before we get into the maths, I’ll explain why using elliptic curves is better than traditional exponentiation: we are about to define a notion of addition in the elliptic curve’s space of solutions, which will cyclically generate new elements. Importantly, while the size of the cycle for exponentiation was, at most, , the maximum size of this cycle on an elliptic curve varies seemingly randomly between and (this is known as the Hasse-Weil bound). This means that its running time is not tied down by the largest prime factor of a single number (Pollard’s algorithm was tied down by ‘s largest prime factor).

Elliptic curve addition of two points (in the continuous case) is defined by forming a line between the two, finding the third point of intersection and reflecting the point across the x-axis (the new point is the result of the addition, and will always be on the elliptic curve). If the same point is added to itself, then we consider the tangent line. Note that if a vertical line is generated, then the resulting point is defined as “infinity”. An example of this is shown below:

Finite elliptic curve point addition involves the same numerical calculations, but calculated under , with division defined as multiplication by the divisor’s inverse. Now we are ready. We pick a random elliptic curve under and a point on it by picking random integers and , and setting . Then, for increasing values of , we calculate the point addition of with itself times (this can be done efficiently by adding the previously calculated value times). In this process, if we ever get an infinity point, we must’ve performed modular division with a value where , as this is the only scenario where a unique inverse does not exist, in which case we can stop early since we’ve already found a factor of .

In fact, we must eventually pass an infinity point! If we repeatedly point-add , then, for some prime factor , under there are only a finite number of values, so we will form a cycle and eventually loop back to our starting point. Note that the last value in this cycle (before it loops around) must be the identity element of the elliptic curve, which is the infinity point, since this is the only one which results in when point-added to . Thus, if the we generate becomes a multiple of some of the point-addition cycle lengths, then the repeated addition of times must be the infinity point! Realise that this algorithm is essentially just an improved version of Pollard’s algorithm, using a different structure (elliptic curves) but the same principle (systematically trying to create multiples of only some of the prime factors of ).

Note that instead of calculating factorials all the way up to , we calculate them up to a smaller “smoothness” bound , and randomly choose another curve and point on it if we don’t get to an infinity point. This is so we can actually exploit the seemingly random variance of elliptic curves’ cycle lengths.

Congratulations, you’ve discovered Lenstra’s Elliptic Curve Method for factorisation, the third fastest in the world! Only required a bit of number theory, right?

From “Competition Mathematics 101”, you may see that Competition Mathematics has approachable academic content but with a peculiar question style. But everyone with sufficient training can become a semi-supernatural being able to tackle those problems.

Here is an introductory question. It is question A1 in Simon Marais Mathematics Competition 2022.

Let ABCD be a unit square, and let P be a point inside triangle ABC. Let E and F be the points on AB and AD, respectively, such that AEPF is a rectangle. Let x and y denote the lengths of  AE and AF, respectively. Determine a two-variable polynomial f(x,y) with the property that the area of AEPF is greater than the area of each of the quadrilaterals EBCP and FPCD if and only if f(x,y) > 0.

If you find the wording weird, you are perfectly normal, and so am I! It is often useful to represent a Geometry question with a diagram.

Then you can see the wording describes two properties:

1. Quadrilaterals EBCP and FPCD are trapeziums. Their areas can be computed by the formula you learnt before.
2. P lying inside triangle ABC makes the area of EBCP less than that of FPCD.

The question remains

What is a two-variable polynomial f(x,y) with the property if and only if f(x,y) > 0? 

Let’s look at a similar phasing.

Find a polynomial that k is greater than h if and only if that polynomial > 0.

So we have k > h. To make the right-hand side 0, we need to have k – h > 0. So k – h is the target as it is coincidentally a polynomial. Therefore, the technique of solving this problem is literally translating the weird question phasing to inequalities. Indeed, as the area of EBCP is always less than that of FPCD, we have

So we have .

You may still wonder the following. Let me explain them one by one.

1. Two-variable:
   You already have x and y, so you cannot introduce a third variable.
2. Polynomial:
   A polynomial means you can just have some real numbers and variables, and then add, subtract and multiply them together. Here, the term does not make the question more difficult. However, if you get something such as , then you need to make it becomes .
3. Property:
   It means some conditions. But you are solving a mathematics problem so you have some conditions. This term is conceptually useless here.
4. If and only if:
   It means you need to have a necessary and sufficient condition. You need to go through some chapters in logic and arguments in Mathematics courses in order to fully understand it. Now, you can treat “A if and only if B” as “if A then B” and “if B then A”. For example, water boils if and only if the water reaches its boiling point.

You may feel that sometimes the difficulty of Competition Mathematics is not the content. I am sure you can do this problem if it is phrased as “Find an inequality in x and y makes the area of AEPF greater than the area of each of the quadrilaterals EBCP and FPCD”.

To practice, please do this simple arithmetic problem. You may see similar questions in high-school Mathematics Competition, but it is helpful for beginners to understand the thinking process in competition.

Calculate the value of

where [x] is the floor function, i.e. the largest integer smaller or equal to x. For example, [1] = 1, [3.2] = 3, [– 4] = – 4 and [– 4.3] = – 5.

Here are some hints if you really need them.

1. Prove by induction (in most competitions, the result is too standard, so you do not need to prove it. However, for beginners, it is a good basic exercise.)
   .
2. For a given positive integer p, solve, for x,
   .
   
   Answer:
   It is
   
3. How many of k makes:
   ?
4. Expand p(2p+1).
5. Note that:
   
6. The answer is:
   59686

Question 2: Binary Help

Your computer has forgotten binary and it needs your help to do a calculation! Luckily, the computer only needs help with calculating integers, and you won’t have to worry about any decimals.

To help the computer, you need to find the next largest power of 2 after the computer’s number.

Solution

To find the next largest power of 2 after N, one can check every ascending power of 2 until a power of 2 is found that is larger than N. This algorithm has a time complexity of O(log N), as N is up to a maximum of 10^18, which is approximately equal to 2^60.

Question 3: Counting Rectangles

While doodling in your maths grid book, a friend comes up to you and draws a large rectangle on your page. The rectangle follows the lines of the page, so that it bounds a a W by H grid of squares. Your friend challenges you to count the number of different grid-aligned rectangles you could draw inside theirs. For example, these rectangles are valid:

Solution

Brute force – count every possible top, left, bottom, right edge of rectangle. An idea of implementation is to iterate through each coordinate as 4 points and count if it’s a valid rectangle. There would be optimization can be made however it does the job.

def count_rectangles(a, b):
    count = 0
    for top in range(a):
        for left in range(b):
            for bottom in range(top + 1, a + 1):
                for right in range(left + 1, b + 1):
                    count += 1
    return count

Maths approach –

For the left and right edges, there are W + 1 possible choices for the left edge and W possible choices for the right edge (since the right edge can be to the right of the rightmost square). To avoid duplicate count, we divide it by 2.

Similarly, there are (H + 1) H choice for picking an edge for height. Result then be WH(W+1)(H+1))/4.

Question 3: Burger

Since becoming the best chef in all of Melbourne, he’s faced tough competition from others vying for his place. One challenger has been gaining popularity with a sort of circular sandwich, made with buns instead of bread. Not to be outdone, Michael has decided to make the perfect circular sandwich.

To achieve this goal, Michael starts with a rectangular slice bread measuring W mm by H mm. From this slice, he must cut out two identical circles to form the top and bottom of his sandwich. Since integers are the most perfect numbers, the circles must have an integer diameter.

Write a program to help Michael find the diameter of the largest pair of circles he can cut out of the slice of bread.

Solution

The solution involve bit knowledge of geometry, and some of common sense. First of all, by drawing the situation out, we can observe a relationship between radius and H, W. Follow this equation, there will be a method to derive a mathsmatical formula for the solution.

The programming approach would uses binary search to find the largest value of d such that the rectangle can fit inside the grid.

def can_fit(d, W, H):
    if d > W or d > H:
        return False
    elif d**2 > ((W-d)//2)**2 + ((H-d)//2)**2:
        return False
    else:
        return True

def find_largest_circle(W, H):
    l, r = 1, max(W, H) + 1
    while r - l > 1:
        m = (l + r) // 2
        if can_fit(m, W, H):
            l = m
        else:
            r = m
    return l

W = int(input("Enter the width of the grid: "))
H = int(input("Enter the height of the grid: "))

largest_radius = find_largest_circle(W, H)

print("The largest circles that can fit in the grid has a side length of", largest_radius)

Question 4 Gerrymending

For this question I do not include description, click this link to view.

Motivation

This question is referring to a scenario where there are two candidates and we need to find the segment where one of them is leading the other. By mentioning the term “segment”, it hints towards the possibility of multiple ways to solve the problem.

• One possible approach is the “divide and conquer” method where we divide the problem into smaller subproblems and then solve them.
• Another approach is the “prefix array” method, which is useful when the situation is static. It help us to find interval’s info more effciently.
• Lastly, the “binary search” method may be used to find the start and end of the segment or to find the maximum difference and verify between the two candidates.

Prefix array is the most straightforward and plus this question doesn’t looks complicate. The reason being, it allows us to compute the number of votes for each candidate in any segment of the line in constant time, i.e., O(1) time complexity.

If we define A’s weight to be 1, and B’s weight to be -1 so that it cancel each other, then our task is to finding a contiguous subarray with the largest sum (represent A*1 + B * -1 = A – B!!!).

We use the prefix minima to find the smallest value seen so far in the prefix sum array, which represents the minimum value of any sub-array that within index i. By subtracting this value from the current prefix sum, we can get the maximum value of any sub-array that ends at index i. The maximum sub-array interval occurs when the prefix sum is at its highest and the prefix minima is at its lowest. So, we use the formula “max(prefix sum – prefix min)” to find the maximum sub-array interval.

def max_subarray_interval(line):
    prefix_sum = 0
    prefix_min = 0
    max_diff   = 0
    curr_diff  = 0

    # iterate over line
    for i, c in enumerate(line):
        # update vote counts
        counts[c] += 1

        # update prefix sum and prefix minima
        prefix_sum += (1 if c == 'A' else -1)
        prefix_min = min(prefix_min, prefix_sum)

        # calculate current difference and update max difference
        curr_diff = prefix_sum - prefix_min
        if curr_diff > max_diff:
            max_diff = curr_diff

    # determine winner
    winner = 'A' if counts['A'] > counts['B'] else 'B' if counts['B'] > counts['A'] else 'BOTH'

Question 5 Shape

For this question I do not include description, click this link to view.

Motivation

This question is about make observation, according to the constraint.

• The shape is symmetric, so we only need to focus on one quadrant (top right for example)
• At least one square along the top row needs to be filled to make the shape the correct height, and everything between them must be filled as well
• Top left corner of the quadrant must also be filled, as well as the bottom right corner
• The entire left column and bottom row must be filled as well (so its convex)

• Then precede, we would like to find valid ways to build the empty hole at the top right as shown in above image.
• The problem becomes: find a path from the top left to the bottom right of the
  grid, moving only right and down
• At here, suppose that we pick a cell at the middle, suddenly we see that there are additionally square need to be filled.

• Beside that, to satisfy diagonal constraint, we will see more square needs to be filled

• Another observation would be, after moving two steps down in a row, we can no longer move two steps right.

The solutuib uses dynamic programming to count the number of valid and convex shapes in a grid. The algorithm iterates over every cell in the grid using two nested loops, and for each cell, it computes the number of valid and convex shapes that can be formed with that cell as the top left and bottom right as shown above.

a_right[0][0] = 1

for i in range(R+1):
  for j in range(C+1):
    if j > 0:
      a_right[i][j] = (a_right[i][j-1] + a_down[i][j-1]) % mod
      b_right[i][j] = (b_down[i][j-1]) % mod
    if i > 0:
      a_down[i][j] = (a_right[i-1][j]) % mod
      b_down[i][j] = (a_down[i-1][j] + b_right[i-1][j] + b_down[i-1][j]) % mod
        
def solve(r, c):
  return (a_right[r][c] + a_down[r][c] + b_right[r][c] + b_down[r][c]) % mod

print(solve(R, C))

Thank you for participating in the OWeek quiz – we hope you had fun! We look forward to hosting more quizzes and articles throughout the year.

Question 1

Bob and Alice are looking for the cheapest way to purchase tickets for a cross-country train ride that they have planned. They are considering a 1-day, 7-day, or 30-day pass, each with a different price.

We can use simple recursion to write a program to solve this problem. Recursion is a programming technique that refers to a process in which a function calls itself repeatedly, for this problem we can define a function takes current days and it returns the minimum cost for travel rest of days.

# - travel stores days of travel
# - cost stores the cost of each ticket
def mincostHelper(travel, costs, currDate, endDate):
    # Base case: 
    # As current date great than endDate, there is no need to travel anymore, it took 0 to complete the journey
    if currDate > endDate:
        return 0
    
    # Recursive case
    # Always return the minimum cost for travel the rest of days
    if currDate not in travel:
        # Skip this date
        return mincostHelper(travel, costs, currDate + 1, endDate)
    else:
        return min(
mincostHelper(travel, costs, currDate + 1, endDate) + costs.oneDay, 
mincostHelper(travel, costs, currDate + 7, endDate) + costs.sevenDays,
mincostHelper(travel, costs, currDate + 30, endDate) + costs.thirtyDays
       )
        

We can use Dynamic Programming (DP) to optimize our solution. DP is a technique that involves breaking down a problem into smaller sub-problems and storing the results of those sub-problems. It is primarily used to optimize problems where the solution can be decomposed into independent subproblems.

For this problem, we will make an array dp[i] that stores the cost of fulfilling a travel plan from day i to the end of the plan. If we have to travel on the ith day, we have three options: we can buy a 1-day pass (dp[i+1]), a 7-day pass (dp[i+7]), or a 30-day pass (dp[i+30]). We will choose the option that gives us the minimum cost, that is, the minimum of dp[i+1], dp[i+7] and dp[i+30]. If we don’t have to travel on the ith day, then we will not buy any pass and the cost is zero.

We only need to do a slight change to the above code, it then will save us a lot of repetitive computation,

# - travel stores days of travel
# - cost stores the cost of each ticket
# - dp[i] = minimum cost to travel rest of days from day i
def mincostHelper(travel, costs, dp, currDate, endDate):
    # Base case: 
    # As current date great than endDate, there is no need to travel anymore, it took 0 to complete the journey
    if currDate > endDate:
        return 0

    # Check if result is stored 
    if currDate in dp:
        return dp[currDate]

    # Recursive case
    # Always return the minimum cost for travel the rest of days
    if currDate not in travel:
        # Skip this date
        dp[currDate] = min(dp[currDate], dp[currDate - 1])
        return mincostHelper(travel, costs, currDate + 1, endDate)
    else:
        dp[currDate] = min(
mincostHelper(travel, costs, currDate + 1, endDate) + costs.oneDay, 
mincostHelper(travel, costs, currDate + 7, endDate) + costs.sevenDays,
mincostHelper(travel, costs, currDate + 30, endDate) + costs.thirtyDays
       )
        return dp[currDate]

        

Time Complexity: O(T) where T = maximum numbered day in travel plan. In our DP solution, we ask maximuly T questions, and each question can be answered in O(1) time knowing answer from other questions.

Space Complexity: O(T)

Question 2

Bob and Alice is looking for an optimized solution to store suicase into warehouse.

We can make several observations towards this question. Firstly, the goal is to get as many boxes inside the warehouse and the size of the box does not matter. Secondly, if there is a narrow section of the warehouse, even if it becomes wide afterwards, the boxes will still get stuck right before it. This is due to the fact that the boxes will not be able to fit through the narrow section, thus resulting in a bottleneck situation. Thirdly, it is common sense to assume that if a small box gets stuck, then bigger boxes will also get stuck.

From above observation, we seems able to construct a Greedy Solution toward this problem. Greedy algorithms are a type of algorithm that makes localized decisions in order to optimize a global goal, it make optimal decisions at each step, according to a specific set of rules, and always aim to make the best decision at that moment in time. Greedy algorithms may not exist in some cases, and if we want to use it to solve a certain question, we would need to prove it. On the otherhand, the technical Dynamic programming we used in first question examine all possible situation, thus give the optinmal solution.

We propose, by insert the boxes in acending order, we can always reach most optimized solution. To show our proposal is correct, we prove by contradiction (a high school maths technique!??).

We propose, at a certain step where we insert the boxes, we can get an optimzied solution if we choose to insert a larger box than the smallest box we have. There are two situation we have

• If the larger box we choose stuck eariler in the “bottleneck” situation we described earlier. Than it’s always worse than we insert the smallest one first and the largest box.
• If the larger box stuck at the same place as the smaller box, it means the warehouse’s height before that place are greater than larger box, and thus greater than smallest box. In this case, it does not matter if we put smallest first, or the larger one.