MORECOOK - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Alice has N friends, the i-th friend has A_i cookies.
Alice has X cookies. Find the minimum number of extra cookies she should buy to ensure that:

  1. At least one friend has less cookies than her, and
  2. No friend has an equal number of cookies to her.

EXPLANATION:

Let M = \min(A) be the minimum number of cookies some friend of Alice has.
As long as Alice has at least M+1 cookies, the first condition will be satisfied.

We’re trying to minimize the number of cookies Alice buys.
So, we have the following algorithm:

  • Let Y denote the final number of cookies Alice has.
    Start with Y = X.
  • Then, if Y \leq \min(A), no friend has less cookies than Alice, so increase Y by 1 and try again.
  • Similarly, if some friend has Y cookies (which can be checked by iterating through all N friends), increase Y by 1 and try again.
  • If Y\gt \min(A) and no friend has Y cookies, the final number of cookies is Y: so the number of cookies bought is Y-X.
    Once this is reached, stop.

All friends have \leq 100 cookies, so we’ll surely stop at Y = 101 at most, so this is fast enough.
Faster solutions exist but aren’t needed for the constraints here.

TIME COMPLEXITY:

\mathcal{O}(100\cdot N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    
    y = x
    while min(a) >= y or a.count(y) > 0: y += 1
    print(y - x)
1 Like