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")
```