Contest Video Solutions by Smart Interviews

Jul 12, 2024

Contest Video Solutions by Smart Interviews

Introduction

  • Discussing solutions for starters 142
  • Topics include penalty shootout probabilities, pizza slicing, solving bitwise problems, and finding specific integers based on factors and primality

Penalty Shootout Problem

  • Problem: Determine if the penalty shootout can end in a draw given current scores
  • Input:
    • Number of test cases T
    • For each test case: integers X (goals by team A) and Y (goals by team B)
  • Output: Yes or No for each test case
  • Approach: Check if remaining goals can equalize scores
    • Team A can score between X to X+2
    • Team B can score Y to Y+1
    • Check if any combination of scores can make them equal
  • Conditions:
    1. X = Y
    2. X = Y + 1
    3. X + 1 = Y
    4. X + 1 = Y + 1
    5. X + 2 = Y
    6. X + 2 = Y + 1

Chef Loves Pizza Problem

  • Problem: Determine cuts required to achieve a specific number of pizza slices
  • Input:
    • Number of test cases T
    • For each test case: integer X representing the number of slices
  • Output: Number of smaller slices for each test case
  • Observations:
    • Pizza cuts add slices incrementally by 2 slices per cut
    • Goal is to have X slices (even number)
    • Number of smaller slices is X - nearest power of 2 less than or equal X * 2
  • Key Calculation:
    • Identify nearest power of 2 by iterating bits

Array Bitwise OR Problem

  • Problem: Find minimum elements to be removed to make OR of array elements equal to 2^x - 1
  • Input:
    • Number of test cases T
    • For each test case: integer n (size of array) followed by array elements
  • Output: Minimum number of elements to be removed
  • Approach:
    • The goal is to get the OR of all remaining elements to be 2^x - 1 (all bits are 1)
    • Tasks:
      • Sort the array
      • Calculate OR in order, check if result equals 2^x - 1
      • Update answer with minimum elements to be removed

Finding Specific Integer Problem

  • Problem: Determine the smallest integer Y with specific properties
    1. Y is not prime
    2. Y is not a perfect square
    3. All factors of Y other than 1 are greater than or equal to X
  • Input:
    • Number of test cases T
    • For each case: integer X
  • Output: Smallest integer Y for each case
  • Solution Strategy:
    • Identify Y by finding prime numbers around X
    • Product of two primes greater than or equal to X meets the conditions
  • Implementation:
    • Check primality of numbers starting from X
    • Compute product of successive primes

Conclusion

  • Solutions for competitive programming problems
  • Example test cases demonstrated and coded out