GFG Weekly Coding Contest - 164 Post Analysis | GeeksforGeeks Practice

Introduction

Hello everyone, my name is Karan Masu, and welcome to this video where we will discuss the solutions for the weekly coding contest. Let's dive into the breakdown of the questions and solutions provided in this contest.

Question 1: Reach Alice

Description: Bob is in his university hostel where Alice calls and invites him to the cafeteria located at a distance d meters from his hostel. Bob has two options to travel this distance: walking or biking. The objective is to determine which mode of transportation will get Bob to Alice faster.

Approach:

• Bob can walk at a constant speed of x meters per second.
• Bob can ride his bike at a constant speed of y meters per second but loses k seconds due to interruptions from friends.
• We need to compare the times taken by walking and biking:
  • Time taken by walking: (T_1 = \frac(d)(x))
  • Time taken by biking: (T_2 = \frac(d)(y) + k)

Solution:
If T1 is less than or equal to T2, Bob should walk. Otherwise, he should bike. Here’s a simplified implementation in Python:

def reach_alice(d, x, y, k):
    T1 = d / x
    T2 = d / y + k
    if T1 <= T2:
        return "walk"
    else:
        return "bike"

Question 2: Bob's Game

Description: Bob plays a game with his students involving selecting numbers from a board based on a string STR of binary values. Depending on whether the character in the string is '0' or '1', a girl (selects the minimum) or a boy (selects the maximum) will choose a number from the board, respectively.

Approach:

1. Short the array.
2. Use two pointers technique to point to the smallest and largest available numbers.
3. Traverse the string and keep updating the array based on the values (0 or 1).
4. Maintain a result list to keep track of selections.

Solution:
Here’s the implementation in Python:

def bobs_game(arr, str):
    arr.sort()
    min_pointer = 0
    max_pointer = len(arr) - 1
    result = []
    
    for char in str:
        if char == '0':
            result.append(arr[min_pointer])
            min_pointer += 1
        else:
            result.append(arr[max_pointer])
            max_pointer -= 1
    
    return result

Question 3: Beautiful Subarrays

Description: You are given an array ARR consisting of n integers. A subarray is called beautiful if the sum of the minimum and maximum elements of that subarray is divisible by the length of the subarray. The task is to count the number of beautiful subarrays.

Approach:

1. The value of array elements is between 1 and 26.
2. Only check subarrays whose length is between 1 and 52 since the maximum value of minimum + maximum (52) determines that lengths beyond this range can never divide it.
3. For every starting point of the subarray, calculate the minimum and maximum and check the condition.

Solution:
Here’s the optimized implementation to handle large arrays:

def beautiful_subarrays(arr):
    n = len(arr)
    result = 0
    
    for i in range(n):
        min_val = float('inf')
        max_val = float('-inf')
        
        for j in range(i, min(i + 52, n)):  # Check only till max length 52
            min_val = min(min_val, arr[j])
            max_val = max(max_val, arr[j])
            if (min_val + max_val) % (j - i + 1) == 0:
                result += 1
    
    return result

Question 4: Restaurant Queries

Description: A restaurant menu has n items with specified prices. Given several queries of two types, modify the prices accordingly and compute the sum of prices after each query:

• Type 1 (1 x -1): Add x to the prices of all items.
• Type 2 (2 x y): Change the prices of items priced x to y.

Approach:

1. For Type 1 queries: Accumulate additions in a variable to avoid direct manipulation on each item.
2. For Type 2 queries: Use a lookup table (hash map) to keep the count of item prices and process changes efficiently.

Solution:
The implementation is optimized using a hash table and a lazy update approach:

def restaurant_queries(prices, queries):
    total_sum = sum(prices)
    count_map = ()
    add = 0
    
    for price in prices:
        count_map[price] = count_map.get(price, 0) + 1
    
    results = []

    for query in queries:
        if query[0] == 1:  # Type 1
            x = query[1]
            add += x
            total_sum += len(prices) * x
        elif query[0] == 2:  # Type 2
            x = query[1] - add
            y = query[2] - add
            
            if x in count_map:
                count = count_map[x]
                total_sum = total_sum - (count * (x + add)) + (count * (y + add))
                count_map[y] = count_map.get(y, 0) + count
                del count_map[x]
        
        results.append(total_sum)
    
    return results

Introduction

• Transportation Optimization
• Array Manipulation
• Subarray Calculation
• Hash Map
• Lazy Update
• Python Implementation

Introduction

1. How does the lazy update work for handling Type 1 queries in Restaurant Queries?

The lazy update technique involves maintaining an "add" variable that tracks the cumulative additions to each item's price without actually updating the array. This helps in handling multiple update queries efficiently.

2. Why is the subarray length capped at 52 in the Beautiful Subarrays problem?

The subarray length is capped at 52 because the elements' range is between 1 and 26, making their sum maximum 52. Lengths beyond this cannot divide sums in the range of 2 to 52.

3. What is the purpose of using two pointers in Bob's Game?

The two-pointer technique helps efficiently choose the smallest or largest available number from a sorted list as required by the game rules.

4. Why is it necessary to update the list as count_map[x - add] and count_map[y - add] in Restaurant Queries?

These updates reflect the effective counts of elements considering the cumulative additions by Type 1 queries, ensuring accurate modifications and calculations for Type 2 queries.

That's a wrap-up of the solutions and explanations for the GFG Weekly Coding Contest - 164. I hope these insights help you understand and solve similar problems efficiently. Happy coding!