ENCNOV - Editorial

PROBLEM LINK:

Practice
Contest Link

Author: Anjali Jha
Tester: Sunita Sen

DIFFICULTY:

EASY

PREREQUISITES:

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