Ninja theater

Hard
0/120
Average time to solve is 45m
profile
Contributed by
3 upvotes
Asked in companies
AppleAmdocs

Problem statement

You have been appointed as the technical lead in the very famous ninja theater. Due to the recent pandemic, all the people inside the theater must follow social distancing. There are ‘N’ seats in a single row in the ninja theater, numbered from 0 to ‘N’ - 1 inclusive. As a technical lead, your task is to find a seating arrangement for ninja theater such that when a person enters the theater, he/she must sit in the seat that maximizes the distance from the closest person.

Note :

1) If the theater is empty, i.e., if no one is in the theater, they sit in the first seat(seat number 0).
2) If there are multiple seats that maximize the distance from the closest person, they sit in the seat with the lowest number.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains a single integer, ‘N’, where ‘N’ denotes the number of seats in a single row in ninja theater.

The second line of each test case contains a single integer, ‘M’, where ‘M’ denotes the number of queries. Here each query can be of two types.

The next ‘M’ lines contain two space-separated integers, ‘type’ and ‘seatNum’, where ‘type’ denotes the query type. For queries of the first type, ‘seatNum’ is -1, whereas, for the second type, it denotes the seat number of the person that leaves the theater.

Note: For every query of the first type, it is guaranteed that at least one seat is empty, and for the query of the second type, it is guaranteed that ‘seatNum’ has a person sitting.

Output Format :

For each test case, for each query of the first type, print ‘K’ space-separated integers denoting the seat numbers that a person should sit to maximize the distance from the closest person. Here ‘K’ denotes the total number of queries of the first type in the current test case.
The output of each test case will be printed in a separate line.

Constraints :

1 <= T <= 5
1 <= N <= 10 ^ 9
1 <= M <= 100
1 <= type <= 2
0 <= seatNum <= ‘N’ - 1

Time Limit : 1 sec

Where ‘T’ is the number of test cases,  ‘N’ denotes the number of seats in a single row in ninja theater, ‘M’ denotes the number of queries, type’ denotes the query type, and ‘seatNum’ denotes the seat number of the person that leaves the theater.

Note :

 You do not need to print anything, it has already been taken care of. Just implement the given function.

Sample Input 1 :

2
6
4
1 -1
1 -1
1 -1
1 -1
7
5
1 -1
1 -1
1 -1
2 0
1 -1

Sample Output 1 :

0 5 2 1
0 6 3 0

Explanation of Sample Input 1 :

Test Case 1 :  
There are 6 seats in ninja theater, and initially, all are empty [null, null, null, null, null, null], where null represents an empty seat.
After the first query, the person sits at seat number 0, [person, null, null, null, null, null]
After the second query, the person sits at seat number 5, [person, null, null, null, null, person], since it maximizes the distance from the person sitting at seat number 0.
After the third query, the person sits at seat number 2, [person, null, person, null, null, person], since it maximizes the distance from the person sitting at seat number 0 and 5 and has the lowest seat number.
After the fourth query, the person sits at seat number 1, [person, person, person, null, null, person], since it has the lowest seat number.

Test Case 2 : 
There are 7 seats in ninja theater, and initially, all are empty [null, null, null, null, null, null, null], where null represents an empty seat.
After the first query, the person sits at seat number 0, [person, null, null, null, null, null, null]
After the second query, the person sits at seat number 6, [person, null, null, null, null, null,  person], since it maximizes the distance from the person sitting at seat number 0.
After the third query, the person sits at seat number 3, [person, null, null, person, null, null, person], since it maximizes the distance from the person sitting at seats number 0 and 6.
After the fourth query, the person sitting at seat number 0 leaves the theater, [null, null, null, person, null, null, person]
After the fifth query, the person sits at seat number 0, [person, null, null, person, null, null, person], since it maximizes the distance from the person sitting at seats number 3 and 6.

Sample Input 2 :

1
8
7
1 -1
1 -1
1 -1
1 -1
2 7
2 3
1 -1

Sample Output 2 :

0 7 3 5 2

Explanation of Sample Input 2 :

Test Case 1 :  
There are 8 seats in ninja theater, and initially, all are empty [null, null, null, null, null, null, null, null], where null represents an empty seat.
After the first query, the person sits at seat number 0, [person, null, null, null, null, null, null, null]
After the second query, the person sits at seat number 7, [person, null, null, null, null, null, null, person], since it maximizes the distance from the person sitting at seat number 0.
After the third query, the person sits at seat number 3, [person, null, null, person, null, null, null, person], since it maximizes the distance from the person sitting at seats number 0 and 7 and has the lowest seat number.
After the fourth query,  the person sits at seat number 5, [person, null, null, person, null, person, null, person], since it maximizes the distance from the person sitting at seats number 0, 3, and 7.
After the fifth query, the person sitting at seat number 7 leaves the theater, [person, null, null, person, null, person, null, null]
After the sixth query, the person sitting at seat number 3 leaves the theater, [person, null, null, null, null, person, null, null]
After the seventh query, the person sits at seat number 2, [person, null, person, null, null, person, null, null], since it maximizes the distance from the person sitting at seats number 0 and 5 and has the lowest seat number.
Hint

Maintain the seat numbers of the persons sitting in the theater in sorted order. For every query of the first type, iterate over this list of seat numbers and find the lowest seat number, which is empty and has a maximum distance from the closest person.

Approaches (2)
Brute Force

The idea here is to maintain a sorted list of seat numbers of the persons sitting in the theater. For every query of type 2, we can directly remove the seat number from our list. For every query of type 1, we will iterate over the list and find the lowest seat number, which is empty and has a maximum distance from the closest person in the theater and place the new person accordingly.

 

Algorithm:

 

  • Declare a list of integers, say ‘seatNumbers’, to store the seat number of persons sitting in the theater in sorted order.
  • Declare an array of integers, say ‘answer’, to store the seat numbers that a person should sit to maximize the distance from the closest person
  • Run a loop over all queries.
    • If the query is of the first type.
      • If the size of ‘seatNumbers’ is 0.
        • Insert 0 into ‘seatNumbers’, as the person will sit on seat number 0.
        • Insert 0 into ‘answer’.
      • Else
        • Declare an integer, say ‘maxDistance’, to store the maximum distance of any empty seat from the closest person and initialize it with a maximum of (distance of the first person from seat number 0, distance of the last person from seat number ‘N’ - 1).
        • Run a loop for ‘i’ from 0 to size of ‘seatNumbers’ - 2.
          • Update ‘maxDistance’ as the maximum of itself and (seatNumbers[i+1] - seatNumbers[i]) / 2.
        • If ‘maxDistance’ is the same as the distance of the first person from seat number 0.
          • Insert 0 into ‘seatNumbers’, as the person will sit on seat number 0.
          • Insert 0 into ‘answer’.
        • Else
          • Declare a boolean, say ‘found’, and initialize it with false.
          • Run a loop for ‘i’ from 0 to size of ‘seatNumbers’ - 2.
            • If (seatNumbers[i+1] - seatNumbers[i]) / 2 is same as  ’maxDistance’
              • Insert (seatNumbers[i+1] + seatNumbers[i]) / 2 into ‘seatNumbers’, as the person will sit on the respective  empty seat.
              • Insert seatNumbers[i+1] into ‘answer’
              • Mark ‘found’ and true and break the loop as we found the required empty seat number.
          • If ‘found’ is false.
            • Insert ‘N’ - 1 into ‘seatNumbers’, as the person will sit on seat number ‘N’ - 1.
            • Insert ‘N’ - 1 into ‘answer’.
    • If the query is of the second type
      • Remove the respective seat number from ‘seatNumbers’.
  • Return ‘answer’.
Time Complexity

O(M ^ 2), where ‘M’ denotes the total number of queries given in the problem.

 

For each query of type 1 and 2, iterating over the list ‘seatNumbers’ takes O(M) time.

Hence, the overall time complexity will be O(M) * O(M), which is O(M ^ 2).

Space Complexity

O(M), where ‘M’ denotes the total number of queries given in the problem.

 

In the worst case, we may have to store the seat numbers for all the ‘M’ queries in ‘seatNumbers’ and ‘answer’. This case occurs when we have queries of only the first type.
Hence, the overall space complexity will be O(M).

Code Solution
(100% EXP penalty)
Ninja theater
Full screen
Console