The sum of skipped hiding spots

A game involving n players in a circular field with n hiding spots. The ith player starts from the hiding spot given by the expression ((k * i * i + l * i + m) % n) and keeps moving until they find a spot to hide. Determine the sum of all the hiding spots that each player skips over before finding an unoccupied spot.

Examples:

Input: n = 47, k = 0, l = 1, m = 0
Output: 0
Explanation:
For each i, player i arrives at the hiding spot i, and as it is empty, it hides there. No collisions.

Input: n = 47, X = 0, Y = 0, Z = 42
Output: 1081
Explanation:
Each player arrives at the hiding spot 42. Player i will have i collisions before it hides on the spot (42+i) modulo 47.

Naïve Approach: The basic way to solve the problem is as follows:

The problem can be solved using two loops where for each player, we will find the next hiding spot using the nested loop but it results in O(n^2) time complexity. 

Efficient Approach: To solve the problem follow  the below idea:

The efficient approach is the greedy approach. First, insert all the numbers in the range [0, n – 1] into the set. Then for each player find the next hiding spot using lower_bound. If no free hiding spot is found, it shows that the player needs to start from 0. Again use lower_bound to find the first free spot. After the parking spot is found, erase it from the set because this spot is not free anymore.

Below are the steps to implement the above approach:

  • Initialize an empty set ‘occupied_spots‘ to represent the occupation status of each spot. Initially, all spots are unoccupied.
  • Initialize variable collisions to 0 to keep track of all the hiding spots each player skips over before finding an unoccupied spot.
  • Iterate over each player i from 1 to n and for each of them:
    • Initialize the player’s initial hiding spot using the expression ((k * i * i + l * i + m) % n).
    • While the current hiding spot is occupied:
      • Increment the ‘collisions’ variable to indicate that the player has skipped over a spot.
      • Move to the next spot in a clockwise direction using the expression `((current spot + 1) % n)`.
    • Add the current hiding spot to the ‘occupied_spots’.
  • Return the final value of ‘collisions‘.

Below is the code to implement the above steps:

Python3

  

  

  

class CircularHiding:

  

    

    

    def hide(self, n, k, l, m):

  

        

        

        occupied_spots = set()

  

        

        

        collisions = 0

  

        

        

        for i in range(n):

  

            

            

            P = (k * i*i + l * i + m) % n

  

            

            

            

            while P in occupied_spots:

                collisions += 1

                P = (P + 1) % n

  

            

            

            occupied_spots.add(P)

  

        

        

        return collisions

  

  

ch = CircularHiding()

  

collisions = ch.hide(67, 2, 9, 7)

  

print(collisions)

Time Complexity: O(N log N)
Auxiliary Space: O(N)

By Julio MarchiPosted on