B. Determining the Number of Unique Lines in a Grid

Given a grid of points defined by coordinates (x, y) where x ranges from 0 to 19 and y ranges from 0 too 20, the objective is to calculate the total number of distinct straight lines that can be formed by connecting any two points.

Implementation Strategy

1. Generate all coordinate pairs.
2. For every unique pair of points, compute the slope (k) and y-intercept (b) of the line connecting them, excluding vertical lines (infinite slope).
3. Use a set to store unique (k, b) tuples, automatically handling dupliactes.
4. The final count is the size of this set plus the count of vertical lines (20 in this grid).

Code Example

# Generate all points in the grid
coordinates = [(x, y) for x in range(20) for y in range(21)]
line_params = []

# Calculate slope and intercept for each pair
for i in range(len(coordinates)):
    for j in range(i + 1, len(coordinates)):
        x1, y1 = coordinates[i]
        x2, y2 = coordinates[j]
        
        # Skip vertical lines (handled separately)
        if x1 != x2:
            slope = (y2 - y1) / (x2 - x1)
            # Intercept calculated using: b = y - k*x
            intercept = y1 - slope * x1
            line_params.append((slope, intercept))

# Count unique lines
unique_lines = set(line_params)
total_count = len(unique_lines) + 20  # Add vertical lines
print(total_count)  # Output: 40257

C. Counting Factor Triplets for a Large Integer

Given the integer N = 2021041820210418, find the number of ordered triples (a, b, c) such that a * b * c = N.

Solution Approach

1. Find all divisors of N.
2. Iterate through all possible combinations of three divisors (with repetition allowed).
3. Count the triples where the product equals N.

Code Example

def count_triplets(num):
    # Find all divisors
    divisors = set()
    for i in range(1, int(num**0.5) + 1):
        if num % i == 0:
            divisors.add(i)
            divisors.add(num // i)
    
    # Count valid triplets
    count = 0
    divisor_list = list(divisors)
    for a in divisor_list:
        for b in divisor_list:
            for c in divisor_list:
                if a * b * c == num:
                    count += 1
    return count

result = count_triplets(2021041820210418)
print(result)  # Output: 2430

D. Finding the Shortest Path Using Dynamic Programming and LCM

Consider a graph with nodes numbered from 1 to 2021. The edge weight between any two nodes i and j (where 1 <= i < j <= i + 21) is defined as the Least Common Multiple (LCM) of i and j. The task is to find the shortest path fromm node 1 to node 2021.

Algorithm

This is solved using Dynamic Programing (DP). Let dp[node] represent the minimum distance from node 1 to node.

• Initialzie dp[1] = 0 and all other dp[i] = infinity.
• For each node i from 1 to 2021, update the distance to nodes j in the range i+1 to i+21 (if j <= 2021) using the relation: dp[j] = min(dp[j], dp[i] + lcm(i, j)).

Code Example

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

def shortest_path(n):
    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[1] = 0
    
    for current in range(1, n + 1):
        for neighbor in range(current + 1, min(current + 22, n + 1)):
            weight = lcm(current, neighbor)
            if dist[current] + weight < dist[neighbor]:
                dist[neighbor] = dist[current] + weight
    return dist[n]

print(shortest_path(2021))  # Output: 10266837

F. Converting Milliseconds to Time Format

Convert a given timestamp in milliseconds since the Unix epoch to a formatted time string HH:MM:SS.

Method 1: Using Python's time Module

import time

def format_time_ms(ms):
    seconds = ms // 1000
    # Convert to GMT time tuple and extract time part
    time_str = time.asctime(time.gmtime(seconds))
    return time_str[11:19]  # Extract 'HH:MM:SS'

print(format_time_ms(1618708103123))  # Output: 01:08:23

Method 2: Manual Calculation

def format_time_manual(ms):
    total_seconds = ms // 1000
    seconds_in_day = total_seconds % (24 * 3600)
    
    hours = seconds_in_day // 3600
    minutes = (seconds_in_day % 3600) // 60
    seconds = seconds_in_day % 60
    
    return f"{hours:02d}:{minutes:02d}:{seconds:02d}"

print(format_time_manual(1618708103123))  # Output: 01:08:23

G. Locating a Number in Pascal's Triangle

Given an integer n, find its first occurrence (smallest position) in Pascal's Triangle. The position is defined as the count of numbers from the top of the triangle to that number, moving left to right, row by row.

Key Insight

For the left half of the triangle, the largest number in each row is at the end. Its first occurrence is at that position. Therefore, we can search diagonally (from the 16th diagonal downwards) using binary search on each diagonal to find n.

Position Calculation

If n is found at row r and diagonal k (0-indexed from the left), its position is: position = r * (r + 1) // 2 + k + 1

Code Example

def combination(a, b):
    """Calculate C(a, b) efficiently, stop if exceeds n."""
    res = 1
    numerator = a
    for denominator in range(1, b + 1):
        res = res * numerator // denominator
        numerator -= 1
        if res > n:
            return res
    return res

def search_diagonal(diag):
    """Binary search for n in a given diagonal."""
    low, high = 2 * diag, n
    while low < high:
        mid = (low + high) // 2
        if combination(mid, diag) >= n:
            high = mid
        else:
            low = mid + 1
    if combination(low, diag) != n:
        return False
    # Calculate position
    pos = low * (low + 1) // 2 + diag + 1
    print(pos)
    return True

n = int(input())
if n == 1:
    print(1)
else:
    for d in range(16, 0, -1):
        if search_diagonal(d):
            break