ZIO17003 - Editorial

DIFFICULTY:

EASY

PREREQUISITES:

Math

Problem link:

PROBLEM:

There are N children in the question playing hide and seek. In each round, one of them seeks and others hide.
You are given an array H of N numbers where H[i] represents the minimum number of rounds ith child have to hide to be satisfied. (1 based Indexing)
We aim to determine the least number of rounds that need to be played so that every child is satisfied.

EXPLANATION:

Let’s say the number of rounds played is M. Now, the ith child can seek in at most (M - H[i]) rounds. ( 1 based Indexing) . And the summation of the number of rounds every child seeks has to be equal to M. So, we can have the following derivation based on upper observations.

\sum_{i = 1}^{N}(M - H_i) \geq M

(M*N - \sum_{i = 1}^{N} H_i ) \geq M

(M*N - \sum_{i = 1}^{N} H_i - M) \geq 0

(M*(N-1) - \sum_{i = 1}^{N} H_i ) \geq 0

(M*(N-1) - \sum_{i = 1}^{N} H_i ) \geq 0

M \geq \dfrac{\sum_{i = 1}^{N} H_i } { (N-1)}

Now, using ceiling function, we can have the minimum estimation of M, that is,
M_1 = ceil(\frac{ \sum_{i = 1}^{N} H_i }{N-1} )

But there has to be at least M2 rounds of play where,
M_2 = max(H_i) ; i \epsilon [1,n]

Final answer will be,
M = max(M_1,M_2)

SOLUTIONS:

a.
N = 7
\sum_{i = 1}^{N} H_i = 65
M_1 = ceiling(65/6) = 11
M_2 = max(H[i]) = 15
M = max(M_1 , M_2) = 15

b.
N = 12
\sum_{i = 1}^{N} H_i = 100
M_1 = ceiling(100/11) = 10
M_2 = max(H[i]) = 9
M = max(M_1 , M_2) = 10

c.
N = 15
\sum_{i = 1}^{N} H_i = 2019
M_1 = ceiling(2019/14) = 145
M_2 = max(H[i]) = 140
M = max(M_1 , M_2) = 145

1 Like

The formula should work for this also right ?
I dont understand why the formula is not working and we are again taking M2 and all

I understood everything else
Thanks a lot !! :slight_smile:

3 Likes

Please explain subtask 3 again, I didn’t understand it .
Thank you

4 Likes

Hey @raj1238,
Thank You for the editorial but I Dont get it. Can you please explain it a little bit more…

4 Likes

An alternate solution:

Let X=Max(H[i]), be the least number of rounds required.

X-H[i] = Number of rounds “i” will be seeker (since H[i] represents hider count)

The algo :

  1. Y= Summation (X-H[i])
  2. if Y < X then: X=X+1. Go to Step 1
  3. if Y >= X, then X is the answer.

An alternate solution:

Let X=Max(H[i]), be the least number of rounds required.

X-H[i] = Number of rounds “i” will be seeker (since H[i] represents hider count)

The algo :

  1. Y= Summation (X-H[i])
  2. if Y < X then: X=X+1. Go to Step 1
  3. if Y >= X, then X is the answer.