A

The only numbers which do not have a odd multiple are powers of $$${2}$$$, i.e. numbers of form $$${2^x}$$$ where $$${x>=0}$$$
You can create an array $$${B}$$$ of size about 50 such that $$${B[0]=1 ~and ~B[i]=B[i-1]*2}$$$ for $$${i>=1}$$$ and check if the given number is equal to any element of $$${B}$$$. Don't forget about overflow while multiplying with 2.

B

If there exists a answer, $$${n~=~X*2020+Y*2021}$$$ where $$${X>=0 ~and~ Y>=0}$$$. Just iterate over $$${X}$$$. Let $$${m~=~n-X*2020}$$$. If $$${m}$$$%$$${2021==0}$$$ answer exists and if $$${m<0}$$$ break the loop.

C

Create two arrays $$${cnt_{boys}}$$$ and $$${cnt_{girls}}$$$ which maintains in how many pairs is a girl and boy involved.
Now iterate over all given one-boy-one-girl pairs. Let the current pair contain boy numbered $$${X}$$$ and girl numbered $$${Y}$$$. Their partners can be the other pair which does not involve the girl $$${Y}$$$ and boy $$${X}$$$, i.e. $$${(k-1)-(cnt_{boys}[X]-1)-(cnt_{girls}[Y]-1)}$$$.
$$${k-1}$$$ because this paired can't be paired with itself and $$${(cnt_{boys}[X]-1)-(cnt_{girls}[Y]-1)}$$$ because this pair is also counted in $$${X's~and~Y's}$$$ appearance.
You need to divide the final answer by two since each pair is counted twice.

D

This one was a very standard problem.
Make two array $$${a~and~c}$$$ where $$${a}$$$ contains the regular apps and $$${c}$$$ contains important apps. Now sort apps in $$${a}$$$ and $$${c}$$$ in descending order of their memory. It can be proved that between two apps of same importance it is better to remove the one with more memory.
Now iterate over number of apps of regular apps. Let the number of regular apps in current iteration $$${x}$$$. Let $$${sum_a~=~sum ~of ~first ~x ~elements ~of ~a}$$$. Now find out how many apps are required from $$${c}$$$ to create a sum $$${>=m-sum_a}$$$. Let $$${y}$$$ such minimum apps. Then $$${ans=min(ans,x+2*y)}$$$

E

I guess constraints were there to fool participants towards a dp solution instead of easier combination solution
Let $$${cnt[i]}$$$ be the number of bloggers with $$${i}$$$ follower. Let $$${X}$$$ be the person with least followers in optimal selection. Let $$${p}$$$ be the number of followers of $$${X}$$$. Let $$${k}$$$ be the number of bloggers with $$${p}$$$ followers in the optimal selection. Then the $$${cnt[p] \choose k}$$$.
To find out $$${X~and~}$$$ sort in decreasing order of followers and keep on choosing till $$${sum of followers>=required followers}$$$.

G

We will iterate over max possible length of the array. The main concept is that if we have a beautiful array of with smallest element $$${x}$$$ and $$${y}$$$ is a factor of $$${x}$$$ then after adding $$${y}$$$ to the array it will still be beautiful. To notice this take any example and sort them in ascending order. Now since $$${x}$$$ is the smallest, it must divide every element of the array and since $$${y}$$$ divides $$${x}$$$, it will also divide all the elements of the array.
Let $$${cnt[i]=the ~number ~of ~times ~i ~appears ~in ~the ~array}$$$.
Let $$${dp[i]=the ~length ~of ~maximum ~array ~with ~smallest ~element ~i}$$$.
Now iterate from $$${i=max_n ~to ~i=0}$$$. Do $$${dp[i]+=cnt[i]}$$$ to include elements equal to $$${i}$$$.
If $$${dp[i]>0}$$$ then for all factors $$${X}$$$ of $$${i}$$$, $$${dp[x]=max(dp[x],dp[i])}$$$.
$$${max_{len}=max(dp[i],max_{len}}$$$
$$${ans=n-max_{len}}$$$

Given an array A of length N and a number B find the number of subarrays A[l....r] such that A[l]+A[r] and max(A[l...r]) are congruent modulo B
1<=N,B<=500000
1<=A[i]<=1e9
The contest of which this question is has ended.

I thought the explanations which I came up for Yestersday's A,C and E were easier to understand. So here they are.

A

hint

Try making solution of n=4 or n=5

solution

Handle $$$n=1$$$ ,$$$n=2$$$ and $$$n=3$$$ case separately Now $$$n>=4$$$ the answer will always have 9 in first position.Solution depends only on the first position at which we stopped.Suppose we stop at position $$$p>=3$$$.

If 1st position is stopped at time $$$t_1$$$, then second position must have stopped at time $$$t_2=t_1-1$$$, third at $$$t_3 = t_2-1 = t_1-2$$$ Since first position have 9 and second is stopped at a second earlier second position is 8 and similarly third position is 7.

If u have tried building solution for n=4 you must have observed that it is possible to 989 in first three positions respectively which better solution than the one we tried to construct above. Thus stopping at 2nd position when it shows 8 is optimal solution.

To construct rest of the string s[I]=(s[I-1]+1)%10

code

#include<iostream>
using namespace std;
int main(){
    int te;cin>>te;
    while(te--){
        int n;cin>>n;
        if(n==1){cout<<"9\n";continue;}
        if(n==2){cout<<"98\n";continue;}
        if(n==3){cout<<"989\n";continue;}
        int ans[n];
        ans[0]=9;
        ans[1]=8;
        ans[2]=9;
        for(int i=3;i<n;i++)ans[i]=(ans[i-1]+1)%10;
        for(int i=0;i<n;i++)cout<<ans[i];
        cout<<endl;
    }
}

C

hint

We are first trying to create a max negative value which we will then in final step subtract from a positive value

solution

Suppose the bags are $$$a_1,a_2,a_3……a_{n_1}$$$
$$$b_1,b_2,b_3…..b_{n_2}$$$
$$$c_1,c_2,c_3……c_{n_3}$$$
Let $$$SUM=a_1+a_2+a_3….+a_{n_1}+b_1+b_2+b_3….+b_{n_2}+c_1+c_2+c_3….+c_{n_3}$$$
We can have mainly have two type of final values

First We can subtract values $$$b_2,b_3,b_4…..b_{n_2}, c_1,c_2,c_3……c_{n_3}$$$ from $$$a_1$$$
The value of $$$a_1$$$ would then be $$$a_1-b_2-b_3-b_4…..b_{n_2}-c_1-c_2-c_3…..-c_{n_3}$$$
And then finally subtract $$$a_1,a_2,a_3…..a_{n_1}$$$ from $$$b_1$$$
The value of $$$b_1$$$ would then be
$$$b_1-(a_1-b_2-b_3-b_4…..b_{n_2}-c_1-c_2-c_3…..-c_{n_3})-a_2-a_3-a_4…a_{n_1}$$$
$$$=b_1+b_2+b_3….b_{n_1}+c_1+c_2+c_3…..+c_{n_3}-a_1-a_2-a_3-a_4…a_{n_1}$$$
$$$=sum-2*(a_1+a_2+a_3….a_{n_1})$$$

Second Another answer that we can construct is
Subtract values $$$b_2,b_3,b_4…..b_{n_2}, c_2,c_3……c_{n_3}$$$ from $$$a_1$$$
NOTE we are not subtracting $$$c_1$$$
The value of $$$a_1$$$ will be $$$a_1-b_2-b_3-b_4…..b_{n_2}-c_2-c_3…..-c_{n_3}$$$
Subtract values $$$a_2,a_3…..a_{n_1}$$$ from $$$c_1$$$
The value of $$$c_1$$$ will be $$$c_1-a_2-a_3-a_4…..a_{n_1}$$$
And then finally subtract $$$a_1$$$ and $$$c_1$$$ from $$$b_1$$$
The final value would then be
$$$b_1-(a_1-b_2-b_3-b_4…..b_{n_2}-c_2-c_3…..-c_{n_3})-(c_1-a_2-a_3-a_4…..a_{n_1})$$$
$$$=b_1+b_2+b_3….b_{n_2}+c_2+c_3+….c_{n_3}+a_2+a_3+a_4…a_{n_1}-a_1-c_1$$$
$$$=sum-2*(a_1+c_1)$$$

Thus the $$$answer=max(sum-2*(a_1+a_2+a_3….a_{n_1}),sum-2*(a_1+c_1))$$$
$$$Answer=sum-min(2*(a_1+a_2+a_3….a_{n_1}),2*(a_1+c_1))$$$
$$$Ans=sum-2*min((a_1+a_2+a_3….a_{n_1}),a_1+c_1)$$$
I have considered bags randomly without loss of generality
That mean I want to compare the bag which has minimum and sum of minimum elements of any two bags

code

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
int n1,n2,n3;
cin>>n1>>n2>>n3;
long long a[n1], b[n2], c[n3];
long long sum=0,sum_of_a=0,sum_of_b=0,sum_of_c=0;
long long min_elements[3]={(long long)1e9+3,(long long)1e9+3,(long long)1e9+3};
// 0 1 2 stores min elements of bag a b and c respectively

for(int i=0;i<n1;i++){cin>>a[i];sum+=a[i];sum_of_a+=a[i];min_elements[0]=min(min_elements[0],a[i]);}
for(int i=0;i<n2;i++){cin>>b[i];sum+=b[i];sum_of_b+=b[i];min_elements[1]=min(min_elements[1],b[i]);}
for(int i=0;i<n3;i++){cin>>c[i];sum+=c[i];sum_of_c+=c[i];min_elements[2]=min(min_elements[2],c[i]);}
sort(min_elements,min_elements+3);
long long min_sum_bag=min(sum_of_a,sum_of_b);
min_sum_bag=min(min_sum_bag,sum_of_c);
sum-=2*min(min_elements[0]+min_elements[1],min_sum_bag);
cout<<sum<<endl;
}

E

Solution

Let us see when the answer is definitely 0
Suppose three vertices x,y,z exists such that ax=ay=az and y lies on path from x to z (or z=x since undirected tree both are same)
In this scenario the answer is always 0.
This can be understood by the given image (I was not write the formal proof)

Try getting a distinctive root in this tree
After checking the above case we can simply iterate over nodes in any order.
Suppose we are node v If the value of the node is unique i.e. no other other element has same value as this node we don't need to anything. Otherwise we check which edge of this node leads us to another node having same value.
The condition which we checked initially assures that there will be exactly one such edge for each node.
Let this edge be E.Now all the node which do not contain this edge in their path to v cannot be distinctive roots. Once you try few cases of own it easy to understand why.
To implement the above solution we can arbitrarily root the tree, do a dfs and assign each vertex a in and out time. Now if we are at vertex v and vertex w is connected to v by an edge E1!=E we can cancel off all the vertex in subtree of v. To do so we can maintain array fin with initial values 0 and reduce all values from in[v] to out[v]+1 time.
Now to obtain final answer iterate over all node and if fin[in[v]]==0 increase answer.

code

Don't have clean implementation at the moment. I will write and update if this blog got some likes.