ADMINSHOP Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Kanhaiya Mohan
Tester: Felipe Mota, Abhinav Sharma
Editorialist: Pratiyush Mishra

DIFFICULTY:

1529

PREREQUISITES:

None

PROBLEM:

CodeChef admins went on shopping at a shopping mall.

There are N shops in the mall where the i^{th} shop has a capacity of A_i people. In other words, at any point in time, there can be at most A_i number of people in the i^{th} shop.

There are X admins. Each admin wants to visit each of the N shops exactly once. It is known that an admin takes exactly one hour for shopping at any particular shop. Find the minimum time (in hours) in which all the admins can complete their shopping.

Note:

  1. An admin can visit the shops in any order.
  2. It is possible that at some point in time, an admin sits idle and does not visit any shop while others are shopping

EXPLANATION:

For each test case, we are given the number of shops N, the number of admins X and the maximum people that can shop at a particular store simultaneously.

Since each Admin must necessarily visit all the N shops once, so clearly the minimum time required in case of no restrictions is N.

When the maximum number of admins are limited for the shops, we first find the shop which allows for the minimum number of admins at the same time. This shop will tell us about the minimum time in case the shifts are more than N otherwise the answer will remain N.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution

1 Like
2

I did it in the same way as in editorial. Can anyone point out where did I go wrong here?((Link)

3

This statement is wrong result = max(n, (x+1)/mini);
Instead you should write

if(x % mini == 0) result = max(n, x/mini);
else result = max(n, x/mini + 1);

1 Like
4

OOOO… yes I understand now, while deriving the solution i used mini = 2. thats why at that time i wrote (x+1)/mini… silly me :cry:

1 Like
5

Suppose the given input for a test case is

2 5 (N X)
1 1 (A1 A2)

The output should be 6. But according to the editorial, output is 5. Is there any other possible arrangement such that the output would be 5?

16505057453874196472580375608710
165050574538741964725803756087101920Ă—1440 148 KB

3 Likes
6 
Hour 1: 1 2
Hour 2: 2 3
Hour 3: 3 4
Hour 4: 4 5
Hour 5: 5 1
6 Likes
7

Please, tell where I am making the mistake.
Here is my code:

from math import ceil
for i in range(int(input())):
    n_shop,x_admin= map(int,input().split())
    
    #input capacity
    capacity= list(map(int,input().split()))
    
    if n_shop>=x_admin:
        print(n_shop)
    
    else: 
        min_capacity= capacity[0]
        
        for cap in capacity:
            if min_capacity>cap: min_capacity= cap
        
        if min_capacity>=x_admin: print(n_shop)    
        else: print(ceil(x_admin/min_capacity))
8

Can anyone tell me with the proof?like why solution is working?

4 Likes
9

Right. The editorial only shows that it would be a lower bound, but it does not show that it can be actually achieved.

10

PROOF BY INDUCTION

11

What is the answer to this?
1
2 3
1 1

3? How?

12 
Hour 1: 1 2
Hour 2: 2 1
Hour 3: 3
13

can anyone pls help me to find out why my following binary search solution is not working?
link

14 
Hour 1: 1 2
Hour 2: 2 3
Hour 3: 3 1
1 Like
15

according to your case there are 2 shops and 3 admins, let’s name the shop A,B and admins with number 1,2,3.
Firstly admins 1,2 will shop in shop A and B in one hour now admin 1 will enter shop B and admin 3 will enter shop A in the second hour, finally admin 1 has completed its task by entering both shops, but admin 3 needs to visit shop B and admin 2 needs to visit shop 1. So that takes additional one hour, hence total hours are 3.

Hour Shop A Shop B
1 admin(1) admin(2)
2 admin(3) admin(1)
3 admin(2) admin(3)

1 Like
16

@yes_v one possible arrangement can be
1 2
2 3
3 4
4 5
5 1

Output would be 5 in this case

17

Admin 3 did not visit shop 2.

18

Oh, yeah, that was a mistake. The answer given by @anon80432234 is correct.