Can anyone please explain the priority queue approach to the SCHEDULE problem.

general
, ,
1

How this problem can be solved using priority queue. And can there be DP approach to solve this problem.

2

please check the first comment on its editorial page
here is the link https://discuss.codechef.com/questions/92702/schedule-editorial

3

@anno

I have already seen that, I didnā€™t understand that.

4

The use of priority queue is clever if you ask me.

  1. The first thing to understand is the priority queue is not like normal queue. It maintains queue according to ā€˜prioritiesā€™. Here, it is making sure that the segment with longest length is at top.
  2. The next step is checking if we have already reduced the consecutive characters to minimum or not. The <=2 is there as, we have already checked if 1 is achievable or not, and in case one is not achievable the immediate minimum after it is 2.
  3. the variable ix stores the index where length is stored to.
  4. The concept of the ā€˜big numberā€™ seems tricky, but conceptually is simple. It just gives the length of the consecutive segments after placing ā€˜10000 - id +1ā€™ flips. Might seem strange at sight, but see how it goes-

Lets se we have ā€œ1111100110ā€.
The longest segment here is ā€˜11111ā€™

    We know its len=5, and the 'big number' associated with it is, lets say, 10000 
    Have a look at variable im. Appreciate that its just storing the number of flips.
    
    im= 10000-(10000-1) = 1.
    
    Now, since flip given is 1, the most appropriate place to flip is the centre, which would make new segment as '11011' . The length of consecutive segment would then be 2. And if you look at his formula, the-
    
    currtop= trueval/(im+1);
    
    is doing nothing but calculating the length of segment on placing the flip. For our case, its-
    
    currtop = 5/(1+1) =2.
    
    Now what if number was 11111111100101 (9 consecutive 1s)
    
    First flip would make segment like 111101111. 
    We will act on the '1111' segment.
    
    The procedure is same, except one key observation which must be made (hence why I took this example)-
    
    We have the TRUE LENGTH of the segment BEFORE FLIPS stored in array. So now, everything is same, except that-
    
    big num = 9999 
    length = 9
    
    Now you might seem confused at this step, but look at the working of currtop.
    
    The number of flips placed on original segment would be, 10000-9999+1 = 2.
    
    The ideal position to place a flip is, after every third element. So the length would now store-
    
    9/(2+1) = 3.
    
    This is the case of -
    
    111011101

Appreciate the fact that since we are REMOVING the old queue and then adding ONLY 1 queue, the answer we get is ideal. It first places one flip in centre, if its STILL largest, it instead places 2 flips at one third distanceā€¦and keeps on trying placing (n-1) flips at 1/n th distance. This, till the length of consecutive segment is largest in it. As soon as its length is no more largest, another element comes at top due to priority queue.

And the while (kā€“) makes sure that we donā€™t use more than necessary flips.

Have a look at his code and simultaneously read the variable description/objectives I gave.

If something is not clear, feel free to get back at it.

(BTW: I cant say if dp angle is possible or not. I am not yet familiar with dp where we place stops or flip positions)

3 Likes
5

nice explanation