Day 52: Competitive Programming Journal

[MyrinNew]

Date: November 15, 2024

Hello Everyone,


Today marks Day 52 of my competitive programming journey. Here’s what I worked on today:


What I Did Today:

I tackled two problems: Find the number of ways to climb n stairs with 1 or 2 steps at a time (Recursion) and Determine if two rectangles overlap on a 2D plane.


1. Find the number of ways to climb n stairs with 1 or 2 steps at a time (Recursion):

Problem:

Given n stairs, find the number of ways to reach the top if you can take 1 or 2 steps at a time.


Explanation:


Use recursion, where the number of ways to reach the n-th step is the sum of the ways to reach the (n−1)-th and (n−2)-th steps.


Base cases:

• If n=0, there is 1 way to stay at the ground (do nothing).
• If n=1, there is only 1 way (1 step at a time).

Implementation:






int countWaysToClimbStairs(int n) {
if (n == 0) return 1;
if (n == 1) return 1;

return countWaysToClimbStairs(n - 1) + countWaysToClimbStairs(n - 2);
}







2. Determine if two rectangles overlap on a 2D plane:

Problem:

Given two rectangles on a 2D plane, determine if they overlap.


Explanation:


Two rectangles overlap if they have a common area.

Conditions to check for overlap:

• One rectangle is to the left of the other (i.e., right edge of one is left of the other’s left edge).
• One rectangle is above the other (i.e., bottom edge of one is above the other’s top edge).

Implementation:






struct Rectangle {
int x1, y1, x2, y2;
};

bool isOverlap(Rectangle r1, Rectangle r2) {
if (r1.x2 if (r1.y2 return true;
}







Reflection:

Today’s problems tested recursion and condition-checking. The climbing stairs problem with 1 or 2 steps was an insightful use of recursion, while the rectangle overlap problem required geometry-based checks and simple logical conditions. Both exercises improved my understanding of recursion and basic geometry.


Stay tuned for more updates, and happy coding!




More...