SBTG - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

In a competition, Chef has a score of X. There are N other participants; participant i has a score of A_i.

At most K times, Chef can do the following:

  • Choose a participant i other than himself.
  • Set A_i to 0.
  • Increase X by 100.

Find the minimum possible rank Chef can attain.
Chef’s rank is defined to be the number of people with a strictly larger score than him.

EXPLANATION:

Since K \le N, it’s ideal to sabotage K different people.

Chef’s rank is dependent on the number of people with larger scores; so it makes sense to sabotage people whose scores are large.
In particular, the natural greedy choice of “always sabotage the person with maximum score” is optimal.

This allows us to solve the problem in \mathcal{O}(NK) by repeating the following algorithm K times:

  • Find the maximum element of A.
    This takes \mathcal{O}(N) time, since you can just iterate across A.
  • Set this maximum to 0, and increase X by 100.

In the end, count the number of elements of A that are greater than X, and output that plus one.

It’s also possible to solve the problem faster.
Note that the elements set to 0 will exactly be the K largest elements of A.
This allows for the solution of sorting A in ascending order and just directly setting the last K elements of A to zero afterwards; taking \mathcal{O}(N\log N) time independent of K.

TIME COMPLEXITY:

\mathcal{O}(NK) or \mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, x, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    
    for i in range(k):
        a[n-1-i] = 0
        x += 100
    
    ans = 1
    for i in range(n):
        if a[i] > x: ans += 1
    print(ans)
1 Like
2

It can be Solved in o(N)

We don’t need to sort We just need the number of scores larger
So, greedily add 100*k to chef score and count how many scores are higher than that and greedily remove k chef’s from it

def solve():

    n,x,k=map(int,input().split())
    a=list(map(int,input().split()))
    a=[i for i in a if i>(x+(100*k))]
    print(max(1,len(a)-k+1))
3 Likes