AOC03 - Editorial

editorial
, ,
1

PROBLEM LINK:

Problem link

DIFFICULTY:

EASY

PREREQUISITES:

Greedy

PROBLEM:

Find the maximum points a team can win, given that a team gets k points, where k is the number of matches played till then.

EXPLANATION:

A team gets k points if it wins the match. Greater the value of k, greater is the points. So, to maximize the points the team can get, we need to make sure all the wins come as late as possible. The schedule should be in such a way that all the teams stronger than Chef’s team should be completed first before competing a team with lesser power.
Let count be the number of teams which have lesser power than Chef’s team. Now the points that Chef’s team will earn is (N - count + 1) + (N - count+ 2) + (N - count + 3) +… + N. As we can see this is an Arithmetic Progression. So we can apply the sum of A.P formula to find the total points earned by his team.
\frac{count}{2} * ((N - count + 1) + N)

Time Complexity:
O(n)

Setter's Solution 
mod=1000000007
t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    count = 0
    ans = 0
    for i in range(n):
        if p[i] < m:
            count += 1
    print((count*((2*n)+1-count)//2)%mod)
2 Likes