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