# Code Corona 2020 Editorial (CORO2020)

This contest was organised by Programming Club, CTAE. It was mainly organised for students of CTAE, Udaipur. Now, we have made it public. You can check it out. Here is the explanation & solution for every problem statement.

Contest Manager: hritikkumar

Problem Setters: hritikkumar, manassingh557, & zenabbw

Tester: hritikkumar

Editorialist: hritikkumar

1. Code Karona! (CODECORO)

Explanation:
You have given T test cases. For each test cases, We will get input N (No. of items). After in next line, We will get N items’ expenses. We have to print the maximum & minimum in all the items.

Solution:

``````#include<bits/stdc++.h> // all header files
using namespace std; //namespace created as std
int main(void)
{
int t; //test cases
cin>>t;
while(t--)
{
int n;
cin>>n;
int e[n];
for(int i=0;i<n;i++)
{
cin>>e[i];
}
int max = INT_MIN, min = INT_MAX;
for(int i=0;i<n;i++)
{
if(e[i]>max)max = e[i];
if(e[i]<min)min = e[i];
}
cout<<max<<endl<<min<<endl;
}
return 0; //return type is int
}
``````

Problem Setter: hritikkumar

2. Practical Exams Revision (CCPC01)

Explanation:
A problem to use simple divisibility rules.

Take the cumulative sum of the array. For a particular index, subtract that number and then check if the remaining sum is divisible by 3 or not.

Take the previous value a[i-1] and the last value a[n] for checking the divisibility by 2 and 5.

For queries: For a particular index, store how many lucky indices are there before that index. Then for given L and R the answer would be answer[R] - answer[L-1] .

Solution:

``````N = int(input())
A = list(map(int, input().split()))

ans = []
sumArr = sum(A)
result = 

for i in range(N):
if i==0:
if (sumArr-A)%3 and A[-1]==0:
result.append(1)
else:
result.append(0)
elif i==N-1:
if (sumArr-A[-1])%3==0 and A[-2]==0:
result.append(result[-1]+1)
else:
result.append(result[-1])
else:
if (sumArr-A[i])%3==0 and (A[i-1] + A[-1])%10==0:
result.append(result[-1]+1)
else:
result.append(result[-1])

Q = int(input())
for _ in range(Q):
L, R = map(int, input().split())
print(result[R] - result[L-1])
print('\n')
``````

Problem Setter: zenabbw

3. Zenab and Corona Research (CCPC02)

Explanation:
Initially, let the Answer=N , the maximum possible value. Now, we know that if someone is related to some other guy, we can claim that “Only 1 of the 2 need to be affected initially” as the other one will automatically get affected later.

So, what We propose is, make the graph. Do DFS( mind it, its a possible disconnected graph!) and reduce the answer as you find you can reach/infect more and more people by given relation. Didn’t try it, but it should work, and that too in roughly ~O(N)O(N) time.

Solution:

``````def find(num):
temp=[]
while l[num]!=num:
temp.append(num)
num=l[num]
for i in temp:
l[i]=num
return num

def union(a, b):
a1 = find(a)
b1 = find(b)
if a1!=b1:
l[a1]=b1

T = int(input())
for i in range(T):
n1 = ""
while n1=="":
N = input().split()
for j in N:
n1+=j
N = int(n1)
R = int(input())
l = [a for a in range(N)]
for _ in range(R):
x, y = map(int,input().split())
union(x, y)
val = 0
for k in range(N):
if l[k]==k:
val+=1
print(val)
``````

Problem Setter: zenabbw

4. Mudit and Sequences (CCPC03)

Explanation:
The main idea is DP. Let’s define dp [ x ] as the maximal value of the length of the special sequence whose last element is x , and define d [ i ] as the (maximal value of dp [ x ] where x is divisible by i ).

You should calculate dp [ x ] in the increasing order of x. The value of dp [ x ] is (maximal value of d [ i ] where i is a divisor of x ) + 1. After you calculate dp [ x ], for each divisor i of x , you should update d [ i ] too.

This algorithm works in O ( nlogn ) because the sum of the number of the divisor from 1 to n is O ( nlogn ).

Note that there is a corner case. When the set is {1}, you should output 1.

Solution:

``````#include<iostream>
using namespace std;
int main()
{
int a,i,j,n,b={0},c={0},p=0,t;
cin>>t;
while(t--)
{
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];
for(j=1;j*j<=a[i];j++)
{
if(a[i]%j==0)
{
c[i]=max(c[i],c[b[a[i]/j]]+1);
if(j>1)
c[i]=max(c[i],c[b[j]]+1);
p=max(p,c[i]);
b[j]=b[a[i]/j]=i;
}
}
}
cout<<p<<endl;
}
}
``````

Problem Setter: manassingh557

5. Manas and Classes (CCPC04)

Explanation:
This is a dynamic programming problem. Notice that the total imbalance of the groups only depends on which students are the maximum in each group and which are the minimum in each group. We thus can think of groups as intervals bounded by the minimum and maximum student. Moreover, the total imbalance is the sum over all unit ranges of the number of intervals covering that range. We can use this formula to do our DP.

If we sort the students in increasing size, DP state is as follows: the number of students processed so far, the number of g groups which are currently “open” (have a minimum but no maximum), and the total imbalance k so far. For each student, we first add the appropriate value to the total imbalance ( g times the distance to the previous student), and then either put the student in his own group (doesn’t change g ), start a new group (increment g ), add the student to one of the g groups (doesn’t change g ), or close one of the g groups (decrement g ).

Runtime: O ( n^2 * k )

Solution:

``````#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
const ll MOD=1000000007;
#define all(x) x.begin(), x.end()

int dp = {};

signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
vi a(n+1);
for(int x = 1; x <= n; x++)
{
cin >> a[x];
}
sort(all(a));

dp = 1;

for(int x = 1; x <= n; x++){
for(int j = 0; j <= x; j++){
for(int v = 0; v <= k; v++){
int vv1 = v+j*(a[x]-a[x-1]);
int vv2 = vv1-(a[x]-a[x-1]);
int vv3 = vv1+(a[x]-a[x-1]);

// Lone set
if(vv1 <= k){
dp[x][j][vv1] += dp[x-1][j][v];
dp[x][j][vv1] %= MOD;
}
//No contrib
if(vv1 <= k){
dp[x][j][vv1] += (ll(j)*dp[x-1][j][v]) % MOD;
dp[x][j][vv1] %= MOD;
}
//New set
if(vv2 <= k and j > 0){
dp[x][j][vv2] += dp[x-1][j-1][v];
dp[x][j][vv2] %= MOD;
}
//Close set
if(vv3 <= k and j < x){
dp[x][j][vv3] += (ll(j+1)*dp[x-1][j+1][v]) % MOD;
dp[x][j][vv3] %= MOD;
}
}
}
}

ll ans = 0;
for(int x = 0; x <= k; x++){
ans += dp[n][x];
ans %= MOD;
}

cout << (MOD + ans) % MOD << endl;

return 0;
}
``````

Problem Setter: hritikkumar

2 Likes