Code Corona 2020 Editorial (CORO2020)

Contest Link: www.codechef.com/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

Organiser: Programming Club, Department of Computer Science and Engineering, CTAE, Udaipur

Problem Setters: hritikkumar, manassingh557, & zenabbw

Tester: hritikkumar

Editorialist: hritikkumar

1. Code Karona! (CODECORO)

Problem Link: https://www.codechef.com/CORO2020/problems/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)

Problem Link: https://www.codechef.com/CORO2020/problems/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 = [0]

for i in range(N):
if i==0:
    if (sumArr-A[0])%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)

Problem Link: https://www.codechef.com/CORO2020/problems/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)

Problem Link: https://www.codechef.com/CORO2020/problems/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[100005],i,j,n,b[100005]={0},c[100005]={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)

Problem Link: https://www.codechef.com/CORO2020/problems/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[205][205][1010] = {};

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[0][0][0] = 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][0][x];
        ans %= MOD;
    }

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

    return 0;
}

Problem Setter: hritikkumar

2 Likes