Recent CP News

Little Monk and Goblet of Fire || Medium Problem

Let’s try to beat deadly competition for Goblet of fire by using Queue (;

Albus Dumbledore announced that the school will host the legendary event known as Wizard Tournament where four magical schools are going to compete against each other in a very deadly competition by facing some dangerous challenges. Since the team selection is very critical in this deadly competition. Albus Dumbledore asked Little Monk to help him in the team selection process. There is a long queue of students from all the four magical schools. Each student of a school has a different roll number. Whenever a new student will come, he will search for his schoolmate from the end of the queue. As soon as he will find any of the schoolmates in the queue, he will stand behind him, otherwise, he will stand at the end of the queue. At any moment Little Monk will ask the student, who is standing in front of the queue, to come and put his name in the Goblet of Fire and remove him from the queue. There are  operations of one of the following types:

  • : A new student of school  whose roll number is (1≤y≤50000) will stand in a queue according to the method mentioned above.
  • : Little Monk will ask the student, who is standing in front of the queue, to come and put his name in the Goblet of Fire and remove him from the queue

Now Albus Dumbledore asked Little Monk to tell him the order in which student put their name. Little Monk is too lazy to that so he asked you to write a program to print required order.

Note: Number of dequeue operations will never be greater than enqueue operations at any point in time.

Input Format:

The first line contains an integer  ), denoting the number of operations. Next,  lines will contain one of the  types of operations.

Output Format:

For each  type of operation, print two space separated integers, the front student’s school, and roll number.

SAMPLE INPUT

5
E 1 1
E 2 1
E 1 2
D
D

SAMPLE OUTPUT

1 1
1 2

Explanation

After the first operation, a student of  school with roll number 1, will stand in the front of the queue as the queue is empty initially.

In the image, the student is represented by (x,y), which means that student is in x school and his roll number is , and a rightmost cell in the front of the queue.

enter image description here

After the second operation, a student of  school with roll number 1, will stand behind the first student as there is no other member of the same in the queue.

enter image description here

After the third operation, a student of  school with roll number 2, will stand behind the member of his school in the queue.

enter image description here

After the fourth operation, the student in the front will put his name in the Goblet of Fire and move out of the queue.

enter image description here

After the fifth operation, the student in the front will put his name in the Goblet of Fire and move out of the queue.

enter image description here

 Solution With Description

Detailed Explanation:
In this question, the enqueue operation is defined as :
If a student of school x comes and there was already a student of school x in the queue, he will stand behind him in the queue, otherwise, he will stand at the end of the queue.

Approach 1: We simulate it the way it is given, that is, when a new student comes we search for his schoolmate in the current queue from the end of the queue. If we find a student from his school, we insert the new student after him and shift all other students one unit back in the queue. If no student of his school is there, we insert the new student in the end of the queue. This would take  time, as we are scanning the entire queue and then shifting the elements.
This approach would take time which will be too slow for the question.

Approach 2: Let us think in a different way. Say we have 4 queues, one for each school. We also have one more queue which keeps track of the schools in the original queue.
Example:
The initial queue is : (2,1) , (2,2) , (1,1) , (1,2) . (the first number being the school number and the second the roll number).
Then the four queues would look like:
 {1,2} ; first school has two students in the queue with roll numbers 1 and 2.
 {1,2}
 {}; there is no student of school 3 in the given queue.
 {}
The other queue is:
 {2,1}
So, q keeps track of which school is presently at what position in the original queue. If we do two dequeue operations , then  will become empty and  would look like:
{1}
Say we now enqueue (2,3), then {3} and  {1,2}.
So, what’s the advantage of this approach?
When we do any enqueue operation, we enqueue the student in it’s school’s queue. If there was no student of his school till now in the original queue, we enqueue his school in the queue . All this takes  time as we are only doing enqueue operation and no shifting is required.
When we do dequeue operation, we simply dequeue the student from his school’s queue. If after this the school’s queue becomes empty, we dequeue the school from queue . This also takes  time.

Pseudo Code:

queue <int> q, q1[5];
input(Q);
for i from 1 to Q:
{
    input(c);
    if(c == 'E')
    {
        input(x);input(y);
        if q has no entry for school x:
            q.push(x);
        q1[x].push(y);
    }
    else
    {
        x = q.front();
        y = q1[x].front();
        q1[x].pop();
        if(q1[x].empty()) q.pop();
        print x and y;
    }
}

 

Time ComplexityQ is the number of queries.

Space Complexity: O() because in a worst case, all operations would be enqueued operations and then a sum of all queue lengths would be .

Source: HackerEarth

{Code With Code@ter}

Give Your Reviews



One thought on “Little Monk and Goblet of Fire || Medium Problem”

  • koushmitha March 17, 2018 at 6:07 am

    can u pls send me the full code

     

    Reply

Leave a Reply