CODE-O-FIESTA Editorial

editorial
1

This is an editorial of CODE-O-FIESTA contest organized for students of SVIT, Vasad.
Contest Link

Problem 1: Plus One

Explanation

Let’s sort the numbers in ascending order. It becomes immediately clear that it is not profitable for us to increase the numbers that are equal to the last number (the maximum of the array).

It turns out that every time you need to take such a subset of the array, in which all the numbers, except the maximums. And once for each operation, the numbers in the subset are increased by one, then how many times can the operation be performed on the array?
Accordingly max(a)−min(a).

Solution 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    print(max(a)-min(a))

Problem 2: Maintain Mean

Explanation

First of all, instead of the mathematic mean, let’s consider the sum of
elements. If the mathematic mean is k, then the sum of elements of the array
is k⋅n. Let’s denote the sum of elements in the original array as s. Note s
is always an integer.

If we remove two elements from the array, the resulting sum of elements should
become k⋅(n−2)=s⋅(n−2)/n. So, the sum of the elements we remove should be
exactly 2s/n.

If 2s/n is not an integer, the answer is 0. Otherwise, we have to find the number of pairs
(i,j) such that i<j and a_i+a_j=2s/n. This is a well-known problem.

To solve it, you can calculate the number of occurrences of each element and
store it in some associative data structure (for example, map in C++). Let
cnt_x be the number of occurrences of element x. Then, you should iterate on
the element ai you want to remove and check how many elements match it, that
is, how many elements give exactly 2s/n if you add ai to them. Let’s sum up all these values for every element in the array.

Unfortunately, this sum is not the answer yet. We need to take care of two things:

  • If for some index i, 2⋅ai=2s/n, then a_i matches itself, so you have to subtract
    the number of such elements from the answer;
  • every pair of elements is counted twice: the first time when we consider the first element of the pair, and the second time — when we consider the second element of the pair. So,
    don’t forget to divide the answer by 2.
Solution 
for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().strip().split()))
    d = {}
    for i in range(n):
        if arr[i] not in d:
            d[arr[i]]=1
        else:
            d[arr[i]]+=1
    s = sum(arr)
    if (2*s)%n != 0:
        print(0)
    else:
        f = (2*s)/n
        count=0
        for i in range(n):
            ext = f - arr[i]
            if ext in d:
                count += d[ext]
            if ext==arr[i]:
                count-=1
        print(int(count/2))

Problem 3: Bring AP

Explanation

Let’s iterate over the number that we want to multiply by m.

How can we check that we can multiply the current number so that an AP is formed?

Note that those 2 numbers that we do not touch should form an AP themselves. For instance, let at the current operation we want somehow multiply the number c. Then a=x_1, and b=x_2=x_1+d.

Note that b−a=x_1+d−x_1=d. Thus, we know what d is. Also we know that c=x_1+2⋅d=a+2⋅d. Let’s check if a+2⋅d is divisible by c. If yes, then we have found the answer, if not, then move on to the next number.

We do the same for a and b.

Be careful with non positive numbers, integer divisions and other edge cases.

Solution

for _ in range(int(input())):

a,b,c = map(int, input().split())
	t1 = 2*b - c
	t2 = 2*b - a
	t3 = a+c 
	if (t1%a==0 and t1>0) or (t2%c==0 and t2>0) or ((t3%2==0) and ((t3/2)%b==0) and t3>0	):
		print("yes")
	else:
		print("no")

Problem 4: Bet For Fans

Explanation

Note: GCD(a,b)=GCD(a−b,b) if a>b
If a=b, the fans can get an infinite amount of excitement, and we can
achieve this by applying the first operation infinite times.

Otherwise, the maximum excitement the fans can get is g=|a−b| and the minimum
number of moves required to achieve it is min( a mod(g),g − a mod(g)).

Solution 
for _ in range(int(input())):
    a, b = map(int, input().split())
    if a == b:
        print(0, 0)
    else:
        mx = abs(a-b)
        mn = min(a % mx, mx - a % mx)
        print(mx, mn)

Problem 5: Settle In

Explanation

You need to find maximum area with all 1s in matrix which can be solved by taking inspiration from a well-known problem - Largest rectangle under histogram

After getting maximum area, all you need to do is check if Chef and his friends can fit in that area.
Link for reference

Solution 
    def maxArea(M, n, m):
    res = hist(M[0])  
    for i in range(1,n):
        for j in range(m):
            if M[i][j]:
                M[i][j] += M[i-1][j]
        
        res = max(res, hist(M[i]))
    return res
def hist(row):
    q = []
    n = len(row)
    res = 0
    for i in range(n):
        while len(q) > 0 and row[i] <= row[q[-1]]:
            currIdx = q.pop()
            l=i
            if len(q) > 0:
               l = i - q[-1] - 1
            else:
                l=i
            curr = row[currIdx]*(l)
            res = max(res, curr)
        q.append(i) 
    while len(q) > 0:
        currIdx = q.pop()
        l=n
        if len(q) > 0:
            l = n - q[-1] - 1
        else:
            l=n
        curr = row[currIdx]*(l)
        res = max(res, curr)
    return res
for _ in range(int(input())):
    arr = list(map(int, input().strip().split()))
    n,m,k=arr[0],arr[1],arr[2]
    M = []
    for i in range(n):
        a = []
        a = list(map(int, input().strip().split()))        
        M.append(a)

    res=(maxArea(M,n,m))
    print(res)
    print("YES") if res >= (k+1) else print("No")
1 Like