CHFQUEUE - Editorial

editorial
, , , , , , ,
1

PROBLEM LINKS :

Practice

Contest

Author and Editorialist Vineet Paliwal
Tester Roman Rubanenko

DIFFICULTY :

Cakewalk

PREREQUISITES :

Stacks , Queue , Modulo , Modular Arithmetic , Modular Multiplication

PROBLEM :

Given N chefs in a queue , each chef may delegate his/her task to the junior least ahead of him and go away . The Head Chefs fearfulness of the scenario is the difference in index of the two positions + 1 . Head Chef’s total fearfulness is product of individual fearfulness corresponding to each chef . Find total fearfulness . In case no junior lies ahead the fearfulness is 1 .

EXPLANATION:

The Naive Solution :

For each chef look at all chefs ahead of this chef in the queue till you find a junior chef and then update the Head Chef’s fearfulness . This has a time complexity of O(N^2) .

Using Stacks :

Start with given queue and an empty stack(of a structure of numbers and their indexes) .
For each chef put him on a stack if the top of stack is not senior to him otherwise pop out as many senior chefs from the stack as possible ( updating Head Chef’s fearfulness at each pop ) and finally push the chef on the stack .
The time complexity of this solution is O(N) .

Example Using Stacks :

Given the queue , 8 3 7 8 9 12 13 11 3 4

Initialize ans = 1 ; sp = 1000000007

Step One : Stack == [8,1]

Step Two : Stack == [3,2] ( ans *= ( 2 - 1 + 1 ) , ans %= sp => ans = 2 )

Step Three : Stack == [3,2] [7,3] ( ans remains same )

Step Four : Stack == [3,2] [7,3] [8,4] ( ans remains same )

Step Five : Stack == [3,2] [7,3] [8,4] [9,5] ( ans remains same )

Step Six : Stack == [3,2] [7,3] [8,4] [9,5] [12,6] ( ans remains same )

Step Seven : Stack == [3,2] [7,3] [8,4] [9,5] [12,6] [13,7] ( ans remains same )

Step Seven : Stack = [3,2] [7,3] [8,4] [9,5] [11,8] ( Two elements are popped out , ans need to be multiplied by 2 and 3 corresponding to each of pop . So ans = 12 )

Step Eight : Stack == [3,2] [3,9] ( Four elements are popped out . ans need to be multiplied (modularly) by 2 , 5 , 6 , 7 )

Step Nine : Stack == [3,2] [3,9] [4,10] .

Finish and output ans .

Point to Remember :

Take modulus with the special number given after each multiplication .

SETTER’S SOLUTION

TESTER’S SOLUTION

2 Likes
2

The stack-based solution is nice. Another simple solution (but with an O(N * log(K)) time complexity) is based on using a segment tree. Let’s build a segment tree over the K levels of seniority. Then we will traverse the chefs from N down to 1. For each chef i we need to find the smallest position associated to a level between 1 and a(i)-1. In the segment tree we will maintain for each leaf y from 1 to K the smallest position of a chef with level y. Thus, we only need to perform a query on the interval 1…a(i)-1 for the minimum value in this interval. After finding the answer for chef i we need to update the value stored in the segment tree for the leaf a(i) (because i is the current smallest position of a chef with level a(i)). Initially we will assume that each value associated to a leaf of the segment tree is +infinity (i.e. a very large value).

1 Like
3

@mugurelionut : Lunch time being for school students we try that problems be doable with simple concepts . It is difficult to prevent O(N log N) and O(N log K) solutions from passing when O(N) is expected complexity , especially in lunch time because we have to allow a good buffer time for poor I/O used by contestants as IOI ( ACM ICPC like contest for school students ) does not require / emphasize fast I/O . Thanks for bringing a different approach to light . Probably some other contestants too might have used a sub-optimal algorithm to get AC . Cheers , Happy Coding .

4

@vineetpaliwal: My post was not criticizing the fact that sub-optimal solutions got full points. For many problems it is very difficult to separate an O(N) algorithm from an O(N * log(N)) algorithm. And for lunch time contests it is probably even a good idea to allow such solutions to get full points. I only pointed out the segment tree solution because for some people it might be easier to grasp (as long as they are familiar with the segment tree data structure, which is rather well-known). A binary indexed tree (BIT) could also be used instead of a segment tree.

1 Like
5

i have tested a lot of cases on my system and i m gettin right answer…bt i m getting WA for my solution on submission
plz help… following is the link to my solution http://www.codechef.com/viewsolution/5578916