 # ENCNOV - Editorial

Author: Anjali Jha
Tester: Sunita Sen

EASY

None

# PROBLEM:

There are N integers in an array. The elements follow the below rules:

1. The number of unique integers in the array lies in the range L to R (both inclusive).
2. Every element in the array is either 1 or x, in which case x/2 is also definitely present in the array.
The maximum and minimum sum of all elements of the array needs to be printed which satisfies the above constraints.

# EXPLANATION:

All the elements will surely be powers of 2 and only then rule 2 can be satisfied.

To find the minimum sum of elements, there must be at least L unique integers. Therefore, we add 2k to min, where 0 \leq k \leq L-1. After satisfying the constraint of adding L unique integers, we are left with N-L integers. The smallest possible number which can be present in the array is 1. Hence we add (N-L)*1 to min.

To find the maximum sum of elements, there must be maximum R unique integers. So we add all 2k to max, where 0 \leq k \leq R-1. After satisfying the constraint of adding R unique integers, we are left with N-R integers. The biggest possible number which can be present in the array is 2R-1. Hence we add (N-R)*2R-1 to max.

For example, given N=5, L=2, L=4.

There must be at least 2 unique integers. Therefore, add 20 and 21 to min. Remaining 3 elements must be 1 to make the sum minimum. Therefore, min=1+2+1+1+1.

There must be maximum of 4 unique integers. Therefore, add 20, 21, 22 and 23 to max. Remaining 1 element must be 23 to make the sum maximum. Therefore, max=1+2+4+8+8.

# TIME COMPLEXITY:

The time complexity will be O(log N)

# SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define ll long long
using namespace std;

void solve() {
int n,l,r;
cin>>n>>l>>r;
int x=pow(2,l-1);
int y=pow(2,r-1);
int mn=0,mx=0;
while(x) {
mn+=x;
x=x/2;
}
mn+=(n-l);
int k=1;
while(k<=y) {
mx+=k;
k*=2;
}
mx+=(n-r)*y;
cout<<mn<<" "<<mx<<endl;
}
int main(){
ios ::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
solve();
return 0;
}

5 Likes